본문 바로가기

2011

logo_main.gif


글: 정재준 (rgbi3307@nate.com ) / 커널연구회(www.kernel.bz)   2011-11-04


연재 차례
 1. C언어 소개
 2. 형태, 연산자, 표현
 3. 제어 흐름
 4. 함수와 프로그램 구조
 5. 포인터와 배열
 6. 구조체
 7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개


개요
많 은 애플리케이션들은 처리대상 데이터들을 삽입, 검색, 삭제하기 위해서 동적인 집합을 필요로 한다. 예를 들면, 컴퓨터 언어를 처리하는 컴파일러는 기호 테이블(Symbol Table)이라는 것을 관리하는데, 이곳의 요소들은 특정 문자열들을 식별 키로 하여 처리된다.
해시 테이블은 사전 입출력 동작(삽입, 검색, 삭제)을 효율적으로 하는 데이터 구조체이다. 처리 대상 데이터의 수가 n개일때, Linked List는 최악의 경우 O(n) 만큼의 처리시간이 소요되는 반면, 해시 테이블에서는 O(1) 만큼의 시간으로 처리될 수 있다.
해시 테이블은 일반적인 배열 형태로서 순번이 부여된 배열 요소에 직접 접근하는 방식(Directly Addressing)으로 O(1) 시간에 동작한다. 배열은 구성 요소마다 순번(위치 인덱스)을 가지고 있으므로 특정 키의 위치를 인덱스 연산하여 직접 접근할 수 있다. 인덱스 연산은 보통 키 값을 통해서 계산한다.
해시 함수(Hash Function)
해 시 테이블 알고리즘의 핵심은 데이터 요소들을 배열형태로 저장한 해시 테이블이다. 데이터 아이템의 키로부터 계산한 인덱스를 사용하여 배열 요소의 위치를 결정한다. 이러한 인덱스는 해시 함수를 통해서 산출된다. 해시 함수 hash는 다음과 같이 정의한다.

index = hash (key, arrayLength)

위 의 해시함수 hash는 key와 arrayLength를 매개변수로 전달받아서 index를 산출한다. 여기서 key는 데이터 아이템 값이고, arrayLength는 해시 테이블의 배열 길이이다. index는 해시 테이블의 배열 요소를 찾아가기 위한 인덱스(해시 값)가 된다.
해시 함수는 해시 테이블 알고리즘의 전체 성능에 많은 영향을 주므로 해시 함수를 잘 작성하는 것은 아주 중요하다. 해시 함수의 가장 기본은 해시 배열 인덱스 값(해시 값)이 균등한 분포로 산출되어야 한다는 것이다. 한쪽으로 몰려서 해시 값이 산출되면 충돌 문제를 해결하기 위한 비용이 증가한다. 균등한 분포의 해시 값 산출은 다소 어려운 문제이나 여러 가지 방법들이 도입되고 있다. 해시 값은 해시 테이블의 크기 범위 내에서 균등하게 산출되어야 한다. 이것을 위해서 2의 누승 형태나 소수(prime number)를 활용하기도 한다. 또한, 암호화 기법을 동원하기도 하고 나머지 연산 및 비트 마스킹 등을 한다.

위의 그림은 사람 이름과 전화번호를 연결하는 해시함수를 설명하는 예제이다. 위에서 buckets으로 표현한 것이 해시 테이블이며 이것의 크기는 16이다. 위에서 해시 함수 hash는 다음과 같이 해시 값(index)이 산출된다.

index = hash (key, arrayLength)
02 = hash (“John Smith”, 16)
01 = hash (“Lisa Smith”, 16)
14 = hash (“Sandra Dee”, 16)

아래 C언어 코드는 해시 함수를 실제로 작성하여 해시 값을 산출하는 것이다. 해시 함수는 다음과 같이 작성했다.

//hash 함수: 문자열 s를 위한 해시 값 산출
unsigned int hash (char *s, int length)
{
 unsigned hashval;

 for (hashval = 0; *s != ‘‘
맨 위로
맨 위로