『Java』 HashMap은 어떤 원리로 동작하는가

HashMap은 자주 사용하는 컬렉션 중 하나다.

키와 값을 쌍으로 저장하며 데이터의 삽입, 삭제, 검색이 평균적으로 O(1) 시간 복잡도를 갖는 자료구조다.

HashMap의 내부 동작 원리와 해시 충돌 해결 방법에 대해 알아보자.

 

 

HashMap 개념

HashMap은 키(Key)와 값(Value)이 1:1로 매핑되는 자료구조다. 여기서 키는 중복을 허용하지 않지만 값은 중복될 수 있다.

내부적으로 배열을 사용하며 각 배열의 요소를 버킷(bucket)이라고 한다.

키를 해시 함수에 통과시켜 해시 값을 얻고 해시 값을 이용해 버킷 배열의 인덱스를 결정한다.
일반적으로 해시 함수는 hashcode() % M 형태로 계산되기에 서로 다른 키가 동일한 인덱스를 가리키는 해시 충돌(hash collision)이 발생할 수 있다.

 

 

해시 충돌 해결 방법

해시 충돌을 해결하기 위해 두 가지 주요 방법이 있다.

 

Open Addressing, 충돌이 발생하면 인접한 다른 버킷을 탐색하여 빈 공간을 찾는다.

Separate Chaining, 충돌이 발생한 버킷에 노드들을 연결 리스트 형태로 저장한다.

 

Java의 HashMap은 Separate Chaining을 사용하며 버킷 내에 연결 리스트를 사용하여 동일한 인덱스의 여러 엔트리를 관리한다. 또한, 연결 리스트의 길이가 일정 수준을 넘어서면 성능 향상을 위해 트리(Tree) 구조로 변환한다.

 

 

HashMap 내부 구조

HashMap은 내부적으로 다음과 같은 구조를 가진다.

 

위 Node에서 키, 값, 해시 값, 그리고 다음 노드를 가리키는 참조를 포함한다.

해시 값을 계산할 때는 키의 hashCode() 메서드를 사용하며 Java 8에서는 해시 충돌을 줄이기 위해 아래와 같은 보조 해시 함수를 사용한다.

 

보조 해시 함수는 해시 코드의 상위 비트를 하위 비트와 XOR 연산하여 해시 값을 균일하게 분포시킨다.

 

 

데이터 삽입 과정

데이터를 삽입할 때의 과정은 다음과 같다.

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 버킷 인덱스를 결정한다.
3. 해당 버킷에 이미 노드가 존재하는지 확인한다.
   • 존재하지 않으면 새로운 노드를 추가한다.
   • 존재하면 키가 동일한지 확인하고, 동일하면 값을 업데이트한다.
   • 키가 다르면 연결 리스트의 끝에 새로운 노드를 추가한다.
4. 연결 리스트의 길이가 일정 수준(TREEIFY_THRESHOLD)을 넘으면 트리 구조로 변환한다.

 

 

HashMap 리사이징

HashMap은 용량(capacity)과 부하율(load factor)을 기반으로 자동으로 크기를 조정한다. 부하율은 HashMap에 저장된 엔트리 수가 용량에 얼마나 가까워졌는지를 나타내는 값이며 기본값은 0.75이다. 이는 저장된 엔트리 수가 용량의 75%를 초과할 때, HashMap의 용량을 두 배로 늘린다는 의미다.

 

리사이징은 해시 충돌을 줄이는 역할을 한다. 새로운 용량으로 버킷 배열을 재생성하고 기존 엔트리들을 재해시(rehashing)하여 배치함으로써 해시 충돌을 최소화한다.