Java HashMap의 내부 동작 - 해시 버킷 개수 조정

관련 포스팅

1. Java HashMap의 내부 동작 - 이론편
2. Java HashMap의 내부 동작 - 실전편
3. Java HashMap의 내부 동작 - 해시 버킷 개수 조정

---

이번 글에서는 자바의 HashMap의 성능을 위한 해시 버킷의 개수에 관련해 알아보자

 

해시 버킷 개수 조정

우선 저번 글에서 확인하였듯이 HashMap에서는 데이터를 해시버킷에 나누어 저장해둔다.

여기서 해시버킷의 인덱스 계산을  "X.hashCode() % M(해시 버킷의 개수)"을 통하여 진행하는데

만일 해시버킷의 개수가 적다면 데이터가 증가할 수록 더 많은 해시충돌이 발생할 것이고,

이는 성능 저하로 이어지게 된다.

 

이를 방지하기 위해 HashMap에서는

데이터 개수가 "load factor(기본값 3/4) * 현재 해시 버킷의 개수"에 도달할 때마다 

해시 버킷의 개수를 2배로 늘려주며 기본 16개부터 시작하여 최대 2^30까지 증가한다.

 

또 해시 버킷의 개수는 생성자에서 지정 가능하다.

만일 기본 생성자로 생성한 HashMap에 많은 양의 데이터를 추가할 경우

데이터 개수의 최적에 맞춰 생성한 해시맵보다 수행 시간이 2.5배 길어진다고한다.

 

따라서 성능을 고려한다면 만일 1000개의 데이터가 입력될 예정인 경우

해시버킷 개수는 1000 * 4/3  = 1333.3333...

즉 1334개이상이어야 해시 버킷 개수 조정 없이 데이터를 수용할 것이다.

허나 해시 버킷의 개수는 2의 제곱으로만 설정되므로 가장 가까운 값인 2048로 생성하면 된다.

해시 버킷의 개수와 loadFactor를 지정할 수 있는 HashMap 생성자

 

그런데 해시 버킷의 크기를 두배로 확장하는 것에는 큰 문제점이 있다.

이는 해시버킷의 개수를 항상 2^a개가 되게 하여

해시 버킷 인덱스를 "X.hashCode() % M"을 통하여 계산 시 해시 코드의 하위 a개의 비트만 사용하게 된다.

이는 해시충돌로 이어질 수 있고 이를 해결하기 위하여 보조 해시 함수를 사용하게 된다.

 

허나 해시 버킷의 크기를 두 배로 확장하는 방식은 중요한 문제점을 갖고 있다.

해시 버킷 인덱스를 "X.hashCode() % M"을 통해 계산할 때 M값을 항상 2^ a으로 유지하게 한다.

이로 인해 해시 코드의 하위 a개 비트만을 사용하기 때문에 해시 충돌이 발생할 확률이 높아진다.

이러한 문제를 해결하기 위해 보조 해시 함수를 사용한다.

---

보조 해시 함수

보조 해시함수는 key의 해시값을 변형하여 index값 분포가 가급적 균등할 수 있도록 하고

결과적으로 해시 충돌 가능성을 줄여준다.

 

Java8의 HashMap은 아래와 같이 해시값을 변형하여 사용한다.

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

 

이와 같이 key의 해시값을 변형해주면 데이터들이 해시 버킷에 좀 더 고르게 분포되어 해시충돌을 줄일 수 있다.

 

---

정리

자바의 HashMap을 기본 생성자로 생성 후 많은 데이터를 넣어줄 경우 성능이 2.5배 하락한다.

따라서 "추가될 데이터 개수 * 4/3" 이상으로 해시 버킷 개수를 지정하여 생성하자.

또 HashMap의 해시버킷에 데이터가 균등하게 분포할 수 있도록 보조 해시 함수를 활용한다.

 

---

관련 포스팅

1. Java HashMap의 내부 동작 - 이론편
2. Java HashMap의 내부 동작 - 실전편
3. Java HashMap의 내부 동작 - 해시 버킷 개수 조정