Hash Table

Hash table 이란?

key-value 쌍의 데이터를 입력받아 빠른 속도로 탐색이 가능한 자료구조이다.

좋은 hash 함수란 ?

hash 값이 고르게 분포되게 하는 것이다.

 

시간 복잡도

collision이 많을 수록 시간복잡도는 O(1)에서 O(n)에 가까워진다.

 

Collision이란?

서로 다른 key의 hash 값이 같을 때 collision 이 발생한다.

 

Collision 해결 방법

1. seperate chaining

linked list를 이용한다. collision 이 발생하면 linked list에 버킷(bucket)을 추가하여 데이터를 저장한다.

시간복잡도

삽입	검색	삭제
O(1)	O(1)	O(1)

worst case 의 시간복잡도

삽입	검색	삭제
O(n)	O(n)	O(n)

2. open addressing

collision 이 발생하면 미리 정한 규칙에 따라 hash table에 비어있는 버킷(bucket)을 찾아 저장한다.

 

이 방법에는 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉜다.

 

1) Linear Probing 선형 조사법

비어있는 버킷(bucket)을 찾을 때 까지 (+1, +2, +3 ~~~ )만큼 건너 뛰어 데이터를 저장한다.

 

2) Quadratic Probing 이차 조사법 

비어있는 버킷(bucket)을 찾을 때 까지 (+1^2, +2^2, +3^2 ~~~ )만큼 건너 뛰어 데이터를 저장한다.

 

3) Double Hashing

Linear Probing과 Quadratic Probing은 이동폭이 같아 클러스터링 문제가 발생할 수 있다.

이 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식이 Double Hashing 이다.

첫번째 해시함수는 최초의 해시값을 얻을 때 사용하고, 두번째 해시함수는 collision이 발생했을 때 이동폭을 얻을 때 사용한다.