Java의 Collections Deep Dive - 1 : HashMap이란?

안녕하세요,

오랜만에 블로그를 적어봅니다!

 

최근 Redis의 Hash 자료구조를 비롯해 여러 Hash계열 자료구조를 사용하면서 내부적인 구현에도 조금씩 차이가 있다는 점을 알게 되었습니다!  또한 평소 Stream이나 Lambda를 사용할 때 Collections이라는 인터페이스에 대해 다소 이해가 부족한 것 같아 여러 기술블로그를 참고하여 학습하고 정리한 것을 포스팅하고자 합니다.

 

Map<K, V>에 대해서

우선 자바의 Collection이란, 데이터의 집합, 그룹을 의미한다.

 

이중 Map은 Interface이며, 엄연히 Collection 인터페이스를 상속받는 것은 아니다.

이는 구조상의 차이 때문이지만, Map 인터페이스 역시 Collection의 구성원 중 하나이다.

 

Map이란, key-value로 구성된 Entry 객체를 저장하는 구조를 갖고 있으며, key, value 각각은 모두 객체이다.

다시 말해, key, value는 모두 primitive type일 수 없다는 의미이다.

 

또한, 하나의 key에 value가 매핑되는 구조이다.

이때 key는 value를 식별하기 위한 식별자의 역할을 하므로, key는 중복되는 값을 가질 수 없다.

 

하지만, Map<K,V>는 인터페이스이므로, 내부적인 구현에 대해서는 정의하지 않고 있다.

 

key-value 구조를 내부적으로 어떻게 구현할 수 있을까?

 

결국은 특정 key에 맞게 value를 저장할 수 있어야 한다.

 

 

왜 HashMap인가?

value를 저장하기 위한 가장 단순한 자료구조를 떠올렸을 때 List가 있다. 

value를 List에 저장하고, List의 Index값을 Key로 사용한다면 key-value 형태의 매핑된 구조를 달성할 수 있다.

 

하지만, List의 Index는 숫자형 자료구조이므로, 숫자를 제외한 다른 문자를 key로 사용하기는 어렵다.

 

따라서 HashMap에서는 특정 key를 Hash함수를 이용하여 중복되지 않는 숫자로 변환한 후에 index로 사용하여 값을 저장하도록 한다.

 

 

해시 충돌이란?

Map은 서로 다른 두 value에 대해, 어떠한 key값(정확히는 key.hashCode()) 값이 서로 다름을 보장해야 한다.

 

hash함수를 이용하더라도 결국 모든 type의 key를 전부 커버할 수는 없다. 

아래의 코드를 보자.

 

 

Java에서 기본적으로 제공하는 hashCode() 함수의 반환값은 int이다. 

int는 32비트 정수 자료형이며, 만약 2^32보다 더 많은 경우의 수를 가진 type이 있다면(ex. String), 이는 hash 함수로 모두 표현할 수 없다.

 

결국 key-value 구조의 데이터의 수가 점점 늘어날 수록, hash 함수의 결과가 중복되는 현상이 발생하는데, 이를 해시 충돌이라고 한다.

 

 

해시 충돌을 해결하는 방법

이러한 해시 충돌을 해결하기 위해, 크게 2가지의 해결 방법이 있다.

 

1. Open Addressing

2. Seperate Chaining

 

하나씩 살펴보자.

 

Open Addressing이란?

Open Addressing이란, 해시 충돌 발생 시 새로운 hash 주소를 계산하여 저장하는 방식을 말한다.

 

크게 Linear Probing, Quadratic Probing, Double Hashing을 적용할 수 있다.

 

Seperate Chaining이란

해시 테이블의 value를 담는 bucket을 Linked-list나 Tree같은 자료구조를 이용해 구성한다.

해시 충돌 발생 시 같은 hash(key) 값에 대해 chain한 방식으로 연결하여 저장하게 된다.

 

결과적으로 Java의 HashMap에서는 Seperate Chaining 방식을 채택하고 있다. 

 

두 방식의 Worst Case는 모두 O(n)이다. 데이터의 개수가 적다면 Open Addressing이 연속된 공간에 데이터를 저장하므로 cache hit ratio가 훨씬 좋을 것이다. 하지만, 데이터의 수가 많아진다면 그 값이 현저하게 떨어진다.

다시 말해, Worst Case의 발생 빈도가 더욱 높아지는 현상이 발생한다.

 

HashMap에서 삭제도 굉장히 빈번하게 이루어지는데, Open Addressing 방식에서는 삭제 처리 역시 번거롭다.

 

 

Java 8 이후 HashMap에서는 Red-Black Tree를 이용한다.

Seperate Chaining 방식을 이용할 때, 만약 해시 함수 값이 균일하게 분포되어 있다면 조회의 기댓값은 O(N/M)이다.

Java 8에서는 이러한 조회(탐색)의 비용을 줄이고자 트리를 사용하여 O(logN/M) 타임으로 절감하도록 구현되어 있다.

 

따라서 내부적인 구현을 살펴봤을 때, Entry 클래스 대신 Node 클래스로 구현되어 있다.

Node 클래스는 Entry 클래스와 내용은 같으나, 자식 클래스로 TreeNode가 있어 트리를 사용할 수 있다.

 

 

TreeNode의 내부 구현에서 red-black tree로 구현되어 있음을 확인할 수 있다.

 

 

무조건 트리를 사용하면 이득인가?

그렇다면, 과연 트리를 사용하는 것이 무조건 이득일까? 해당 방식에도 단점은 있다.

 

트리는 기본적으로 Linked List 대비 메모리 사용량이 많다.

 

또한, Seperate Chaining 역시 여러 개의 데이터가 중첩되는 상태까지 도달하려면 어느 정도의 데이터가 있어야 한다.

즉, 데이터의 수가 적을 때에는 굳이 Linked List를 사용하지 않을 이유가 없다. 

 

이를 위해, HashMap에서는 기본적으로 LinkedList를 활용하되, 

한 해시 버킷에 8개의 key-value 쌍이 모이면 LinkedList를 Tree로 변경하는 Treeify 작업이 수행된다.

 

반대로, Tree에서 해당 버킷에 있는 데이터를 삭제하여 한 해시 버킷에 6개의 key-value 쌍으로 감소한다면 Linked List로 재변경하는 Untreeify 작업이 수행된다.

 

두 값에 대해 2만큼의 차이를 둔 이유는 어떠한 key-value 값이 반복적으로 삽입/삭제되는 경우 변환 과정이 반복되어 성능 저하로 이어질 수 있기 때문이다.

 

해시 버킷의 Resizing

해시 버킷의 수가 적다면 메모리를 아낄 수 있지만, 해시 충돌의 가능성이 높아져 성능이 저하된다.

HashMap은 key-value쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 수를 2배 증가시켜 해결한다.

 

이러한 해시 버킷의 기본값은 16이며,

버킷의 수를 확장시키는 임계점의 기본값은 현재 데이터 개수가 해시 버킷의 개수 중 75%인 시점이다.

 

이는 필요에 따라, 아래와 같이 생성자 parameter 값을 통해 직접 지정할 수 있다.

 

 

보조 해시 함수

어떠한 key에 대해 index를 계산하기 위한 해시함수의 일반적인 형태는 아래와 같다. 

이때 M값은 해시 버킷의 개수가 되는데, M값이 소수일 때 가장 균등한 분포를 갖게 된다.

int index = key.hashCode() % M;

 

하지만 Java의 HashMap은 2^N개의 버킷 수를 가지므로, 별도의 보조 해시 함수를 통해 균등한 분포를 가질 수 있도록 한다.

 

즉 보조 해시 함수란, key의 해시값을 변형하여 해시 충돌 가능성을 줄이는 역할을 한다.

 

 

구현되어 있는 해시 함수를 보면, 상위 16비트 값을 XOR 연산하는 단순한 형태를 가진다. 

이는 기본적으로 데이터의 양이 많아지면 Tree 구조로 변환하여 해시 충돌시 발생되는 성능 문제를 완화시킬 수 있고,

통계적으로 위와 같은 해시함수를 적용했을 때 균등 분포에 가까워지는 경우가 많아 위와 같은 형태로 구성되었다고 한다.

 

 

Reference

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

https://dev.gmarket.com/13