C 로 구현한 알고리즘 - 2부 자료 구조, 8장 해쉬 테이블(hash tables)

8장 해쉬 테이블이다.

(책에는 해시 테이블이라고 적혀 있지만, 난 해쉬가 어감이 더 좋아서...)

바로 고고싱...

해쉬 테이블(hash table)

해쉬 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성되는 자료구조 이다.

해쉬 테이블의 해쉬 함수는 키 값을 받아 그 키의 해쉬값(hash coding 또는 hash value)을 리턴한다.

간단한 해쉬테이블을 시각적으로 표시했을 때, 아래와 같은 그림으로 표시할 수 있다.

(Author: Jorge Stolfi, 원본: http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg)

해쉬 테이블의 장점은 상수 시간에 탐색이 가능한 것이다.

대신 다른 특징(혹은 단점?)은 순차적인 접근을 지원하지 않는 것이다.

따라서 이러한 특징에 맞는 상황에서 사용되어야 할 것이다.

추가적으로 해쉬 테이블의 특징을 좀 더 알아보자.

- 사용할 키와 해쉬 함수를 잘 선택하여 테이블에 균등하게 항목이 배분되도록 해야 한다.

- 다른 키값에 대해 같은 해쉬값(같은 테이블로 매핑되는 경우)을 가지는 경우 충돌(collision)이라고 한다.

- 충돌 해결 방법에는 여러가지가 있으며 대표적인 방법(책에 설명된)은

  연쇄 해쉬 테이블(chained hash table)과 개방 주소지정 해쉬 테이블(open-addressed hash table)이 있다.

위키피디아에 따르면 해쉬 테이블은 탐색 트리(search tree)나 다른 lookup 구조의 테이블보다 효율적이라고 한다.

이런 이유로 아래와 같은 곳에서 사용이 된다. (참조: http://en.wikipedia.org/wiki/Hash_table#Uses )

- Associative arrays (프로그래밍 랭귀지의 데이터 타입 같은 것. 예를 들면 Python 의 Dictionary 타입?)

- Database indexing

- Caches

- Sets

- Object representation

- Unique data representation

위키피디아에 상세한 설명이 되어 있으니, 해쉬 테이블에 대한 더 많은 정보를 원한다면 방문해 보기 바란다.

http://en.wikipedia.org/wiki/Hash_table

앞으로 나올 용어에 대해서 간단히 설명하면 다음과 같이 사용할 것이다.

n : 테이블의 항목 갯수

m : 버킷의 갯수

a : 부하 계수(load factor). a = n / m

해쉬 테이블 인터페이스

해쉬 테이블에 필요한 인터페이스는 간단한 편이다.

Data Insert, Remove, Lookup 정도?

중요한 건 키 값을 같이 넘겨주는 것이다.

해쉬 함수(hash function)

해쉬 함수 h 는 키값 k 를 받아 테이블 위치 x 에 매핑하는 함수이다.

k 의 값은 보통 정수임을 가정한다.

k 가 정수가 아니더라도 어렵지 않게 정수로 바꿀 수 있다.

(물론 k 가 같은 값이 나오지 않게 잘 바꿔야 하겠다)

책에서는 간단한 방법 2가지를 제시한다.

- 나눗셈 방법(devision method)

으로 표현할 수 있다. 일반적으로 m 의 값으로는 2의 제곱수는 피해서

2의 제곱수에 가깝지 않은 소수를 m 으로 선택한다.

- 곱셈 방법(multiplication method)

k*A 한 다음 여기에서 소수 부분만 택하여 m 을 곱한값에서 정수 부분만 택한값을 사용한다.

( A 값은 저렇게 하면 효율적이라고 Donald Knuth 란 분이 이야기 했나 보다. )

이것들은 간단한 방법들이니 좀 더 효율적인 해쉬 함수를 원한다면,

좀 더 공부가 필요하겠다.

충돌 해결(Collision resolution)

출동 해결 방법에는 여러가지가 있다.

좀 더 자세한 건 역시 위키피디아! ( http://en.wikipedia.org/wiki/Hash_table#Collision_resolution )

- 연쇄 해쉬 테이블(Sererate Chaining)

(Author: Jorge Stolfi, http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_LL.svg )

위 그림과 같이 한 버킷을 링크트 리스트로 구성하는 방법이다.

- 개방 주소지정 해쉬 테이블(Open addressing)

(Author: Jorge Stolfi,http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_SP.svg )
그림이 좀 헷갈려 보이긴 하지만, 위와 같은 충돌 발생시 다른 버킷에 저장하는 방식이다.

여기서 잠깐, 다른 버킷은 어떻게 선택하는가?

잘 알려진 방법으로는 다음과 같은 3가지 방법이 있다.

1. 선형 조사(Linear probing) : 다음 버킷을 조사. 주클러스터링 현상으로 과다한 조사 발생 가능성 있음.

2. 2중 조사(Quadratic probing) : i^2 번째의 버킷을 조사. 부클러스터링 현상으로 과다한 조사 발생 가능성 있음.

   (i 는 현재까지 조사한 위치의 갯수)

3. 2중 해싱(Double hashing): 해쉬 함수와 보조 해쉬 함수의 결과를 더하는 것이다.

2중 조사와 다른 점은, 키 값에 따라 다음 조사위치가 고정된 것이 아니라 달라진다는 것이다.

수식으로 표현하지면 위와 같다. 그러나 어떤 위치가 두 번 조사되기 전에 모든 위치들이

조사됨을 보장하기 위해 다음의 두 절차 중 하나를 따라야 한다.

a. m이 2의 제곱수이고 h2 가 항상 홀수를 리턴한다.

b. m이 소수이고 h2는 항상 m보다 작은 양수를 리턴해야 한다.

결론

여기에 적은 것은 해쉬 테이블의 일부분일 뿐이다.

이 글에서는 해쉬 테이블의 핵심만 기억하도록 하자.

해쉬 테이블의 정의, 좋은 해쉬 함수가 필요하다는 거, 그리고 충돌 해결이 필요하다는 거 정도?

역시 중요한 것은 실제로 적절한 곳에 사용하는 것이겠지...

해쉬 테이블에 대한 깊이 있는 이해를 위해서는 좀 더 공부가 필요하겠다.

 

(2012.7.2 추가)

Double Hashing이 항상 좋은 것은 아니다.

예를 들면 Double Hashing 함수에서 i 값이 증가 할 때, 그 interval 이 커서

cache 문제가 발생할 수 있다고 한다.

(참고: http://en.wikipedia.org/wiki/Double_hashing )

또한, 인터넷을 검색해서 적절한 second hash function 의 샘플을

찾지를 못하겠다. 나중에 꼭 쓸일이 있게되면 연구해 봐야겠다.

(2012.7.3)

굳이 인터넷을 검색하지 않아도,

책에 적절한 Double Hashing 의 적절한 샘플이 있었다.

(어젠 책이 없는 관계로...)

이 식에서 아래와 같은 방법의 해쉬 함수를 사용할 수 있다.