HashMap에서 Hash 충돌이 발생하면 어떤 일이 일어나나요?

[eunjungL]

.

[Chocochip101]

Java에서 HashMap을 사용할 때 해시 충돌이 발생하면, 해시 충돌을 처리하기 위해 체이닝과 레드-블랙 트리가 작동합니다. 해시 충돌이란 두 개 이상의 키가 동일한 해시 값을 가지는 경우를 말합니다.

체이닝 (Chaining)

HashMap은 기본적으로 체이닝 방법을 사용하여 해시 충돌을 처리합니다. 체이닝에서는 각 버킷이 연결 리스트(또는 자바 8부터는 레드-블랙 트리)로 구현됩니다. 해시 충돌이 발생하면, 동일한 해시 값을 가지는 요소들은 같은 버킷의 연결 리스트에 추가됩니다.

해시 충돌 처리 과정

1. HashMap은 키의 해시 값을 계산하여 해당 버킷의 인덱스를 결정합니다.
2. 만약 동일한 해시 값을 가진 다른 키가 이미 존재하는 경우, 해당 버킷의 연결 리스트에 새로운 엔트리(키-값 쌍)를 추가합니다.
3. 이 연결 리스트를 순회하면서 키를 검색할 때, 해시 값이 동일한 키들 중에서 정확한 키를 찾기 위해 equals() 메서드를 사용하여 비교합니다.

레드-블랙 트리 (Red-Black Tree)

자바 8부터는 해시 버킷의 요소가 8개 이상을 초과하면, 해당 버킷의 연결 리스트를 레드-블랙 트리로 변환합니다. 레드-블랙 트리는 균형 잡힌 이진 검색 트리로, 요소를 추가하거나 검색할 때 평균적으로 O(log n) 시간 복잡도를 제공합니다.

레드-블랙 트리 전환

1. 버킷의 연결 리스트가 일정 길이를 초과하면, 해당 버킷의 노드들을 레드-블랙 트리로 변환합니다.
2. 트리로 변환된 버킷은 해시 충돌로 인해 동일한 해시 값을 가진 키들을 더 빠르게 검색할 수 있습니다.

HashMap의 초기 용적과 적재 기준(load factor)을 조정함으로써 성능을 조정할 수 있습니다. 적재 기준은 해시맵이 리사이즈를 수행할 시점을 결정합니다. 기본값은 0.75로, 이는 해시맵의 75%가 채워지면 자동으로 리사이즈가 수행된다는 의미입니다.