해시 테이블

해시 테이블
종류	정렬되지 않은 연관 배열
발명일	1953
점근표기법으로 된 시간복잡도 기능 평균 최악의 경우 탐색 Θ(1) O(n) 삽입 Θ(1) O(n) 삭제 Θ(1) O(n) 공간 복잡도 공간 Θ(n) O(n)

해시 테이블로 구현된 작은 전화번호부

컴퓨터 과학에서 해시 테이블(hash table)은 딕셔너리(dictionary) 또는 단순히 맵(map)이라고도 불리는 연관 배열을 구현하는 자료 구조이다. 연관 배열은 유일 키를 값에 매핑하는 추상 자료형이다. 해시 테이블은 해시 함수를 사용하여 버킷 또는 슬롯의 배열로 인덱스(해시 코드라고도 함)를 계산하고, 여기서 원하는 값을 찾을 수 있다. 조회 중에 키는 해시되고 결과 해시는 해당 값이 저장된 위치를 나타낸다. 해시 테이블로 구현된 맵을 해시 맵이라고 한다.

대부분의 해시 테이블 설계는 불완벽 해시 함수를 사용한다. 따라서 해시 함수가 하나 이상의 키에 대해 동일한 인덱스를 생성하는 해시 충돌은 일반적으로 어떤 방식으로든 처리되어야 한다. 해시 충돌을 처리하는 일반적인 전략에는 연결 리스트를 사용하여 동일한 슬롯에 여러 요소를 저장하는 체이닝과 프로빙 시퀀스에 따라 다음 사용 가능한 슬롯을 검색하는 개방 주소 지정이 있다.

잘 구성된 해시 테이블에서 각 조회의 평균 시간 복잡도는 테이블에 저장된 요소 수와 독립적이다. 많은 해시 테이블 설계는 키-값 쌍의 임의 삽입 및 삭제를 허용하며, 작업당 분할 상환 상수에 평균 비용을 가진다.

해싱은 공간-시간 트레이드오프의 예시이다. 메모리가 무한하다면, 전체 키를 직접 인덱스로 사용하여 단일 메모리 접근으로 값을 찾을 수 있다. 반대로, 무한한 시간을 사용할 수 있다면, 값은 키에 관계없이 저장될 수 있으며, 요소를 검색하기 위해 이진 검색 또는 선형 검색이 사용될 수 있다.

많은 상황에서 해시 테이블은 탐색 트리 또는 다른 테이블 조회 구조보다 평균적으로 더 효율적인 것으로 밝혀졌다. 해시 테이블은 빠른 평균 사례 성능 때문에 데이터베이스 인덱싱, 캐싱 및 연관 배열 구현과 같은 작업에 현대 소프트웨어 시스템에서 널리 사용된다. 이러한 이유로, 특히 연관 배열, 데이터베이스 인덱싱, 캐시, 집합과 같은 다양한 종류의 소프트웨어에서 널리 사용된다. 많은 프로그래밍 언어는 프로그래머로부터 해싱의 복잡성을 추상화하는 Python의 딕셔너리, Java의 HashMap, C++의 unordered_map과 같은 내장 해시 테이블 구조를 제공한다.

역사

해싱의 개념은 여러 곳에서 독립적으로 발생했다. 1953년 1월, 한스 페터 룬은 체이닝을 사용하는 내부 IBM 메모랜덤을 작성했다. 개방 주소 지정의 첫 번째 예시는 룬의 메모랜덤을 기반으로 A. D. 린에 의해 제안되었다. 거의 같은 시기에 진 암달, 일레인 M. 맥그로, 너새니얼 로체스터, 아서 새뮤얼은 IBM 리서치에서 IBM 701 어셈블러에 해싱을 구현했다. 선형 프로빙을 사용하는 개방 주소 지정은 암달에게 공로가 있지만, 안드레이 예르쇼프도 독립적으로 같은 아이디어를 가지고 있었다. "개방 주소 지정"이라는 용어는 W. 웨슬리 피터슨이 대용량 파일 검색 문제에 대해 논의한 기사에서 만들어졌다.

체이닝을 이용한 해싱에 대한 첫 번째 출판물은 프라임 모듈로 나머지를 해시 함수로 사용하는 아이디어를 논의한 아놀드 듀미에게 공로가 있다. "해싱"이라는 단어는 로버트 모리스의 기사에서 처음 출판되었다. 선형 프로빙의 이론적 분석은 원래 콘하임과 바이스가 제출했다.

개요

연관 배열은 (키, 값) 쌍의 집합을 저장하고 삽입, 삭제 및 조회(검색)를 허용하며, 유일 키의 제약이 있다. 연관 배열의 해시 테이블 구현에서 길이 $m$인 배열 $A$는 $n$개의 요소로 부분적으로 채워지며, 여기서 $m\geq n$이다. 키 $x$는 해시 함수 $h$를 사용하여 해시되어 해시 테이블 내의 인덱스 위치 $A[h(x)]$를 계산하며, 여기서 $h(x)<m$이다. 해시 테이블의 효율성은 로드 팩터에 따라 달라지는데, 이는 저장된 요소 수와 사용 가능한 슬롯 수의 비율로 정의되며, 로드 팩터가 낮을수록 일반적으로 작업이 빨라진다. 이 인덱스에 키와 그에 연결된 값이 모두 저장된다. 값을 키와 함께 저장하면 조회 시 인덱스의 키를 확인하여 충돌이 발생하더라도 올바른 값을 검색할 수 있다. 합리적인 가정 하에 해시 테이블은 자가 균형 이진 탐색 트리에 비해 검색, 삭제 및 삽입 작업에 대한 더 나은 시간 복잡도 한계를 가진다.

해시 테이블은 또한 각 키에 대해 저장된 값을 생략하고 키의 존재 여부만 추적하여 집합을 구현하는 데 일반적으로 사용된다.

로드 팩터

로드 팩터 $\alpha$는 해시 테이블의 중요한 통계이며 다음과 같이 정의된다. $${\text{load factor}}\ (\alpha )={\frac {n}{m}},$$ 여기서

• $n$은 해시 테이블에 채워진 엔트리의 수이다.
• $m$은 버킷의 수이다.

해시 테이블의 성능은 로드 팩터 $\alpha$에 비례하여 저하된다. $m$과 $n$이 큰 극한에서는 이상적인 무작위 해시 함수에 대해 각 버킷은 통계적으로 기대값 $\lambda =\alpha$를 가진 푸아송 분포를 따른다.

소프트웨어는 일반적으로 로드 팩터 $\alpha$가 특정 상수 $\alpha _{\max }$ 미만으로 유지되도록 보장한다. 이는 좋은 성능을 유지하는 데 도움이 된다. 따라서 일반적인 접근 방식은 로드 팩터 $\alpha$가 $\alpha _{\max }$에 도달할 때마다 해시 테이블의 크기를 조정하거나 "재해싱"하는 것이다. 마찬가지로 로드 팩터가 $\alpha _{\max }/4$ 아래로 떨어지면 테이블 크기를 조정할 수도 있다.

분리 체이닝의 로드 팩터

분리 체이닝 해시 테이블에서 버킷 배열의 각 슬롯은 데이터의 연결 리스트 또는 배열에 대한 포인터를 저장한다.

분리 체이닝 해시 테이블은 로드 팩터가 증가함에 따라 성능이 점진적으로 저하되며, 재조정이 절대적으로 필요한 고정 지점은 없다.

분리 체이닝에서 최상의 성능을 제공하는 $\alpha _{\max }$ 값은 일반적으로 1에서 3 사이이다.

개방 주소 지정의 로드 팩터

개방 주소 지정에서는 버킷 배열의 각 슬롯이 정확히 하나의 항목을 보유한다. 따라서 개방 주소 지정 해시 테이블은 로드 팩터가 1보다 클 수 없다.

개방 주소 지정의 성능은 로드 팩터가 1에 가까워지면 매우 나빠진다.

따라서 개방 주소 지정을 사용하는 해시 테이블은 로드 팩터 $\alpha$가 1에 가까워지면 크기를 조정하거나 재해싱해야 한다.

개방 주소 지정에서 허용 가능한 최대 로드 팩터 $\alpha _{\max }$는 약 0.6에서 0.75 범위여야 한다.

해시 함수

해시 함수 $h:U\rightarrow \{0,...,m-1\}$는 키의 유니버스 $U$를 테이블 내의 인덱스 또는 슬롯에 매핑한다. 즉, $x\in U$에 대해 $h(x)\in \{0,...,m-1\}$이다. 해시 함수의 일반적인 구현은 테이블의 모든 요소가 워드 크기 내에 $u$의 비트 길이가 제한되는 유니버스 $U=\{0,...,u-1\}$에서 파생된다는 정수 유니버스 가정에 기반한다.

해시 함수 $h$는 주어진 집합 $S$에 대해 단사적이면, 즉 $S$의 각 요소 $x$가 ${0,...,m-1}$에서 다른 값으로 매핑되면 완벽하다고 한다. 모든 키를 미리 알고 있다면 완벽 해시 함수를 만들 수 있다.

정수 유니버스 가정

정수 유니버스 가정에 사용되는 해싱 방식은 나눗셈 해싱, 곱셈 해싱, 유니버설 해싱, 동적 완벽 해싱 및 정적 완벽 해싱을 포함한다. 그러나 나눗셈 해싱은 일반적으로 사용되는 방식이다.

나눗셈 해싱

나눗셈 해싱의 방식은 다음과 같다. $$h(x)\ =\ x\,{\bmod {\,}}m,$$ 여기서 $h(x)$는 $x\in S$의 해시 값이고 $m$은 테이블의 크기이다.

곱셈 해싱

곱셈 해싱의 방식은 다음과 같다. $$h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor$$ 여기서 $A$는 정수가 아닌 실수 상수이고 $m$은 테이블의 크기이다. 곱셈 해싱의 장점은 $m$이 중요하지 않다는 것이다. 어떤 $A$ 값도 해시 함수를 생성하지만, 도널드 커누스는 황금비를 사용할 것을 제안한다.

문자열 해싱

일반적으로 문자열이 해시 함수의 키로 사용된다. 스트롭스트루프는 처음에 0인 부호 없는 정수를 반복적으로 1비트 왼쪽 시프트한 다음 다음 문자의 정수 값과 XOR 연산하는 간단한 해시 함수를 설명한다. 이 해시 값은 테이블 크기의 모듈로 취해진다. 왼쪽 시프트가 순환 시프트가 아닌 경우 문자열 길이는 부호 없는 정수의 비트 크기보다 최소 8비트 작아야 한다. 문자열을 정수로 해시하는 또 다른 일반적인 방법은 다항식 롤링 해시 함수를 사용하는 것이다.

해시 함수 선택

해시 값의 균등 분포는 해시 함수의 근본적인 요구 사항이다. 균등하지 않은 분포는 충돌 횟수와 이를 해결하는 비용을 증가시킨다. 균등성은 설계상 보장하기 어려운 경우가 있지만, 피어슨 카이제곱 검정과 같은 통계적 테스트를 사용하여 경험적으로 평가할 수 있다.

분포는 애플리케이션에서 발생하는 테이블 크기에 대해서만 균일해야 한다. 특히 테이블 크기를 정확히 두 배로 늘리고 반으로 줄이는 동적 크기 조정을 사용하는 경우 해시 함수는 크기가 2의 거듭제곱일 때만 균일해야 한다. 여기서 인덱스는 해시 함수의 일부 비트 범위로 계산될 수 있다. 반면에 일부 해싱 알고리즘은 크기가 소수인 것을 선호한다.

개방 주소 지정 방식의 경우 해시 함수는 클러스터링도 피해야 한다. 클러스터링은 둘 이상의 키를 연속적인 슬롯에 매핑하는 것이다. 이러한 클러스터링은 로드 팩터가 낮고 충돌이 드물더라도 조회 비용을 급등시킬 수 있다. 널리 사용되는 곱셈 해시(multiplicative hash)는 특히 클러스터링 동작이 좋지 않은 것으로 알려져 있다.

K-독립 해싱은 주어진 해시 테이블 유형에 대해 특정 해시 함수에 나쁜 키 집합이 없음을 증명하는 방법을 제공한다. 선형 프로빙 및 쿠쿠 해싱과 같은 충돌 해결 방식에 대해 K-독립성 결과가 다수 알려져 있다. K-독립성은 해시 함수가 작동함을 증명할 수 있으므로, 가장 빠른 해시 함수를 찾는 데 집중할 수 있다.

충돌 해결

해싱을 사용하는 검색 알고리즘은 두 부분으로 구성된다. 첫 번째 부분은 검색 키를 배열 인덱스로 변환하는 해시 함수를 계산하는 것이다. 이상적인 경우는 두 검색 키가 동일한 배열 인덱스로 해시되지 않는 것이다. 그러나 이는 항상 그런 것은 아니며 보이지 않는 데이터에 대해 보장할 수 없다. 따라서 알고리즘의 두 번째 부분은 충돌 해결이다. 충돌 해결을 위한 두 가지 일반적인 방법은 분리 체이닝과 개방 주소 지정이다.

분리 체이닝

분리 체이닝으로 해결된 해시 충돌

버킷 배열의 헤드 레코드를 사용한 분리 체이닝으로 인한 해시 충돌

분리 체이닝에서는 각 검색 배열 인덱스에 대해 연결 리스트를 이름-값 쌍으로 구성하는 과정이 포함된다. 충돌된 항목은 단일 연결 리스트를 통해 함께 연결되며, 고유한 검색 키로 항목에 접근하기 위해 리스트를 순회할 수 있다. 연결 리스트를 사용한 체이닝을 통한 충돌 해결은 해시 테이블 구현의 일반적인 방법이다. $T$를 해시 테이블, $x$를 노드라고 하면, 작업은 다음과 같이 수행된다.

Chained-Hash-Insert(T, k)
  insert x at the head of linked list T[h(k)]

Chained-Hash-Search(T, k)
  search for an element with key k in linked list T[h(k)]

Chained-Hash-Delete(T, k)
  delete x from the linked list T[h(k)]

요소가 수치적으로든 사전적으로든 비교 가능하고 전순서를 유지하며 리스트에 삽입되면, 실패한 검색의 종료가 빨라진다.

분리 체이닝을 위한 다른 자료 구조

키가 정렬되어 있는 경우, 자가 균형 이진 탐색 트리와 같은 "자가 구성" 개념을 사용하는 것이 효율적일 수 있으며, 이를 통해 이론적 최악의 경우가 $O(\log {n})$로 줄어들 수 있지만, 추가적인 복잡성이 도입된다.

동적 완벽 해싱에서는 조회 복잡도를 최악의 경우에도 $O(1)$로 보장하기 위해 2단계 해시 테이블이 사용된다. 이 기술에서는 $k$개의 엔트리로 구성된 버킷이 $k^{2}$개의 슬롯을 가진 완벽 해시 테이블로 조직되어 상수 시간의 최악의 경우 조회 시간과 낮은 분할 상환 삽입 시간을 제공한다. 한 연구에 따르면 배열 기반 분리 체이닝은 부하가 높을 때 표준 연결 리스트 방법보다 97% 더 나은 성능을 보인다.

각 버킷에 퓨전 트리를 사용하는 것과 같은 기술은 높은 확률로 모든 연산에 대해 상수 시간을 제공한다.

캐싱 및 참조 국부성

분리 체이닝 구현의 연결 리스트는 공간 국부성—참조 국부성—으로 인해 캐시 인식적이지 않을 수 있다. 연결 리스트의 노드가 메모리에 흩어져 있으면 삽입 및 검색 중 리스트 순회가 CPU 캐시 비효율성을 초래할 수 있기 때문이다.

분리 체이닝을 통한 충돌 해결의 캐시 인식 변형에서는 연결 리스트나 자가 균형 이진 탐색 트리가 일반적으로 배포되는 대신 동적 배열이 사용된다. 이 배열은 캐시 친화적인 것으로 밝혀졌다. 이는 배열의 연속 할당 패턴이 하드웨어 캐시 선인출기—예를 들어 변환 색인 버퍼—에 의해 활용될 수 있어 접근 시간과 메모리 소비가 줄어들기 때문이다.

개방 주소 지정

 이 부분의 본문은 개방 주소 지정입니다.

선형 탐사(간격=1)를 사용한 개방 주소 지정으로 해결된 해시 충돌. "테드 베이커"는 고유한 해시 값을 가지고 있지만, 이전에 "존 스미스"와 충돌했던 "샌드라 디"와 충돌했다는 점에 유의한다.

이 그래프는 체이닝과 선형 탐사를 사용하는 대규모 해시 테이블(캐시 크기를 훨씬 초과)에서 요소를 찾는 데 필요한 평균 CPU 캐시 미스 수를 비교한다. 선형 탐사는 더 나은 참조 국부성으로 인해 더 나은 성능을 보이지만, 테이블이 가득 찰수록 성능이 급격히 저하된다.

개방 주소 지정은 모든 엔트리 레코드가 버킷 배열 자체에 저장되고 해시 해결이 프로빙을 통해 수행되는 또 다른 충돌 해결 기술이다. 새 엔트리를 삽입해야 할 때, 해시된 슬롯부터 시작하여 일부 탐사 시퀀스에 따라 버킷을 검사하여 비어 있는 슬롯을 찾는다. 엔트리를 검색할 때, 동일한 시퀀스로 버킷을 스캔하여 대상 레코드를 찾거나 사용되지 않는 배열 슬롯을 찾을 때까지 스캔하며, 이는 검색 실패를 나타낸다.

잘 알려진 탐사 시퀀스는 다음과 같다.

• 선형 탐사, 탐사 간격이 고정되어 있다 (일반적으로 1).
• 제곱 탐사, 탐사 간격이 원래 해시 계산으로 주어진 값에 이차 다항식의 연속적인 출력을 더하여 증가된다.
• 이중 해시, 탐사 간격이 보조 해시 함수에 의해 계산된다.

개방 주소 지정의 성능은 로드 팩터 $\alpha$가 1에 가까워질 때 탐사 시퀀스가 증가하므로 분리 체이닝에 비해 느릴 수 있다. 테이블이 완전히 채워진 경우 로드 팩터가 1에 도달하면 탐사는 무한 루프로 이어진다. 선형 탐사의 평균 비용은 해시 함수가 요소를 테이블 전체에 균일하게 분산시켜 클러스터링을 피하는 능력에 달려 있다. 클러스터가 형성되면 검색 시간이 증가하기 때문이다.

캐싱 및 참조 국부성

슬롯이 연속적인 위치에 있기 때문에 선형 프로빙은 참조 국부성으로 인해 CPU 캐시를 더 잘 활용하여 메모리 레이턴시를 줄일 수 있다.

개방 주소 지정 기반의 다른 충돌 해결 기법

병합 해싱

 이 부분의 본문은 병합 해싱입니다.

병합 해싱은 테이블 내에서 버킷 또는 노드가 연결되는 분리 체이닝과 개방 주소 지정의 하이브리드이다. 이 알고리즘은 고정 메모리 할당에 이상적으로 적합하다. 병합 해싱에서 충돌은 해시 테이블에서 가장 큰 인덱스를 가진 빈 슬롯을 식별한 다음, 충돌하는 값을 해당 슬롯에 삽입하여 해결된다. 버킷은 또한 삽입된 노드의 슬롯에 연결되어 충돌하는 해시 주소를 포함한다.

쿠쿠 해싱

 이 부분의 본문은 쿠쿠 해싱입니다.

쿠쿠 해싱은 최악의 경우 $O(1)$ 조회 복잡도와 삽입에 대한 상수 분할 상환 시간을 보장하는 개방 주소 지정 충돌 해결 기술의 한 형태이다. 충돌은 각각 자체 해싱 함수를 가진 두 개의 해시 테이블을 유지함으로써 해결되며, 충돌된 슬롯은 주어진 항목으로 대체되고, 슬롯의 미리 점유된 요소는 다른 해시 테이블로 이동된다. 이 과정은 모든 키가 테이블의 빈 버킷에 자신만의 자리를 가질 때까지 계속된다. 만약 이 절차가 무한 루프에 들어가면(이는 임계 루프 카운터를 유지함으로써 식별된다), 두 해시 테이블 모두 새로운 해시 함수로 다시 해시되고 절차는 계속된다.

홉스카치 해싱

 이 부분의 본문은 홉스카치 해싱입니다.

홉스카치 해싱은 쿠쿠 해싱, 선형 탐사 및 버킷의 이웃 개념(주어진 점유된 버킷 주위의 후속 버킷, "가상" 버킷이라고도 함)을 통해 체이닝의 요소를 결합한 개방 주소 지정 기반 알고리즘이다. 이 알고리즘은 해시 테이블의 로드 팩터가 90%를 초과할 때 더 나은 성능을 제공하도록 설계되었으며, 병행 환경에서도 높은 처리량을 제공하여 크기 조정 가능한 병행 해시 테이블 구현에 매우 적합하다. 홉스카치 해싱의 이웃 특성은 주어진 이웃 내의 버킷에서 원하는 항목을 찾는 비용이 버킷 자체에서 찾는 비용과 매우 가깝다는 속성을 보장한다. 이 알고리즘은 다른 항목을 이동시키는 가능한 비용을 포함하여 항목을 이웃에 삽입하려고 시도한다.

해시 테이블 내의 각 버킷에는 H 비트 비트 배열인 추가 "홉 정보"가 포함되어 있으며, H - 1 엔트리 내에서 현재 가상 버킷에 원래 해시된 항목의 상대 거리를 나타낸다. 삽입될 키를 $k$, 키가 해시되는 버킷을 $Bk$라고 하면, 알고리즘의 이웃 속성을 보장하기 위해 삽입 절차에 여러 경우가 포함된다. 만약 $Bk$가 비어 있다면, 요소가 삽입되고 비트맵의 가장 왼쪽 비트가 1로 설정된다. 비어 있지 않다면, 테이블에서 빈 슬롯을 찾기 위해 선형 탐사가 사용되며, 버킷의 비트맵이 업데이트된 후 삽입이 이루어진다. 만약 빈 슬롯이 이웃 범위, 즉 H - 1 내에 없다면, 각 버킷의 이웃 불변 속성에 따라 후속 스왑 및 홉 정보 비트 배열 조작이 수행된다.

로빈 후드 해싱

로빈 후드 해싱은 개방 주소 지정 기반 충돌 해결 알고리즘이다. 충돌은 "홈 위치" 즉, 항목이 해시된 버킷에서 가장 멀리 떨어져 있거나 가장 긴 탐사 시퀀스 길이(PSL)를 가진 요소를 이동시키는 방식으로 해결된다. 이 이름은 부자에게서 훔쳐 가난한 자에게 주었던 전설적인 로빈 후드 의적의 이름을 따서 명명되었다.

로빈 후드 해싱은 이론적 검색 비용을 변경하지 않지만, 버킷에 있는 항목의 분포의 분산에 크게 영향을 미친다. 즉, 해시 테이블의 클러스터 형성을 처리한다. 로빈 후드 해싱을 사용하는 해시 테이블 내의 각 노드는 추가 PSL 값을 저장하도록 확장되어야 한다. 삽입될 키를 $x$, $x{.}{\text{psl}}$을 $x$의 (증가) PSL 길이, $T$를 해시 테이블, $j$를 인덱스라고 할 때, 삽입 절차는 다음과 같다.

• If $x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}$: 외부 탐사를 시도하지 않고 다음 버킷으로 이동한다.
• If $x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}$: 항목 $x$를 버킷 $j$에 삽입하고, $x$와 $T[j]$를 교환한다—이를 $x'$라고 하자. $(j+1)$번째 버킷에서 $x'$를 삽입하기 위한 탐사를 계속한다. 모든 요소가 삽입될 때까지 이 절차를 반복한다.

동적 크기 조정

반복된 삽입은 해시 테이블의 엔트리 수를 증가시키고, 결과적으로 로드 팩터를 증가시킨다. 조회 및 삽입 작업의 분할 상환 $O(1)$ 성능을 유지하기 위해 해시 테이블은 동적으로 크기가 조정되며, 테이블의 항목은 새 해시 테이블의 버킷으로 재해싱된다. 이는 다양한 테이블 크기가 모듈로 연산으로 인해 다른 해시 값을 초래하므로 항목을 단순히 복사할 수 없기 때문이다. 일부 요소를 삭제한 후 해시 테이블이 "너무 비어지면" 과도한 메모리 사용을 피하기 위해 크기 조정을 수행할 수 있다.

모든 엔트리를 이동하여 크기 조정

일반적으로 원래 해시 테이블 크기의 두 배인 새 해시 테이블이 사적으로 할당되고, 원래 해시 테이블의 모든 항목은 항목의 해시 값을 계산한 후 삽입 작업을 통해 새로 할당된 테이블로 이동된다. 재해싱은 간단하지만 계산 비용이 많이 든다.

일괄 재해싱의 대안

일부 해시 테이블 구현, 특히 실시간 시스템에서는 해시 테이블을 한 번에 모두 확장하는 비용을 지불할 수 없는데, 이는 시간 결정적인 작업을 방해할 수 있기 때문이다. 동적 크기 조정을 피할 수 없다면, 재해싱 중에 (일반적으로 새 테이블 크기의 50%에서) 저장 공간의 순간적인 증가를 피하고, 이전 해시 테이블의 대규모 메모리 블록 해제로 인한 메모리 단편화를 방지하여 힙 압축을 유발하는 솔루션은 점진적으로 크기 조정을 수행하는 것이다. 이런 경우 재해싱 작업은 이전 해시 테이블에 할당된 메모리 블록을 확장하여 해시 테이블의 버킷이 변경되지 않도록 점진적으로 수행된다. 분할 상환 재해싱의 일반적인 접근 방식은 두 개의 해시 함수 $h_{\text{old}}$와 $h_{\text{new}}$를 유지하는 것이다. 새 해시 함수에 따라 버킷 항목을 재해싱하는 과정은 클리닝이라고 불리며, $\mathrm {Add} (\mathrm {key} )$, $\mathrm {Get} (\mathrm {key} )$ 및 $\mathrm {Delete} (\mathrm {key} )$와 같은 작업을 커맨드 패턴을 통해 래퍼 $\mathrm {Lookup} (\mathrm {key} ,{\text{command}})$로 캡슐화하여 각 버킷의 요소가 재해싱되고 그 절차는 다음과 같이 진행된다.

• $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ 버킷을 청소한다.
• $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ 버킷을 청소한다.
• 명령이 실행된다.

선형 해싱

 이 부분의 본문은 선형 해싱입니다.

선형 해싱은 테이블의 동적 증가 또는 감소를 한 번에 하나의 버킷씩 가능하게 하는 해시 테이블의 구현이다.

성능

해시 테이블의 성능은 해시 테이블의 엔트리에 대해 준무작위 숫자($\sigma$)를 생성하는 해시 함수의 능력에 달려 있으며, 여기서 $K$, $n$ 및 $h(x)$는 키, 버킷의 수 및 해시 함수를 나타내어 $\sigma \ =\ h(K)\ \%\ n$이다. 만약 해시 함수가 다른 키($K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$)에 대해 동일한 $\sigma$를 생성하면 충돌이 발생하며, 이는 다양한 방식으로 처리된다. 해시 테이블에서 연산의 상수 시간 복잡도($O(1)$)는 해시 함수가 충돌하는 인덱스를 생성하지 않는다는 조건에 따라 가정된다. 따라서 해시 테이블의 성능은 선택된 해시 함수가 인덱스를 분산시키는 능력에 정비례한다. 그러나 이러한 해시 함수를 구성하는 것은 실질적으로 불가능하며, 따라서 구현은 더 높은 성능을 달성하기 위해 사례별 충돌 해결 기술에 의존한다.

해시 함수가 유니버스 요소를 균일하게 분포시키고, 테이블에 저장된 요소가 유니버스에서 무작위로 추출될 때 최상의 성능을 얻을 수 있다. 이 경우 체이닝을 사용한 해싱에서 성공적인 검색의 예상 시간은 ${\textstyle 1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)}$이고, 실패한 검색의 예상 시간은 ${\textstyle e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)}$이다.

응용 분야

연관 배열

 이 부분의 본문은 연관 배열입니다.

해시 테이블은 많은 유형의 인메모리 테이블을 구현하는 데 일반적으로 사용된다. 이들은 연관 배열을 구현하는 데 사용된다.

데이터베이스 인덱싱

해시 테이블은 디스크 기반 자료 구조 및 데이터베이스 인덱스(예: dbm 등)로도 사용될 수 있지만, 이러한 응용 분야에서는 B 트리가 더 널리 사용된다.

캐시

 이 부분의 본문은 캐시 (컴퓨팅)입니다.

해시 테이블은 캐시를 구현하는 데 사용될 수 있다. 캐시는 주로 느린 미디어에 저장된 데이터에 대한 접근 속도를 높이는 데 사용되는 보조 데이터 테이블이다. 이 응용 프로그램에서 해시 충돌은 충돌하는 두 엔트리 중 하나를 폐기함으로써 처리될 수 있다—일반적으로 테이블에 현재 저장된 오래된 항목을 지우고 새 항목으로 덮어쓰므로, 테이블의 모든 항목은 고유한 해시 값을 가진다.

집합

 이 부분의 본문은 집합 자료 구조입니다.

해시 테이블은 집합 자료 구조의 구현에 사용될 수 있으며, 이는 특정 순서 없이 고유한 값을 저장할 수 있다. 집합은 일반적으로 요소 검색보다는 컬렉션에 값의 멤버십을 테스트하는 데 사용된다.

전치 테이블

 이 부분의 본문은 전치 테이블입니다.

전치 테이블은 검색된 각 섹션에 대한 정보를 저장하는 복잡한 해시 테이블이다.

구현

많은 프로그래밍 언어는 내장 연관 배열 또는 표준 라이브러리 모듈 형태로 해시 테이블 기능을 제공한다.

• 자바스크립트에서 "객체"는 키-값 쌍(속성이라고 함)의 변경 가능한 컬렉션으로, 각 키는 문자열이거나 보장된 고유 "심볼"이다. 다른 값은 키로 사용될 때 먼저 문자열로 강제 변환된다. 일곱 가지 "원시" 데이터 유형 외에, 자바스크립트의 모든 값은 객체이다. ECMAScript 2015는 또한 임의의 값을 키로 허용하는 Map 자료 구조를 추가했다.
• C++11은 임의의 유형의 키와 값을 저장하기 위한 unordered_map을 표준 라이브러리에 포함한다.
• Go의 내장 map은 타입 형태의 맵 타입을 구현하며, 이는 종종 (항상 보장되는 것은 아니지만) 해시 테이블이다.
• 자바 프로그래밍 언어에는 HashSet, HashMap, LinkedHashSet 및 LinkedHashMap 제네릭 컬렉션이 포함된다.
• 파이썬의 내장 dict는 타입 형태의 해시 테이블을 구현한다.
• 루비의 내장 Hash는 루비 2.4부터 개방 주소 지정 모델을 사용한다.
• 러스트 프로그래밍 언어는 HashMap, HashSet을 러스트 표준 라이브러리의 일부로 포함한다.
• 닷넷.NET 표준 라이브러리에는 HashSet 및 Dictionary가 포함되어, C# 및 VB.NET과 같은 언어에서 사용할 수 있다.

참조

내용주

같이 보기

• 분산 해시 테이블

외부 링크

• (영어) A Hash Function for Hash Table Lookup by Bob Jenkins.
• (영어) Hash Tables by SparkNotes—explanation using C
• (영어) Hashmap explanation using Java
• (영어) Hash functions by Paul Hsieh