[자료 구조] 해시 테이블(Hash Table)

key-value 쌍의 데이터를 입력받아 빠른 탐색을 가능하게 하는 자료구조이다. 각 해시 테이블의 hash function에 key 값을 집어넣어 얻은 해시값을 위치로 key-value 데이터 쌍을 저장합니다. key 에 해당하는 value 값을 찾을 때 다른 주소의 탐색없이 Hash function에 key 값을 넣은 결과값의 위치만 확인하면 되기에 빠른 탐색이 가능하다. 여기서 value값을 저장하는 위치를 버킷(슬롯)이라고 한다.

Hash Function

Hash Function은 각 key값에 해당하는 고유한 인덱스 값을 얻기 위해 존재한다.

Division Method 

Index = key % 테이블의 크기

Digit Folding

Key의 각 자리 문자를 ASCII 코드로 바꾼 값을 합한 값을 Index로 사용한다.

Multiplication Method

숫자로 된 Key값(K), 0과 1 사이의 소수(A), 보통 2의 제곱수(m) 를 곱합 값을 Index로 사용한다.

Index =  (KA mod 1) × m

Univeral Hashing

다수의 해시함수 집합 H에서, 무작위로 해시함수를 선택하는 기법이다. (https://klioop.tistory.com/43)

 

Collision

각기 다른 key들이 같은 hash function 결과값을 가지게 되면 충돌(Collision)이 일어났다고 한다. 이러한 경우 크게 두가지 Open addressing 과 Separate chaining 이라는 방법으로 해결한다. Collision이 일어나면 연산속도가 느려지기 때문에 hash function 설계 상에 최대한 Collision 적게 일어나도록 해야한다.

Open addressing

Open addressing은 미리 정한 규칙에 따라 비어있는 버켓을 찾는 방식입니다. Separate chaining방식에 비해 메모리를 효율적으로 사용할 수 있습니다. Open addressing방식에는 Linear Probing, Quadratic Probing, Doubling Hashing이 있습니다.

 

Linear Probing

• Collison이 발생한 인덱스를 기준으로 일정한 크기만큼 인덱스를 증가시키며 빈 슬롯을 찾는 방법

Quadratic Probing

• Collison이 발생한 인덱스를 기준으로 제곱수만큼 인덱스를 증가시키며 빈 슬롯을 찾는 방법

Double Hashing

• 위의 두 방법은 인덱스의 증가값이 일정하기 때문에 클러스터링 문제가 발생할 확률이 높다. 이를 해결하기 위해 또 하나의 Hash function을 통해 key마다 다른 인덱스 증가값을 주는 방법이다.

Separate chaining

인덱스마다 Linked list 나 Tree 형태로 Slot을 만들어 Collision을 해결한다. Collision이 발생한 위치에 새로운 슬롯을 생성해준 뒤 연결시켜준다. Linked list로 사용하다가 Collision이 많아지면 Binary Search Tree 형식으로 바꿔줘 시간 복잡도 O(n) 에서 O(logn)으로 줄일 수 있다.

Open addressing VS Separate chaining

Open addressing	Separate chaining
Key들이 Hash table 내부에만 존재	Key들이 Hash table 내외로 다 존재 가능
기존에 정해진 크기를 넘어선 key의 개수를 넣는 것은 불가	해시 테이블의 크기와 상관없이 key 삽입가능
삭제가 어렵다	삭제가 쉽다
추가적인 공간이 불필요	해시 테이블 외부에 있는 키들의 포인터를 저장하기 위한 추가 공간 필요
캐시 성능이 좋다.	해시 테이블 외부에도 key가 있기 때문에 캐시 성능이 좋지 않다,
그 슬롯을 가리키는 해시값이 없어도 슬롯 사용가능	몇개의 슬롯은 전혀 사용되지 않을 가능성 있음

Reference

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cestlavie_01&logNo=220932263930

https://mangkyu.tistory.com/102

https://www.gatevidyalay.com/separate-chaining-open-addressing-comparison/