java에서 사용하는 Hash Collision 해결 방법

목차

1. HashMap이란?
2. Hash Collision
3. java에서 Hash Collision을 해결하는 법
4. 결론
5. reference

 

1.  HashMap이란?

※ 들어가기에 앞서 이 블로깅은 java 8 버전 이상에서 Hash Collision 해결 방법에 대해서 설명하고 있음을 알려드립니다.

 

JDK 1.2부터 추가됐으며, Key와 Value를 가지는 Map 인터페이스를 구현하고 Key와 Value의 null 값을 가질 수 있으며 non thread-safe 한 Hash Table 기반 자료구조입니다.

put() 메서드를 사용해 데이터를 추가할 수 있으며 get() 메서드를 사용하여 기본적으로 O(1)의 탐색시간으로 데이터를 검색할 수 있는 특징을 가지고 있습니다.

 

HashMap에 데이터가 등록되는 과정을 조금 살펴보도록 하겠습니다. put() 메서드는 내부적으로 putVal() 메서드를 호출하여 데이터를 추가하게 되는데 이때 Hash Table의 size와 Key의 hash code 값을 & 비트 연산한 값을 Hash Table의 index로 사용하게 됩니다.

HashMpa의 put 메서드

HashMap의 putVal 메서드

 

 

이제 간략한 예제를 통해 HashMap의 데이터 추가와 조회를 해보도록 하겠습니다.

밑의 예제는 Key로 전화번호를 가지고 Value로 이름을 가지는 HashMap을 선언하여 한 사람이 여러 개의 핸드폰을 사용하고 있는 경우를 표현한 예제입니다.

실행 결과

 

이렇게 다른 Key와 같은 Value를 가지는 데이터는 Hash Table을 사용하는 자료구조인 HashMap에서 전혀 문제가 되지 않습니다.

하지만 특수한 경우 다른 Key를 가지지만 Hash Table의 size와 Key의 hash code를 & 비트 연산한 결괏값이 이미 Hash Table의 index로 사용 중인 경우에는 Hash Collision이라는 것이 발생하게 됩니다.

 

2.  Hash Collision

위의 예제처럼 동일하지 않은 객체에 대해서 hash code 값이 같지 않은 해시 함수를 완전 해시 함수(perfect hash function)라고 합니다.

 

하지만 현실적으로 완전 해시 함수를 만드는 것은 불가능합니다. 그 이유는

1. hash code는 32bit 정수 자료형인 int를 반환하는데 int 자료형 보다 더 많은 객체 수가 필요한 경우에는 결국에는 Hash Collision이 발생.
2. 32bit의 크기만큼 Hash Table의 size를 가지는 것은 자원 낭비가 엄청나게 심함.

그렇다면 Hash Collision을 해결하기 위해 어떤 방법들이 존재할까요? 대표적으로 Separator Chaining, Open Addressing 방식이 존재합니다. 그 중 java에서는 Separator Chaining 방식을 사용하여 Hash Collision을 해결하고 있습니다. (Open Addressing 방식은 저도 잘 모르는 관계로 다루지 않겠습니다.. ㅎ)

 

 

3.  java에서 Hash Collision을 해결하는 법

java 8 버전 이상에서의 Separator Chaining 방식은  기본적으로 Linked List를 사용하여 Hash Collision을 해결합니다. 하지만 특정 index에 대한 Hash Collsion의 횟수가 트리화 임곗값 - 1(TREEIFY_THRESHOLD, default value 8)과 같거나 크고 Hash Table의 size가 최소 트리화 용량(MIN_TREEIFY_CAPACITY, default value 64) 보다 크면 Linked List를 Red-Black Tree로 바꿔 검색 성능을 최적화하고 있습니다.

 

밑의 코드에서 PhoneBook 클래스는 Key와 Hash Table size의 & 비트 연산 결과가 같은 index를 반환하도록 hashCode() 메서드를 오버라이드 하여 하드코딩 한 코드입니다.

 

 

위 코드를 실행해 Hash Collision 발생 시 정말 Linked List를 활용하여 충돌을 해결하고 있는지 확인해 보도록 하겠습니다.

사진에서 빨간 네모 부분을 보시면 Hash Collision 발생 시 Node의 next가 null이면 next에 새로운 Node를 생성하여 연결해 주는 것을 볼 수 있습니다.

HashMap의 putVal 메서드에서 Hash Collision을 처리 코드

 

또한 밑의 사진처럼 특정 index에 대한 Hash Collision 횟수가 TREEIFY_THRESHOLD 상수 값에 1을 뺀 것 보다 크거나 같으면 treeifyBin() 메서드를 호출해 Hash Table을 resizing 하거나 Linked List -> Tree 구조로 바꾸는 것을 보실 수 있습니다.

Hash Table resizing 및 Tree 변환 코드

 

 

4.  결론

java 8 버전 이상부터는 hash code와 Hash Table의 size에 대한 & 비트 연산 시 동일한 index 결괏값이 나오는 경우 Hash Collision을 해결하기 위해 Linked List와 Red-Black Tree를 사용합니다. Hash Collision 발생 시 resizing과 Tree로 바꾸는 작업은 작은 비용이 아니기 때문에 동일하지 않은 객체에 대해서 같지 않은 hash code 값이 나오도록 hashCode() 메서드를 정확하게 재정의 해주어야 합니다.

 

5.  reference

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html