Hash Collision(해시 충돌) Open Addressing(개방 주소법)

해시 충돌

hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황

Open Addressing(개방 주소법)

해시 충돌이 발생하면 테이블 내의 사용되지 않는 곳을 탐사(Probe) 한 후, 비어있는 곳에 충돌된 데이터를 저장하는 방식

 

- Linear Probing (선형조사)

 

비어있는 곳을 선택할 때, 바로 다음 빈 공간으로 한다. 

 

1. 함수의 결과에 따른 index의 슬롯이 비어 있으면 데이터를 저장한다.

2. 비어 있지 않다면, 이전에 저장된 데이터의 key 비교한다.

3. key 값이 같다면, 값을 업데이트한다. 다르면 바로 다음 index를 확인합니다.

3. 빈 슬롯을 찾을때까지 1칸씩 이동하여, 빈 슬롯을 찾으면 데이터를 저장합니다.

 

*저장을 하는 배열은 원형이라 가정을 합니다. 

*특정 위치에 데이터가 집중적으로 저장되어 군집형태를 이루게 되기 때문에 해당 데이터를 찾을때 시간이 비효율적이될 수 있습니다.

key와 value가 같다고 가정한다.

 

- Quadratic Probing (이차 조사)

 

바로 다음 빈 공간에  데이터를 저장한것과 달리 제곱수를 더해서 빈 슬롯을 찾아서 저장한다.

제곱수로 빈 공간을 찾는 이유는 가능하면 데이터가 한 곳에 몰리지 않도록 하기 위해서 입니다. 그래서 Cluster(군집)의 크기를 적게 하기 위함 입니다. 하지만, 여전히 군집이 커질수 있습니다.

 

1. 함수의 결과에 따른 index의 주소가 비어 있으면 데이터를 저장한다.

2. 비어 있지 않다면, 이전에 저장된 데이터의 key 비교한다.

3. key 값이 같다면, 값을 업데이트한다, 다르면 바로 1칸, 2칸, 4칸, 8칸, 16칸 씩 이동하면서 index를 확인합니다.

4.  빈 슬롯을 찾을때까 1칸, 2칸, 4칸, 8칸, 16칸이동하여, 빈 슬롯을 찾으면 데이터를 저장합니다.

 

- Double Hash (이중 해시)

 

 빈 주소의 공간을 택하는 방법을 랜덤성있게 하여 가능한 Cluster(군집)의 크기를 적게해야 된다

이중 해쉬 방식은 2개의 해시함수를 사용한다.

 

first hash function - 슬롯에서 데이터가 들어갈 idx를 계산한다.

second hash function - 충돌 발생시 빈 슬롯을 찾기위해 얼마나 이동할지 구하기 위해 사용됩니다.

 

1. 함수의 결과에 따른 index의 슬롯이 비어 있으면 데이터를 저장한다.

2. 비어 있지 않다면, 이전에 저장된 데이터의 key 비교한다.

3. key 값이 같다면, 값을 업데이트한다. 다르면 second hash function에 넣어 몇칸씩 이동할지 계산합니다.

3. 슬롯을 찾을때까지 offset을 증가시켜, 빈 공간을 찾아 데이터를 저장합니다.

 

 

 

* 두 개의 해시 함수를 이용하기 때문에 연산이 상대적으로 오래걸립니다. 대신 클러스터의 크기가 상대적으로 작아진다.

 

결국 OpenAddressin(Linear, Quadratic, Double)은 Cluster의 크기 따라 성능이 달려있다.

 

Cluster 영향을 주는것은 Hash Function, Collision Resolution Method, Load Factor 가 있다.

 

Load Factor란 Hash Table Size중 얼마나 슬롯에 데이터가 들어가 있는냐이다.

즉, 실제 저장된 데이터의 개수가 N개고 Hash Table Size는 M이라 하면 Load Factor의 값은 N/M이다. 

0 <= N/M <= 1

 

평균적으로 M >= 2N, 즉 테이블의 크기가 저장된 데이터의 크기 보다 2배 이상으로 유지하고, C-Universe Hash Function을 사용하면 Cluster의  평균 탐색 시간이 O(1)된다는것이 증명 되어있다.

 

새로운 데이터가 삽입 되었을 경우, 슬롯의 절반이 찼다면, 확장하는 비용을 감수하더라도 Table을 크기를 2배로 증가 시키고,

데이터를 재배치 한다.