[자료구조] hash table

1. hash table

key : value 시스템 구조를 가지며, 데이터 검색을 빠르게 할 수 있는 자료구조이다.

hash table의 작동원리를 보면, 빠른 검색을 할 수 있는 이유를 알 수 있다.

hash table은 내부에 array 구조를 통해 data를 저장을 한다. 이때, 하나의 저장하는 공간을 일반적으로 버킷이라고 부른다.

hash table은 각각의 key값에 대하여 특정한 알고리즘인 hash function을 이용해 index를 생성한다.

생성된 index를 통해 array에서 데이터를 검색하거나, 생성 및 삭제를 동작 시킨다.

즉, 아래의 방식으로 key값을 통해 value에 접근을 할 수 있기 때문에 평균적으로 o(1)의 시간복잡도가 나온다. (hash function 1번 수행)

key → hash function → index → value

 

 

✨ hash table vs array

search 시,

array는 하나하나 체크하며 비교 o(n)

hash table은 key를 통해 value 접근 o(1) (추가, 삭제도 o(1))

 

 

2. hash function

특정 key을 대입 후 index 값(hash code라고 부름) 반환을 하는 hash function을 만들어야 함.
아래는 hash function의 예시이다.

• Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
• Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
• Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
• Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

 

3. Resolve Collision

: 충돌을 해결하는 기본적인 2가지 방식

(1) open address

해시 충돌이 발생하면, (즉 삽입하려는 해시 버킷이 이미 사용 중인 경우) 다른 해시 버킷에 해당 자료를 삽입하는 방식
공개 주소 방식이라고도 불리는 이 알고리즘은 Collision 이 발생하면 데이터를 저장할 장소를 찾아 헤맨다.
Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다. 대표적으로 3가지 방식이 있다.

- Linear Probing (선형탐사)

현재의 버킷 index로부터 고정폭 만큼씩 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행한다. 선형탐사는 바로 인접한 인덱스에 데이터를 삽입해가기 때문에 데이터가 밀집되는 클러스터링(Clustering) 문제가 발생하고 이로인해 탐색과 삭제가 느려지게 된다.

 

-Quadratic probing

해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식 선형탐사에 비해 더 폭넓게 탐사하기 때문에 탐색과 삭제에 효율적일 수 있다. 하지만 이는 초기 해시값이 같을 경우에 탐사하는 역시나 클러스터링 문제가 발생하게 된다.

 

- Double hashing probing (이중 해싱 탐사)
해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다.
이중해싱은 선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입된 것이다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.

 

(2) separate chaining

일반적으로 Open Addressing 은 Separate Chaining 보다 느리다. Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다.

 

- 연결 리스트를 사용하는 방식(Linked List)  
각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식하지만 메모리 문제를 야기할 수 있으며, 테이블의 부하율에 따라 선형적으로 성능이 저하된다. 따라서 부하율이 작을 경우에는 open addressing 방식이 빠르다.
해시 충돌이 일어나더라도 linked list로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.

 

-Tree 를 사용하는 방식 (Red-Black Tree) 

기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.