HashMap 충돌 (java 8)

HashMap을 굉장히 자주 사용하는데 String 이나 POJO 같은 Object를 key로 사용할 수 있어서 편리하다.

저 Object를 가지고 내부적으로 key를 어떻게 사용하는지 알아보자

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash(key) 함수로 hash값을 만들어서 사용하는데, 그 리턴값의 타입이 int다.

hash함수를 보면 key라는 Object의 int를 리턴하는 hashCode() 함수를 바로 사용을 하고 있다.

key가 Object의 hashCode 로 int를 사용한다는 것은 2의 32승 개의 key를 가질수 있는 구조다.

 

또한 그러면 HashMap에서 get으로 원소를 가져올 때 O(1)로 가져오려면 2^32개의 배열을 들고있어야 하는데 그러면 너무 낭비이다. 그렇기 때문에 버킷 사이즈를 M으로 정하고 index를 다음과 같이 계산한다. 

 

int index = X.hashCode() % M;

 

그러면 진짜로 같은 어쩌다가 같은 hash로 key충돌 외에도 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 key를 사용하게 된다.

 

어떻게 해! 

방법은... linked list로 같은 해쉬 키를 가진 버킷을 유지하는것이다.

그러면 이제 탐색하는데 시간은 좀 더 걸리지만 메모리를 절약할수있다.

java 8에서는 이걸 개선하기 위해서 한 버킷의 크기가 threshold이상 커지면 linked list를 tree로 변경한다.

Tree같은 경우에는 worst case에서 linked list보다 탐색 속도가 worst case에서 O(log n) 으로 linked list의 O(n)보다 작다.

 

thresold는 다음과 같이 되어있다.

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

하나의 버킷에 개수가 8개 이상이면 트리화 하고 반대로 삭제되서 6개보다 작아지면 링크드 리스트로 변경한다.

 

 

실제로 java 8의 index계산 및 해쉬 함수를 보자

 

테이블의 index i는 테이블의 last index (n-1) 에 hash값을 & 연산해서 계산한다.

i = (n - 1) & hash

hash값은 key를 가지고 한차례 변경을 해주는데,

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 h ^ (h >>> 16) 연산으로 해쉬값을 변경한다.

 

>>> 연산자는 잘 안써봣는데, 

정수 h의 각 비트를 16만큼 오른쪽으로 이동시키고 빈자리를 0으로 채우는것이다. (>>는 최상위 비트로 앞을 채움)

그러니까 상위 비트를 하위에도 넣어주는 것이다. 

 

왜냐면, index계산할 때 & 연산을 통해서 상위 비트가 어차피 날라가기 때문에 하위에 넣어주는것이다. 

java 7에서는 이거보다 복잡한 방식으로 hash값 조정을 했다고 하는데, java 8에서 hash bucket 관리하는 방식이 linked list에서 tree로 변경됨에 따라 좀더 간단한 연산으로 성능상 이점을 얻고자 했던것 같다.

 

 

자바독 설명에 따르면 다음과 같다.

key.hashCode()를 계산하고 해시의 상위 비트를 하위 비트로 확산(XOR)합니다.  테이블은 2의 거듭제곱 마스킹을 사용하기 때문에 현재 마스크 위의 비트만 달라지는 해시 집합은 항상 충돌합니다. (알려진 예 중에는 작은 테이블에 연속적인 정수를 보유하는 Float 키 세트가 있습니다.)  따라서 상위 비트의 영향을 아래쪽으로 분산시키는 변환을 적용합니다. 비트 확산의 속도, 유틸리티 및 품질 간에는 절충점이 있습니다. 많은 공통 해시 집합이 이미 합리적으로 분포되어 있으므로(확산의 이점을 얻지 못함) 트리를 사용하여 빈에서 대규모 충돌 집합을 처리하기 때문에 가능한 가장 저렴한 방법으로 일부 이동된 비트를 XOR하여 체계적인 손실을 줄입니다.  뿐만 아니라 테이블 경계로 인해 인덱스 계산에 사용되지 않는 최상위 비트의 영향을 통합합니다.

 

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