Hashing(1)

Hashing

어떠한 key값이 주어지면 그 key 값으로 상수시간에 원하는 값을 찾을 수 있게 하는 것이 Hashing이다.

 

record 값을 담고 있는 Hash table을 이용하는데, 이 Hash table을 편의상 HT라고 하자.

 

HT가 가지고 있는 slot의 개수를 M개라고 하자.

 

우리는 key 값을 mapping하는 Hash function을 이용한다. 이 hash function을 h라고 하자.

어느 key 값 K가 주어졌을 때 h(K)의 범위는 다음과 같다.

0<=h(K) <= M-1

 

따라서 주어진 key 값으로 hash function안에 넣어서 구한 값 i를 이용하여 HT[i]에 위치해있는 record를 가져오면 상수시간안에 값을 찾을 수 있는 것이다!

 

 

Collision

서로 다른 key 값 두 개 k1과 k2가 존재할 때 만약 h(k1) = h(k2)라면 collision이 발생한다.

다른 key값을 가지면 다른 value가 나와야 하는데 가리키는 위치가 똑같기 때문에 record를 배치할 수 없게 된다.

이를 해결하기 위하여 collision resolution policy가 여러 개 존재한다.

다음 게시글에 어떠한 collision resolution policy가 있는지 살펴보겠다.

 

 

 

Hash Functions

어떤 hash function이 좋은 것인가?

-> incoming data에 상관 없이 모든 slot에 고른 probability를 주는 hash function

 

 

예)

M = 16이고 h(K) = K%16. h(k)는 좋은 hash function인가?

->

1) key가 짝수만 들어온다면 홀수 slot들은 쓰이지 않는다

2) K가 큰 값이면 모든 bit를 사용하지 않고 마지막 bit 4개만 사용한다.

이러한 이유로 좋은 hash function이 아니다.

 

1) 해결 방법 :

M을 소수를 사용한다.

2) 해결 방법 :

key의 모든 bit를 사용한다. 예를 들어 hash function이 k^2 % M 이었으면 모든 bit를 사용할 수 있다.

 

 

 

 

 

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