해쉬 테이블 또는 해쉬 맵은 key와 value를 갖는 자료 구조이다. 주요 동작은 효율적인 검색(주어진 키(예를 들어, 사람 이름)로 적합한 값을 찾는(전화번호)) 이다. 해쉬 함수를 이용해서 주어진 키를 해쉬값으로 변환하고 해쉬값을 인덱스로 하여 원하는 값이 있는 버켓(bucket)을 찾아내는 것이다.
1. 시간 복잡도와 해쉬 테이블의 용도
해쉬 테이블은 종종 연관 배열, set, 그리고 캐쉬의 구현에 사용된다. 배열과 비슷하게, 해쉬 테이블은 평균적으로 검색에 테이블 내 아이템의 수와 상관없이 O(1)의 상수 시간 복잡도를 제공한다. 그러나 최악의 경우 검색 시간은 O(n)으로 나빠질 수도 있다. 다른 연관 배열 자료 구조와 비교해, 해쉬 테이블은 많은 수의 자료가 저장될 때 좀 더 유용하며 데이터 셋의 크기를 예측할 수 있을 때 더욱 유용하다.
해쉬 테이블의 검색 성능은 해쉬 함수의 성능과 해쉬 테이블의 크기에 좌우된다. 충돌이 발생하면 할수록 성능은 점점 O(n)에 가까워지므로 충돌을 최대한 억제시키는 것이 해쉬의 핵심 포인트다.
2. 해쉬 함수
좋은 해쉬 함수는 해쉬 테이블 성능 향상에 필수이다. 질 낮은 해쉬 함수는 데이터들의 key를 같은 bucket으로 유도하는 경우가 많아짐으로써 충돌이 증가하고 이는 곧 심각한 해쉬 테이블의 성능 저하로 이어진다.(물론 어떤 구현으로도 충돌을 완전히 피할 수는 없다) 게다가 몇몇 해쉬 함수들은 계산 비용이 너무 많이 들어 상당히 부담스럽다.
좋은 해쉬 함수를 선택하는 것은 상당히 까다로운 일이다. 다른 알고리즘이나 자료구조와는 다르게 해쉬 함수에 대해서는 딱히 정형화된 기준이 없다. 아래에 정리할 해쉬 함수 파트는 3가지 조건 : simplicity, speed, strength 에 초점을 맞출 것이다.
단순성과 속도는 쉽게 측정이 가능하나 strength는 좀 더 애매한 개념이다. SHA-1 같은 cryptographic 해쉬 함수는 상대적으로 느슨한 strength가 필요하나 느린 속도나 복잡한 구조는 상당히 불만족스럽다. 사실 crytographic 해쉬 함수도 악의 있는 공격자에 대한 보호 장치를 제공하지 않아, 특정 해쉬 함수를 쓰기 보다 universal 해쉬 함수가 사용되어지는 경우도 있다.(Universal 해쉬 함수는 공격자에 의해 최악의 성능으로 빠질 수 없도록, 충돌이 너무 자주 일어나지 않도록 보장하는 해쉬 함수를 얘기한다)
표준 방식은 없지만, 대개 해쉬 함수가 avalanche effect를 낼 수 있는지 여부로 해쉬 함수의 strength를 측정한다.(avalanche(눈사태) effect : 입력 데이터를 살짝만 바꿔(ex. flipping single bit) 출력 데이터가 상당히 바뀌는 효과(ex. halfs the output bits flipping))
다행히 위의 3가지 조건을 만족시키는 좋은 해쉬 함수들이 나와 있으며 Jenkins의 One-at-a-time 해쉬 함수가 대표적인 예라 할 수 있다. 32/64비트 int형의 괜찮은 해쉬 함수를 첨부한다. ---> int_hash_func.txt
해쉬 함수를 작성하는 방법에 따라 종류를 분류해보면 분할, 폴딩, 중간-제곱 함수, 추출, 기수 변환 등이 있으며 일반적으로 해쉬 테이블의 크기가 소수(prime number)일 때 성능이 좋아진다.
3. 충돌 해결
두 개의 키가 같은 인덱스로 해싱되면 같은 곳에 저장될 수 없다. 따라서 해싱된 인덱스에 이미 다른 값이 들어 있다면, 새 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있는 것이다. 100만개의 크기를 가지는 해쉬 테이블에 뛰어난 해쉬 함수로 가지고 있다고 해도, 대략 2500개의 레코드가 찼을 때 충돌이 발생활 확률은 95%에 이른다고 한다.
따라서 충돌 해결은 필수이며 가장 널리 쓰이는 chaining 방식과 open addressing 방식에 대해 알아보자.
1) Chaining
모든 bucket을 연결 리스트로 만들어 충돌이 발생하면 해당 bucket의 list에 추가하는 방식이다. 위 그림에서 보듯이, Smith와 Dee의 해쉬값이 873으로 동일하게 나왔으므로 Smith->Dee의 연결 리스트 형식으로 삽입하는 것이다.
Chaining 방식은 open-addressing 방식에 비해 크게 두 가지 이점을 가진다.
1. 삭제 작업이 간단하다.
2. 모든 버켓이 사용중이더라도 성능 저하가 더디게 나타나므로 open-addressing 방식에 비해 테이블 확장을 상당히 늦출 수 있다.
실제로 많은 chaining 해쉬 테이블에서 확장이 전혀 필요하지 않을 수 있는데, 테이블이 채워지는 것에 비례, 성능 저하가 linear하게 발생하기 때문이다. 예를 들어, chaining 해쉬 테이블에 적정 크기보다 2배의 데이터가 삽입되어도 2배의 속도 저하가 있을 뿐이다.
연결 리스트를 사용하는 chaining 해쉬 테이블은 연결 리스트의 단점도 그래도 물려받아, 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 되고 traverse의 캐쉬 효율도 좋지 않다. 대체 자료구조로서 최악의 경우에 O(n)이 아닌 O(log n)의 검색 복잡도를 보장하는 self-balancing tree를 고려해 볼 필요도 있다.
그러나 해쉬 테이블이 꽉 찰 정도로 운영되거나 상당히 높은 확률로 충돌이 발생하지 않는다면(저렇게 되지 않도록 하는 것이 가장 좋다), 통상적으로 리스트의 길이는 대부분 상당히 짧으며 모든 버켓이 2개 이상의 개체를 가지지도 않기 때문에 연결 리스트를 이용한 chained 해쉬 테이블로도 충분히 효과적이다.
그리고 데이터의 크기가 작을 때는 space 오버헤드를 줄이고 캐쉬 효율을 높이기 위해 연결 리스트 대신 dynamic array를 쓸 수도 있다.
2) Open-addressing
Open-addressing 해쉬 테이블은 배열 내에 데이터를 바로 저장할 수 있다.
충돌은 탐사(probing) 방식으로 해결하며 다음과 같은 잘 알려진 probe sequence들이 있다.
1. Linear probing : 순차적으로 탐색하며 비어있는 버켓을 찾을 때까지 계속 진행된다. 최악의 경우, 탐색을 시작한 위치까지 돌아오게 되어 종료(모든 버켓 순회)하게 된다. 캐쉬의 효율은 높으나 데이터의 클러스터링에 가장 취약한 단점이 있다.
2. Quadratic probing : 2차 함수를 이용해 탐색할 위치는 찾는다. 캐쉬의 효율과 클러스터링에 강한 능력에서 linear probing과 double hashing probing의 중간 정도 능력을 가진다.
3. Double hashing probing : 하나의 해쉬 함수에 의해 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당하는 방법이다. 캐쉬 효율은 3가지 방식 중 가장 좋지 않지만, 클러스터링에 거의 영향을 받지 않는다. 또한 가장 많은 연산량을 요구한다.
탐사 방식에 따라 open-addressing 해쉬의 성능이 달라지지만, 가장 치명적인 영향을 미치는 요소는 바로 해쉬 테이블의 load factor(전체 슬롯에서 사용중인 슬롯 비율)이다. Load factor가 100%로 증가할수록 데이터를 찾거나 삽입하기 위해 필요한 탐사 횟수는 비약적으로(dramatically) 증가한다. 일단 테이블이 꽉 차게 되면 probing이 실패하여 끝나버리기도 한다. 아래 표는 load factor에 따른 평균 성공 탐색수와 실패수이다.
위 표와 같이 아무리 좋은 해쉬 함수를 쓰더라도 일반적으로 load factor는 80%로 제한된다.(자바에서의 Hashmap은 기본 load factor threshold가 75%이다) 클러스터링에 가장 취약한 linear probing 방식이 load factor가 높을수록 가장 급격하게 성능 저하가 발생하는 것을 확인할 수 있다. 따라서 load factor가 임계점을 넘어 큰 경우의 성능은
double hashing > quadratic > linear 의 순서다.
물론 질 낮은 해쉬 함수는 엄청난 클러스터링을 유발함으로써 아주 낮은 load factor에도 해쉬 테이블의 성능을 상당히 낮아지게 한다. 어떤 문제가 해쉬 함수의 클러스터링을 유발하는지 알기는 쉽지 않아도, 해쉬 함수가 심각한 클러스터링을 유발하게 하는 것은 상당히 쉽다. 그냥 잘 만들어진, 그리고 많은 사람들에 의해 충분히 검증된 공개된 함수들을 가져다 쓰자 :-)
3) Chaining vs Open-addressing
Chained 해쉬 테이블은 open-addressing에 비해 다음과 같은 장점을 가진다.
1. 효과적으로 구현하기 간단하고 기본적인 자료구조 정도만 요구된다.
2. 해쉬 함수를 구현(선택)하는 관점에서 볼 때, chained 해쉬 테이블은 클러스터링에 거의 영향을 받지 않아 충돌의 최소화만 중점적으로 살펴보면 된다. 반면에 open-addressing 방식은 클러스터링까지 피해야 하므로 해쉬 함수의 성능에 지대한 영향을 받아 해쉬 함수를 구현(선택)하기가 쉽지 않다.
3. 테이블이 채워져도 성능 저하가 linear하게 발생한다. 비록 테이블이 채워질 수록 chain은 늘어나겠지만(리스트의 길이가 길어지겠지만) near-filled 상태의 open-addressing 방식에서 발생하는 급작스런 lookup 시간의 증가는 발생하지 않는다. (아래 그림을 보자)
4. 데이터의 크기가 대략 5 words and more 이라면, open-addressing 방식보다 적은 메모리를 사용한다.
5. 테이블의 데이터가 산재해 있다면(아주 큰 배열에서 빈 공간이 많은), chained 해쉬 테이블은 연결 리스트 등 테이블 외 별도의 외부 저장 공간에 동적으로 할당하여 사용함으로써 2 ~ 4 words의 작은 데이터라도 미리 공간을 잡아놓고 사용하는 open-addressing 방식보다 적은 메모리를 사용한다.
작은 크기의 데이터에 대해(a few words or less) open-addressing은 chaining에 비해 다음과 같은 장점을 가진다.
1. Open-Addressing 방식은 어떠한 포인터도 저장할 필요가 없고 테이블 외부에 어떠한 추가적인 저장 공간이 필요 없으므로 chaining 방식보다 메모리 효율이 높다.
2. 삽입시 메모리 할당 오버헤드가 없으며, 메모리 할당자가 없이도 구현이 가능하다.
3. 외부에 별도 공간을 필요로 하지 않기 때문에 chaining의 연결 리스트 같은 외부 공간에 필요한 추가적인 작업이 요구되지 않는다. 또한 (특히 linear probing에서) chaining보다 뛰어난 locality of reference(하나의 자원에 여러 번 접근하는 process)를 가진다. 데이터의 크기가 작다면, 특히 lookup에서, 이러한 특성들로 인해 chaining보다 성능이 좋을 수 있는 것이다.
4. 포인터를 사용하지 않음으로써 serialization이 용이하다.
반면에 open-addressing 방식은 큰 데이터를 다뤄야 할 때는 좋지 않은 선택인데, 데이터들이 캐쉬 라인을 채워버릴 것이며(캐쉬의 이득이 없어짐) 많은 공간이 (크기가 큰) 빈 슬롯들에 의해 낭비될 것이다.
정리하자면 open-addressing 방식은 테이블에 모두 저장될 수 있고 캐쉬 라인에 적합할 수 있을 정도로 데이터의 크기가 작을수록 성능이 더 좋아진다. 테이블의 높은 load factor가 예상되거나, 데이터가 크거나, 데이터의 길이가 가변일 때 chained 해쉬 테이블은 open-addressing 방식보다 적어도 동등하거나 훨씬 더 뛰어난 성능을 보인다.
4) Coleasced hashing
Chaining과 open-addressing을 혼합한 방식이며, 테이블 내의 버켓들끼리 서로 chain 링크를 가지게 한다.(Chained 방식은 각 버켓들 마다 고유의 chain 링크를 갖는다)
Open-addressing 처럼, chaining에 비해 storage usage and cache에서 우위를 보인다.
Chaining 처럼, 클러스터링에 거의 영향을 받지 않으며 실제로 테이블이 높은 밀도로 효과적으로 채워질 수 있다.
하지만 chaining과 다르게 버켓끼리 chain 링크를 거는 방식이므로 테이블 슬롯보다 많은 수의 데이터를 저장할 수 없다.
4. Table resizing
성능이 좋은 해쉬 함수를 사용하면 일반적으로 전체 슬롯의 70~80%가 채워져도 해쉬 테이블의 성능은 유지된다. 이 상태에서 더 많은 데이터가 추가되면, 충돌 해결 메커니즘에 따라 gradually or dramatically 하게 성능 저하가 발생한다. 이를 피하기 위해 load factor가 특정 임계점을 돌파하면 더 큰 테이블을 새로 만들어 데이터를 모두 옮기는 방법이 있다.
테이블 확장은 상당히 비용이 많이 드는 작업이며, 확장의 필요성은 해쉬 테이블의 단점 중 하나이다. 아주 무식하게 데이터가 하나씩 삽입될 때마다 매번 테이블을 늘어난 크기만큼 확장시킨다고 가정하면, 성능이 기하급수적으로 떨어질 것이며 더 이상 사용하기 힘든 해쉬 테이블이 될 것이다. 하지만 특정 퍼센트(예를 들어 10%, 100%)로 확장을 한다고 하면, 확장이 자주 발생하지 않아 lookup에 발생하는 평균적인 시간이 O(1)으로 되는 amortized(평소엔 좋지만 최악의 상황도 있는) 복잡도를 갖게 된다.
반면에 특히 real-time 시스템 같은 시스템에서는 테이블을 확장시키는 발생하는 비용을 감당하지 못할 수 있다. 이를 간단하게 해결하려면, 삽입될 데이터의 수보다 아주 큰 테이블을 만들거나 삽입 자체를 너무 많이 못하게 금지시키면 된다. 또 다른 방법으로 유용하지만 more memory-intensive인 기술은 다음과 같이 점진적으로 확장하는 방식이다.
1. 새 해쉬 테이블을 할당하지만 이전 해쉬 테이블을 삭제하지 않고, lookup 과정에서 두 테이블 모두 체크한다.
2. 데이터가 삽입될 때마다 새 테이블에 저장하고 특정 k 만큼 이전 테이블에서 새 테이블로 데이터를 이전한다.
3. k 만큼 데이터를 옮기다가 이전 테이블에 저장된 데이터가 없으면 이전 테이블을 free 한다.
Linear hashing은 incremental 해쉬 테이블 확장을 가능하게 하는 해쉬 테이블 알고리즘이다. 하나의 해쉬 테이블로 구현되지만, 두 개의 유효한 lookup 함수를 가진다.
아무리 훌륭한 방법을 고안, 구현하더라도 확장은 분명 해쉬 테이블의 심각한 성능 저하를 초래할 것이다. 가급적 확장이 일어나지 않도록 해쉬 테이블을 설계하고, 필요하다면 load factor가 일정 이상 늘어나지 않도록 테이블의 데이터 수를 제한하는 것도 확장하는 것보다는 낫다고 생각한다.
5. 해쉬의 단점
해쉬 테이블은 데이터를 pseudo-random 위치에 저장하기 때문에, 데이터를 정렬된 순서로 접근하는 것에 엄청난 비용이 발생한다. Self-balancing binary tree 같은 다른 자료구조에서는 일반적으로 lookup 시간이 O(log n)으로 느리고 구현도 더 복잡하지만 항상 데이터가 정렬되어 있다. 그리고 traverse 능력도 현저히 떨어지는데, 데이터가 산재해 있을 확률이 높은 해쉬 테이블의 특성상 빈 슬롯도 모두 체크하면서 순회를 해야 하기 때문이다.
해쉬 테이블은 일반적으로 locality-of-reference가 취약한데 데이터의 접근 패턴이 기본적으로 해쉬값을 이용한 jump around 방식이기 때문이며, 이는 프로세서의 캐쉬 미스를 발생(cause long delay)시킨다. 데이터의 수가 적고 key type이 integer 처럼 비교하기에 비용이 적게 든다면, linear search를 하는 배열 같은 간단한 자료구조에서 lookup에 더 나은 성능을 보인다.(일반적으로 hash는 개체수가 적을 때 성능이 떨어진다)
또한 해쉬 테이블은 구현 및 사용이 좀 더 어렵고 문제를 수반하기 쉽상이다. 모든 key type에 대해 강력한 해쉬 함수를 요구하는데, 다른 자료 구조의 간단한 비교 함수에 비해 설계하기도 구현하기도 디버그하기도 쉽지 않다. 특히 open-addressing 방식에서는 질 낮은 해쉬 함수를 만들기가 꽤나 쉽다.
6. 결론
하지만 최근 Java 등에서 map이 hashmap으로 대체되는 등, 검색이 주요 동작인 자료구조의 핵심이 되고 있다. 트리의 높이에 탐색 시간이 비례하는 map에 비해 평균적으로 O(1)의 탐색 시간을 보장하는 hashmap이 훨씬 좋음은 두 번 말해 입 아플 정도다.
Hash는 구현하기 어려운 자료구조가 아니나, 아름답게 구현하기는 무척 어려운 편이다. 뛰어난 해쉬 함수를 구현하거나 찾고 원만한 충돌 해결 알고리즘을 사용할 수 있다면 hash는 반드시 강력한 도구가 될 것이다.
