Hashing(2)

Collision Resolution

Collision resolution에는 Open hashing과 Closed hashing이 있다.

 

Open hashing

Open Hashing

Collision이 생기면 table 밖에 저장한다.

한계점으로는 사용이 안되는 slot이 생길 수 있다.

 

 

Closed Hashing

Collision이 생기면 table안에 있는 다른 slot에 저장한다.

다음의 예들은 Closed Hashing의 종류들중 하나이다.

Bucket Hashing

Hash table slot들을 bucket으로 나눈다.

왼쪽의 table의 한 예이다.

10개의 칸이 있지만 bucket은 5개이다. h(k) = k mod 5이다.

같은 hash 값이 나와도 bucket안에 공간이 있기 때문에 collision이 일어나지 않고 slot을 채울 수 있다.

그러나 bucket이 차면 overflow가 생길 수 있다는 한계점을 가지고 있다.

 

Bucket hashing은 open hashing과 비교하였을 때 collision이 더 많이 일어나기 때문에 item을 search하는 시간이 오래걸린다.

그러나 사용하는 space가 적다는 장점이 있다.

 

 

 

 

 

 

 

 

 

 

Linear Probing

probe function을 이용한다.

hash function에서의 값이 같다면 probe function에서 key 값을 넣어서 나온 값을 더한 index에 item을 넣는 것이다.

Linear Probing의 경우 probe function P(K, i) = i이다.

Key의 값과 상관없이 collision이 난 index의 다음 index에 item을 넣게 해준다.

 

linear probing의 문제점은 다음과 같은 상황에서 나온다.

왼쪽과 같은 상황일 때 random key가 들어온다면 Slot2에 들어갈 확률이 60%이고 나머지 slot에 들어갈 확률은 각각 10%에 불과하다.

 

바로 다음 index에 item들을 넣다보니 nonempty slot들이 뭉쳐있는 상황이 발생하기 때문이다. 이러한 현상을 primary clustering이라고 한다.

 

이를 해결하기 위하여 probe function을 qudratic으로 만들거나 상수배를 곱하는 등을 하기도 한다.

 

 

 

 

 

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업