[자료구조] Hash

해시 함수

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

가장 유명한 함수로는 modular 연산이 있고, 그 외의 여러 함수가 존재한다.

h(x) = x mod 13

 

좋은 해시 함수의 조건

• 계산이 간단해야 한다.
• 입력 원소가 테이블 전체에 고루 저장되어야 한다.

---

 

하지만 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정에서 충돌이 존재한다.

예를 들어 h(x) = x mod 13 인 해시함수에서,
x가 4, 17인경우 h(x), 즉 해시값은 동일하게 4로 매핑되며 이것을 해시 충돌(Hash Collision)이라고 한다. 

if(h(x1) == h(x2)) collision!

---

해시 충돌 해결 방법

1. chaning

hash table의 각 cell(bucket)을 linked list로 만든다.

linked list는 동일한 해시 결과 값 h(x) 을 가진 records들을 순차적으로 저장한다.

 

장점

• 확장성이 용이하며 데이터의 삽입/삭제가 편리
• 해시함수나 hashtable 실제 크기인 n에 영향을 덜 받음

단점

• 체인이 길어지면 최악의 경우 검색시간이 O(n)임
• linked list로 연결되어 저장된 물리주소가 순차적이지 않기 때문에 cache locality가 낮아져 cache performance 가 좋지 않음
• linked list를 위한 별도의 공간이 필요

 

2. open addressing 

chaning과 달리 주어진 Hash Table 공간에서 해결하는 방법이다.

따라서 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.

- 선형조사(linear probing), 이차원 조사(quadratic probing), 더블 해싱(double hashing)

linear probing

가장 간단한 충돌 해결 방법

충돌이 발생할 경우 i칸 씩 이동

테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아감

hi(x) = (h(x)+i) mod m  (m = table size)

quadratic probing

충돌이 발생할 경우 i^2칸 씩 이동

hi(x) = (h(x) + i^2) mod m  (m = table size)

double hashing

두 개의 함수를 사용하는 방법

충돌이 발생할 경우 i * h(x)칸 씩 이동

hi(x) = (h(x) + i * h'(x)) mod m  (m = table size)

 

 

 

---

 

reference

https://shb0328.github.io/programming/data%20structure/algorithm/hash/

https://www.programiz.com/dsa/hash-table