좋은 해시함수란?
-
해시함수는 Collision을 최소화 하는 방향으로 설계되어야 한다. 또한 Collision이 발생할 경우 어떻게 대응해야 하는지가 가장 중요하다고 할 수 있다.
-
해시함수에 대한 Collision이 증가할수록 시간복잡도는 O(1)에서 O(n)까지 점점 가까워질 것이다. 따라서 Collision 해결은 필수이며 그 방법에 대해 알아보고자 한다.
Open Address(개방주소법) vs Separate Chaining(분리 연결법)
개방주소법
- 충돌 발생시 다른 해시 버킷에 자료를 삽입하는 방식이다. 이 방법은 만약 충돌이 발생하면 데이터를 저장할 장소를 찾아 헤메다가 알맞은 버킷을 발견하면 데이터를 저장한다.
분리 연결법
-
Open Address보다 Separate Chaning이 더 빠르다. Open Addressing의 경우 버킷을 채운 밀도가 높을수록 버킷을 더 많이 탐색해야 하기 때문이다.
-
Java7에서는 HashMap에서 Collision발생시 이 방법을 사용하고 있다고 한다.
@@@ 자바 HashMap의 동작방식
- 자바에서 hashmap에 데이터를 저장할 때, 먼저 key값을 hashcode()를 이용해 int형의 hash값으로 바꾸고 이를 버킷의 사이즈인 M으로 나는 나머지가 해시 버킷의 인덱스가 된다.
- ex) int index = hashcode() %M;
분리 연결법 2가지
-
LinkedList를 사용하여 Collision 발생 시 해당 버킷에 Collision이 발생하면 LinkedList에서 데이터를 삽입하듯이 새로 추가하는 방식이다. 하지만 작은 데이터들을 저장할 때 리스트 자체의 오버헤드가 부담이 될 수 있다.
-
Red-Black Tree를 사용하는 방법이다. 기본적인 동작방식은 같지만 해시 버킷에 할당된 key-value 쌍의 데이터 개수에 따라 LinkedList를 사용할 것인지, 트리를 사용할 것인지 구분된다.
-
이 기준은 데이터의 개수가 6, 8일때이다. 데이터의 삽입, 삭제가 빈번하게 일어나는 해시테이블에서는 기준을 7로 잡고 6에서 7로 변할때 LinkedList -> RBTree로 바꾸고, 7에서 6으로 변하면 다시 바꾸는 과정은 Switching 비용이 너무 많이 들기 때문에 임시값인 7을 비워둔 것이다.
효율성
- Open Address방식은 데이터가 연속적으로 저장되기 때문에 데이터가 적다면 더 성능이 좋다. 하지만 버킷을 계속해서 사용하기 때문에 데이터의 개수가 많아질 경우 좋은 성능을 내기 어렵다.
