[자료구조] Hash 충돌과 이를 회피하기위한 기법
Hash function 이란?
해시함수(hash function) :
먼저, 해시함수는 해시테이블 에서 index 값으로 사용된다. key-value 쌍을 저장할 때, 고유한 key를 hash code로 변환시킨다. 이 때의 결과값은 데이터 고유의 index로 사용되기때문에 다른 값들과 같아선 안된다. 이를 위한 알고리즘이 바로 해시함수(hash function) 이다.
hash function을 무조건 1:1 (key --> hash code) 로 만들게 되면, 결국 array와 다를바 없고 메모리를 너무 차지하게 된다.
따라서, 일반적으로 좋은 hash function은 키 전체를 참조하여 해쉬값을 만들어 낸다. hash function는 다음의 4가지 대표적 특성을 가진다.
- 압축 및 일관성 -> 고정길이의 해시값, 같은 메시지에는 언제나 동일한 결과값을 반환한다.
- 계산용이성 -> 계산이 빠르고 용이해야한다.
- 일방향성 -> f(M) 의 경우, M을 역산 할 수 없다(역상저항성).
- 충돌저항성 - > apple, appl 이라는 메시지가 있을때, 이 둘의 해시값은 매우 크게 다른값을 가져야한다.
∎ Hash 충돌과 이를 회피하기위한 기법
해시함수는 출력값은 유한하고, 입력값은 무한하기 때문에 충돌이 발생한다. 즉, 서로 다른 입력값이 같은 출력값을 가질 수 있다.
이를 회피하기 위한 방식으로 개별 체이닝 방법과 오픈 어드레싱이 있다.
개별 체이닝 (Separate Chaining) - C++, JAVA, GO
별도의 자료구조(연결 리스트, 트리-RedBlackTree)를 활용하여 버킷에 덧붙이는 방식.
- 연결 리스트(Linked List) -> 버킷들을 Linked List로 만들어, Collision 발생 시 별다른 조치 없이 해당 버킷에 추가해주는 방법. 하지만 연결리스트의 단점들도 고대로 가져오게 된다.
- 트리(Red-Black Tree) -> 버킷에 저장된 데이터가 많아질수록 연결리스트의 순차적 접근 방식이 상당히 비효율적이게 되기 때문에, 이를 트리구조로 사용한다. O(N) -> O(H)
오픈 어드레싱 (Open Address) - Python, Ruby
해시 충돌이 발생하면, 다른 비어있는 해시 버킷에 해당 자료를 삽입하는 방식.
남은 버킷의 용량이 적을 경우, 효율이 크게 떨어질 수 있다.
- Linear Probing -> 순차적으로 비어있는 버킷을 탐색한다.
- Quadratic probing -> 2차함수를 이용하여 탐색할 위치를 찾는다.
- Double hashing probing -> 하나의 해시함수에서 충돌이 발생하면 2차 해시함수를 이용해 새로운 주소를 할당.
+)
Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web(Karger et al.) -> 분산 캐싱, Hash Ring 개념 사용
Reference
https://returnbliss.tistory.com/18
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#tree