Java HashMap의 내부 동작 - 이론편

해당 글은 Java8 기준으로 작성되었습니다.

 

https://potwings.tistory.com/56

Java HashSet, HashMap 내부 구조 & List보다 contains의 성능이 더 좋은 이유

이전 글에서 ArrayList와 HashMap의 contains의 성능을 비교해보았고

HashMap의 contains는 HashMap에서 get 후 null 체크를 진행하는 것을 확인하였다.

 

여기서 HashMap에서 get은 단순히 키값을 hashCode와 equals 메소드를 통하여

동등성과 동일성 비교 후 불러올 줄 알았으나 생각보다 메소드 내부가 복잡하였다.

 

이를 보고 나서 HashMap이 정확히 어떻게 동작하는지 알고 싶어졌고,

마침 HashMap의 내부 동작에 대해 잘 정리해주신 글이 있어

해당 글을 참고하여 정리해보고자 한다.

원글 : https://d2.naver.com/helloworld/831311

 

---

HashMap의 정의

HashMap은 키에 대한 해시 값을 활용하여 값을 저장하고 조회하는 associate array(Map)

라고 정의할 수 있다.

 

이 내용만 보았을 경우 단순히 객체의 hashCode값만 비교하는 것인가? 라고 생각할 수 있다.

허나 String와 POJO(Plain Old Java Object)에 대한 완전한 해시함수는 불가하다.

(완전한 해시함수 - 객체에 대해 equals가 false일 경우 둘의 hashCode가 일치하지 않게하는 함수)

 

아닌데? 가능한데? 라고 생각한다면 내용 확인

만일 완전한 해시함수가 존재하더라도 hashCode의 결과값은 int(2^32)이다.

허나 String과 POJO는 2^32보다 더 많은 종류의 객체를 생성할 수 있으므로 불가능하다.

 

만일 2^32개로 가능하다 치자.

그러면 HashMap에서 O(1)의 성능을 보장하기 위해서는 2^32개의 배열을 HashMap에서 보관하고 있어야하고

이는 메모리 낭비로 이어진다.

 

 

이러한 이유로 인해 해시함수를 사용하는 associate array 구현체들은

실제 해시 함수의 정수 표현범위보다 작은 M개의 원소가 있는 배열만을 사용한다.

배열의 index값은 아래와 같이 계산한다.

int index = X.hashCode() % M;

 

 

허나 실제 자바 코드를 확인해보니 인덱스를 아래와 같이 확인하고 있었다.

n = HashMap의 크기, hash = 키의 hash값

 

이를 보고 참고한 글이 잘못되었다 생각하였으나

더 확인해보니 X.hashCode() % M == (M - 1) & hash이 성립하였다.

나는 이와 관련해서 놀라운 증명을 찾아냈으나 여백이 부족하여 적지 않는다.

다음 글에서 자세히 설명하겠으나 HashMap의 크기(M)는 항상 2^n이다.

2^n - 1을 이진수로 표현하면  0111...111와 같이 이진수의 n자리 이하의 수들이 모두 1이다.

이 수와 hash값을 AND연산을 진행할 경우

이진수로 변환한 hash값에서 n자리 이하의 수들이 AND 조건에 부합하여 결과값에 포함될 것이다.

 

hashCode = 13, M = 8일 경우를 예시로 들어 확인해보자.

hashCode와 M - 1을 이진수로 변환하면 아래와 같다.

1101(hashCode = 13)

0111(M - 1 = 7)

이에대해 AND연산을 진행하면 0101 즉 5가 되어 13 % 8 = 5 와 동일한 결과가 나온다.

 

 

위와 같이 index 값을 계산하면

서로 다른 hashCode를 가지는 객체가 1/M 확률로 같은 배열(해시 버킷)을 사용하게 되며

이를 해시 충돌이라 한다.

 

이러한 해시 충돌이 발생하여도 정상적으로 데이터를 조회할 수 있도록

Java의 HashMap은 Separate Chaining을 사용한다.

 

---

Separate Chaining이란

Separate Chaining은 각 배열마다 LinkedList의 첫부분을 저장해둔 후 동일한 인덱스의 값이 들어올 경우 기존 값을 뒤로 미룬 후 새로 들어온 값을 head로 사용하는 방식이다.

 

예시를 통하여 확인해보자,

A, B, C, D의 순서대로 값이 들어오고 HashCode 값은 A : 0, B : 1, C : 2M + 1, D : M + 1 이라고 가정하자.
이 경우 int index = X.hashCode % M을 통하여 계산한 HashMap에서의 index 값은 0, 1, 1, 1이 될것이다.

이를 Separate Chaining을 사용하여 저장할 경우 아래와 같이 된다.

출처 : https://d2.naver.com/helloworld/831311

 

---

정리

Java의 HashMap에서는 X.hashCode() % M으로 인덱스 계산 후

Separate Chaining을 활용하여 데이터를 저장하고 있었고,

필자가 처음 생각하였던 단순 equals, hashCode의 비교보다 더 효율적으로 동작되고 있었다. 

 

 

다음 글에서는 Java에서 HashMap을 코드로 어떻게 구현해두었는지

또 그 HashMap에 Separate Chaining이 어떻게 구현되어 있는지 알아보도록 하자.

 

 

---

관련 포스팅

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