[자바] HashMap 동작 원리 정리

자바에서 HashMap은 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array입니다.

• 연관 배열(associate array) : 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료 구조

데이터를 저장할 버킷을 찾는 방법

HashMap은 객체의 hashCode() 메서드의 반환 값을 사용한 hashCode() % BUCKET_SIZE 수식을 사용하여 데이터를 저장/조회를 할 버킷 위치를 계산합니다. 위 수식을 사용하여 데이터를 BUCKET_SIZE 내의 위치에 값을 저장할 수 있게 됩니다.

해시 값 충돌이 발생한다면?

보통 Hash 값 충돌이 발생하면 개방 주소법, 체이닝 기법을 사용하여 충돌을 해결한다고 알려져 있습니다.

• 개방 주소법 : 충돌이 발생하면 다른 버킷에 데이터를 저장
• 체이닝 : 각 버킷은 연결 리스트의 헤더를 가리키고, 충돌이 발생하면 연결 리스트에 데이터를 저장

자바의 HashMap은 이 중에 체이닝 기법을 사용하여 충돌을 해결합니다. 다만 특이한 점이 하나 있습니다. 특정 버킷에 데이터 개수가 일정 개수 이상이 되면 연결 리스트에서 트리로 자료 구조를 변경하여 탐색 시간을 줄인다는 것 입니다. 자바 8에서는 특정 버킷에 8개의 데이터가 저장되면 트리로 변경하고, 6개 이하인 경우 연결리스트로 다시 변경합니다. 자료 구조 변경 기준을 8과 6으로 2개의 차이가 나도록 한 이유는 만약 어떤 동일한 키 값이 반복적으로 삽입/삭제가 되는 경우에 불필요한 자료 구조 변환 작업이 일어나기 때문입니다.

해시 버킷 크기의 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만, 해시 충돌로 인해 성능상 손실이 발생하게 됩니다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정한 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘리는 방식으로 동작합니다.

해시 버킷 개수의 기본값은 16이고 최대 개수는 2^30개이고. 데이터의 개수가 임계점이 이를 때마다 버킷 개수의 크기를 2배식 증가시킵니다.

해시 버킷 크기를 2배로 확장하는 임계점은 데이터 개수가 load factor * 현재 해시 버킷 개수에 이를 때입니다. load factor는 생성자를 통해 지정할 수 있으며, 기본값은 0.75입니다.

다만, 버킷의 개수가 2배로 증가할 때마다 모든 데이터를 읽어서 새로운 체이닝을 구성해야 하므로 저장될 데이터의 개수가 예상된다면 생성자 인자를 통해 사이즈를 지정하여 불필요한 재구성 과정을 줄이는 것이 좋습니다.

보조 해시 함수를 이용한 해시 값의 균등 분포

보통 해시에서 버킷의 위치인 X.hashCode() % BUCKET_SIZE을 계산할 때 BUCKET_SIZE가 소수인 경우에 값이 균등하게 분포할 수 있고, 2ⁿ을 사용하는 경우 충돌이 쉽게 발생할 수 있다고 알려져 있습니다.(2ⁿ 으로 버킷 사이즈로 사용하는 경우 하위 n개의 비트만 사용하여 버킷 위치를 사용하게 되어 비효율적입니다.)

그래서 2ⁿ 으로 버킷의 사이즈를 해시 맵은 충돌을 줄이기 위해 보조 해시 함수를 사용합니다. 보조 해시 함수란 해시값을 변형하여 충돌 가능성을 줄이는 것 입니다. 자바 8의 HashMap 보조 해시 함수는 다음과 같은 로직으로 구성되어 있습니다.

// 상위 16비트 값을 XOR 연산
hash(Object key) { 
    int hash; 
    return (key == null) ? 0 : (hash = key.hashCode()) ^ (h >>> 16); 
}

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