java HashMap의 해시충돌 및 전략

HashMap은 key의 중복을 허용하지 않고 key-value를 1:1로 매핑하는 자료구조이다.

hash의 제공해주는중 장점으로는 빠른 탐색,삽입,삭제에도 있지만 해시 충돌이라는 문제를 꼭 생각해봐야 한다.

 

해쉬 충돌

 

동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수(perfect hash functions)라고 한다.

Integer, Long, Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있다. 하지만 String이나 POJO(plain old java object)에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.

 

더 나아가 자바는 기본적으로 hashcode()함수의 리턴값을 int로 지정해놓았기 때문에 2^32개의 객체를 다르게 저장할 수 있지만 가능한 키 범위가 더 많을수도 있고, 가능한 키 범위와 동일하게 배열의 크기를 할당해 놓는게 아니라 동적으로 늘려가기 때문에(2배씩 늘려나감) 충돌이 발생할 수 밖에 없다.

 

인덱스를 정하는 방법은  int index = X.hashCode() % M; 이다. M은 배열의 크기

이 식에서 알 수 있는것은 hashcode의 값이 달랐더라도 M 모듈러 연산을 하면서 한번 더 해쉬충돌이 일어날 수 있어 총 2번의 충돌이 가능하다는 점이다.

 

해결방식에는 어떤 것이 있을까.

Open Addressing과 Separate Chaining 구조

open addressing 

open addressing 방식은 찾은 해시값의 버킷이 이미 사용중인 경우 비어있는 다른 해시 버킷에 데이터를 삽입하는 방식이다.Linear Probing(고정폭으로 증가시켜보며 탐색),Quadratic probing(폭을 제곱시키며 탐색 1^2,2^2,3^2) 등의 방식이 있다.

 

Separate Chaining

Separate Chaining방식은 찾은 해시값의 버킷이 이미 사용중인 경우 링크드 리스트를 만들어 순차적으로 저장한다.

index에 들어가있는 첫 인자는 링크드 리스트의 head 부분이 된다.

 

장단점

open addressing

두 방식 모두 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다. 하지만 open addressing은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋다.

따라서 데이터가 적다면 open addressing이 좋다. 하지만 데이터가 많아지면 캐시 적중률이 떨어지기 때문에 장점이 사라지게 된다. 더 나아가 삭제가 어렵다.

hashMap은 삭제가 빈번하게 호출될 수 있는 자료구조인데, 중간에 삭제된 데이터 때문에 제대로 검색을 하지 못하는 부분과 삭제된 부분에 Dummy node를 삽입해 놓아야 한다는 불편함이 생긴다.

 

Separate Chaining

삭제에 대한 처리가 linked list를 타고들어가서 노드를 삭제해주면 되기 때문에 간단하다는 장점이 있다.

그리고 버킷의 크기가 커지면 open addressing은 버킷의 밀도가 높아져서 worst case가 자주 일어난다는 단점이 생긴다. 하지만 separate addressing 방식은 worst case를 줄여주는 보조 해시 함수를 사용한다(마지막 링크 d2확인)

 

그럼 자바는 어떤 것을 활용할까?

자바 7 까지는 기본적인 Separate Chaining을 활용하여 O(N)의 시간복잡도를 발생시켰지만. 자바 8에서 부터 링크드 리스트부분을 red-black-tree를 활용하여 O(logN)의 시간을 가지고 해결하도록 성능을 향상 시켰다.

코드를 살펴보면

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;  


if (binCount >= TREEIFY_THRESHOLD - 1) // 임계값이 초과할 경우 트리화
		treeifyBin(tab, hash);
		break;

8개의 key-value쌍이 생기면 트리로 만들고 다시 6개가 된다면 링크드 리스트로 변경한다. 2의 차이가 나는 것은 1개의 차이로 계속 자료구조의 변경이 생기면 비효율적이기 때문이다.

 

느낀점

자바는 성능향상을 위해 노력하는구나.

hashmap의 시간복잡도만 외우던 것을 반성하게 되었다.

N이 작아서 시간복잡도의 문제가 없을때보다 N이 커졌을때를 생각해서 Separate Chaining을 도입했고 거기서도 red-black-tree로 최적화 시켜 사용하는구나.

 

공부한곳

https://d2.naver.com/helloworld/831311

https://woodcock.tistory.com/24