검색결과 리스트
Hash table에 해당되는 글 1건
글
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 의 적절한 샘플이 있었다.
(어젠 책이 없는 관계로...)
이 식에서 아래와 같은 방법의 해쉬 함수를 사용할 수 있다.
'공부' 카테고리의 다른 글
C 로 구현한 알고리즘 - 2부 자료 구조, 10장 힙(Heap)과 우선순위 큐(Priority Queue) (0) | 2012.07.03 |
---|---|
C 로 구현한 알고리즘 - 2부 자료 구조, 9장 트리(Tree) (0) | 2012.07.03 |
C 로 구현한 알고리즘 - 2부 자료 구조, 7장 집합(Set) (0) | 2012.06.21 |
C 로 구현한 알고리즘 - 2부 자료 구조, 6장 스택과 큐(Stack and Queue) (0) | 2012.06.20 |
C 로 구현한 알고리즘 - 2부 자료 구조, 5장 연결 리스트(linked list) (0) | 2012.06.20 |