데이터 구조 19

Hashing 

 

: 저장하려는 Key값에 따라 위치를 정하는 것

 

• 용어

Hash table : key값이 들어갈 연속적인 저장공간 ( array )

Hash Function : Hash table상의 위치를 mapping 하는 함수

 

Collision : 서로 다른 key값이 같은 bucket주소로 mapping  ( ex: 화장실 칸에 한 명 있는데 거기에 들어간다는 느낌 )

→ 3명들어갈 칸이면 사실 들어가도 되긴 함

 

overflow : bucket이 꽉찼는데, slot 수보다 많이 저장되려고 할 때

→ collision이 발생하다가는 결국 overflow가 발생함

 

→ 구현할 때 고려해야하는 issues

: 1. Hash fuction  / 2. overflow handling method

 

요건 : 계산이 쉬워야 한다       /        collisions은 최소화  <<이걸 위해선 고유성이 있는 걸 key로 해야함

 

 

 

Collision 최소화 하는 법

 

 

1) Mid sqare : key값을 제곱한다 → 2진수로 바꾼다 → 몇 번째 비트 숫자들만 가져와서 그걸 key값 삼아서 Mapping

 

2) Folding :  key값을 2진수로 바꾼다 → 몇 개로 자른다. → 잘린 것들끼리 대칭적으로 더한다.

ex) 110001101 를 3개씩 자른다 → (대칭적으로 안 하겠음 ) 110 + 001 + 101 이렇게 더한 값을 key값으로 한다

 

3) Division : %를 이용하여 나오는 값을 Key값으로 한다.

f(k) = k%M (M=table size) 

M은 [ Prime number ] 혹은 [ 20이하의 정수로 나누어지지 않는 숫자 ] 로 하는 게 좋다 

 

4) Digit analysis : 고유성을 갖는 digit을 key값으로 선택한다

ex) 학번별로 나눌 때, 22000082 로 한다고 생각해보자

2200을 key값으로 하는 게 좋을까 82로 하는 게 좋을까 ?

고유성이 있는 걸 고르자면 82이다 

고유성이 있어야 collision이 안 생김.

 

 

 

---

 

Overflow handling 

 

1) Linear Open Addression

  hash table의 해당 주소에 overflow가 발생하면 ( = 꽉찼다 )

  → 가장 가까운(+1부터) + 비어있는 칸으로 가서 key를 넣는다.

   

 + 검색할 땐 원래 가려고 했던 곳부터 찾으면서 없으면 가장 가까운 칸들로 가면서 본다

  ( 다 검사하지 않도록, 빈 칸을 만나면 그 원소가 X라는 의미

 왜냐하면 가장 가까운, 빈 칸으로 가는 매커니즘이기 때문에 빈칸이 있으면 끝이란 뜻 )

 

단점 : 계속 덩어리져있다. 골고루 나누어지는 느낌이 아님

---

 

2) Quadratic probing

Linear open addression의 개선점

- 해당 칸에 overflow 가 발생하면 다음 순서대로 넣을 곳을 찾는다.

 

 

ex)

해당 칸(n번째 칸) overflow ?

> 원래 칸의 [ +(1^2) 칸 ] 으로 가서 비어있는지 확인 > 비어있으면 넣고 아니면 다음 단계

> 원래 칸의 [ -(1^2) 칸 ] 으로 가서 비어있는지 확인 > 비어있으면 넣고 아니면 다음 단계

> 원래 칸의 [ +(2^2) 칸 ] 으로 가서 비어있는지 확인 > 비어있으면 넣고 아니면 다음 단계

> 원래 칸의 [ -(2^2) 칸 ] 으로 가서 비어있는지 확인 > 비어있으면 넣고 아니면 다음 단계

...

 

 

---

 

3) rehasing

- n개의 hash fuction을 여러 개 만들어서 순서대로 적용

       f1 (k), f2 (k), f3 (k) …. fn (k)

k를 f=x 식으로 해싱 > overflow 

> k를 f=x^2 식으로 해싱 > overflow 

> k를 f=x^3 식으로 해싱 > overflow

...

 

 

4) Chaining

- Linked list로 구현 (참고 : 먼저 들어온 놈이 더 바깥쪽으로 밀림)

 

 

 

 

---

요약

 

 

 

Loading density  A = n( 저장된 원소의 수 ) / slot * bucket ( 저장공간 = table size) 

  →  A가 크면 활용도는 높다는 뜻, collision이 높을 가능성이 높음

 

hash table size가 크면   → 공간 낭비 가능성

hash table size가 작으면   → Collision + 성능 저하 가능성

 

 

장점 : Search / Insert / Delete 연산이 효율적

단점 : 1) Worst case 가능성을 알아내기 힘들다

  2) key값의 순서로 찾는 게 안된다. = sorted order 로 traverse 하는 기능 불가능

 아는 key값 검색은 가능

 

요건 1. 신속한 계산 / 2. Collision 최소화하기

 

 

출처: 한동대학교 김호준교수님  - 데이터 구조 PPT