hashing

Hashing 이란?

- 다양한 길이의 key 값을 hash function에 input으로 넣어서 고정된 길이

(0,1,2,.... M-1, M=데이터가 저장된 hash table의 크기)의  output (hash value, h(key))으로 변환하는 작업

 

- key 값에 해당하는 데이터가 저장/탐색되는 위치(index)를 알아내기 위해 사용됨.  

→ Sorting과 searching이 모두 O(1)에 가능한 구조이다.

---

Hash 함수의 충돌

서로 다른 탐색 키를 갖는 항목들이 같이 해시 주소를 가지는 현상

→ 충돌이 발생하면 해시 테이블에 항목 저장 불가능

 

충돌 해결책

→ chaining 체이닝

→ open addressing 개방 주소법

---

Chaining 체이닝

버킷 내에 연결 리스트를 할당하여 삽입과 삭제를 진행하는 방식

→ 각 버킷에는 고정된 슬롯이 할당되어 있지 않고 연결 리스트를 할당받기 때문에 충돌이 발생하지 않는다.

→ 버킷 내에서는 연결리스트 순차탐색을 진행한다.

 

---

Open addressing 주소 개방법

충돌이 일어난 항목을 해시 테이블의 다른 위치에 저

1) 선형 조사법

2) 이차 조사법

3) 이중 해싱법

4) 임의 조사법

 

1) 선형 조사법

오버플로우가 발생한 경우 버킷을 순차적으로 탐색해간다.

 

2) 이차 조사법

선형 조사법과 유사하지만, 충돌이 발생하면 +1을 더해서 mod 연산을 하는 것이 아니라, 아래와 같은 식을 사용한다.

(h(k) + inc*inc) mod M

inc = 1, 2, 3, 4, ...

 

3) 이중 해싱법

오버 플로우 / 충돌이 발생하면 원래의 해시함수와 다른 별개의 해시 함수를 사용한다.

h'(k) = C - (k mod C)

C = 해시 테이블 크기 M보다 작은 소수

h(k) → 충돌 발생

→ h(k) + h'(k)

→ h(k) + 2* h'(k)

→ h(k) + 3* h'(k)

https://velog.io/@bada308/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9CHash