Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
빠른 이유
- 내부적으로 배열(버킷)을 사용하여 데이터를 저장한다.
- 각각의
Key값에 해시함수를 적용해 배열의 고유한index를 생성해 검색하기 때문이다.
간단한 예
Key, Value가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장하려한다.
index = hash_function("John Smith") % 16연산을 통해index값을 계산한다.array[index] = "521-1234"로 전화번호를 저장한다.
이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있따.
해시테이블의 평균 시간복잡도는
O(1)이다.
Hash 함수
해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 아래에 대표적인 해시 함수 3+1가지가 있다.
Division Method
나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어(나머지 연산) 계산한다.
(주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다.
Digit Folding
각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
Multiplication Method
- 숫자로된
Key값K - 0과 1사이의 실수
A - 보통 2의 제곱수인
m
위 세가지를 사용하여 다음과 같은 계산을 해준다.
h(K)=(KAmod1)*m
Univeral Hashing
다수의 해시 함수를 만들어 집합 H에 넣어두고, 무작위로 해시 함수를 선택해 해시값을 만드는 기법이다.
해시값이 충돌하는 경우
John Smith를 해시 함수를 돌려 나온 값과 MinKyu를 해시 함수를 돌려 나온 값이 동일하다면?
분리 연결법(Separate Chaining)
버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 Chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.
개방 주소법(Open Addressing)
추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.
기본적으로 세가지 방법 모두 테이블 크기만큼 나머지 연산하여 배열의 범위를 벗어나지 않도록 한다.
Linear Probing
현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
Quadratic Probing
해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어, 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2칸씩 옮기는 방식이다.
Double Hashing Probing
해시된 값을 한 번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한 번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
개발 주소법은 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 HashTable을 재정리 해주는 작업이 필요하다.
시간 복잡도
Key 값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 O(1)의 시간 복잡도로 데이터를 조회할 수 있다.
하지만
충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간 복잡도가 증가할 수 있다.
충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만 공간을 많이 사용한다는 치명적인 단점이 있다. 만약 테이블이 꽉 차있는 경우 테이블을 확정해주어야 하는데, 이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확장을 하지 않도록 테이블을 설계해주어야 한다.
출처
