개념
맵을 구현하는 가장 효율적인 방법 중 하나는 해시 테이블을 사용하는 것이다.해시 테이블은 맵 연산을 평균 O(1) 시간에 실행할 수 있다. 해시 테이블은 버켓(bucket) 배열과 해시 함수로 이루어져 있다.
버켓(Bucket)
배열 해시 테이블을 위한 버켓 배열은 크기가 N인 배열 A이다. 여기서 A의 각 셀을 "버켓"으로 생각하고(즉, 키-원소 쌍들을 저장하는 컨테이너) 정수 N은 배열의 용량(capacity)이다. 만약 키들이 [0, N-1] 범위에 잘 분포된 정수라면, 버켓 배열만으로 충분하다. 키 k를 갖는 원소 e는 단순히 버켓 A[k]에 삽입된다.
만약 키가 [0, N-1] 범위에 있는 유일한 정수라면, 각 버켓은 최대 하나의 엔트리를 저장한다. 따라서 버켓 배열의 검색, 삽입, 그리고 삭제는 최악의 경우 O(1)의 시간이 소요된다. 단, 버켓 배열은 O(N)의 공간을 사용하므로 N이 실제 맵에 존재하는 엔트리 개수 n에 비해 매우 크면, 공간이 낭비된다. 또한 버켓 배열에서는 키들이 [0, N-1] 범위에 있는 유일한 정수여야 하는데, 이것은 흔하지 않은 경우이다. 이러한 단점 때문에, 키를 [0, N-1] 범위 안의 정수로 변환하는 좋은 매핑과 함께 버켓 배열을 사용한다.
해시 함수(Hash Function)
해시 테이블 구조의 두 번쨰 부분은 해시 함수라 불리는 h 함수이다. 이 함수는 맵의 각 키 k를 [0, N-1] 범위의 정수로 변환하는데, 여기서 N은 이 테이블을 위한 버켓 배열의 용량이다. 이러한 해시 함수가 있으면, 임의의 키에 대하여 버켓 배열 방법을 적용할 수 있다. 이 방법은 키 k 대신 해시 함수값 h(k)를 버켓 배열 A의 인덱스로 사용하는 것이다. 대부분의 경우 키 값 k를 직접 버켓 배열의 인덱스로 사용하는 것은 부적절하다.
만약 두 개 이상의 키들이 같은 해시값을 가지면, 두 개 이상의 원소들이 A의 같은 버켓에 매핑될 수 있다. 이러한 경우를 충돌(collision)이 발생했다고 한다. A의 각 버켓이 한 개의 원소만 저장할 수 있다면 두 개 이상의 원소들은 한 버켓에 대응시킬 수 없게 되어, 충돌의 문제가 발생한다. 충돌을 해결하는 방법도 있지만, 가장 좋은 전략은 충돌을 피하는 것이다. 따라서 해시 함수는 맵 내의 키들을 매핑하는 과정에서 충돌을 가능하다면 최소화하는 것이 좋다. 실용적으로는 해시 함수의 계산이 빠르고 쉬운 것이 좋다.
해시 함수 h(k)의 계산은 두 단계로 나뉜다. 해시 코드(hash code)라 불리는 키 k를 정수로 바꾸는 과정과 압축 함수(compression function)라 불리는 해시 코드를 버켓 배열의 인덱스 범위로 매핑하는 과정이다.
해시 코드(Hash Code)
해시 함수의 첫 단계는 맵의 임의의 키 k에 대해 주어진 정수값을 할당하는 것이다. 키 k에게 할당된 정수 값을 k에 대한 해시 코드라 한다. 이 정수 값은 [0, N-1] 범위에 있지 않아도 되며 음수 값일 수도 있지만, 키들에 주어진 해시 코드들은 가능하면 충돌을 피하는 것이 바람직하다. 만약 키들의 해시 코드가 충돌하면, 압축 함수도 충돌을 피할 수 없다. 모든 키에 대한 일관성을 위해, 키 k에 주어진 해시 코드는 k와 같은 키의 해시 코드와 같아야 한다.
해시 코드를 만드는 방법에는 정수로 형변환, 다항식(Polynimial) 해시 코드, 원형 이동(Cyclic Shift) 해시 코드 방법이 있다.
압축 함수(Compression Function)
키에 대한 해시 코드의 범위가 보통 버켓 배열 A의 인덱스 범위를 벗어나기 때문에, 키 k에 대한 해시 코드를 버켓 배열에 바로 사용할 수 없다. 따라서 객체 k에 대한 정수 해시 코드를 결정한 다음에도 그 정수를 범위 [0, N-1]으로 매핑하는 문제가 남아 있다. 이러한 압축 단계는 해시 함수가 수행하는 두 번째 과정이다.
압축 함수에는 나눗셈(Division) 방법과 MAD(multiply add and divide) 방법이 있다.
충돌-처리 기법(Collision-Handling Schemes)
해시 테이블의 핵심은 버켓 배열 A와 해시 함수 h를 사용하여 맵의 각 엔트리 (k, v)를 "버켓" A[h(k)]에 저장하는 것이다. 그러나 이러한 간단한 아이디어는 두 개의 키 k1과 k2가 같은 해시값을 가지면 문제가 생긴다. 이러한 충돌은 함수 find(k), insert(pair(k, v)), erase(k)의 구현도 복잡하게 만든다.
충돌-처리 기법에는 별도 체이닝(Separate Chaining), 오픈 어드레싱(Open Addressing)(선형 검사(Linear Probing), 제곱 검사(Quadratic Probing), 이중 해싱(Double Hashing))의 방법이 있다.
오픈 어드레싱 방법들은 별도 체이닝 방법보다 공간은 절약되지만 속도 면에서 반드시 빠르지는 않다. 만약 메모리 공간이 중요한 문제가 아니라면 별도 체이닝 방법이 적절하다.
댓글