HashMap은 어떤 구조일까?

우리는 종종 Key - Value 구조의 HashMap을 사용한다. HashMap은 Key 중복이 없어 중복을 거르고 Key 값으로 빠르게 값을 찾아오기에 조회하는데에 이 점이 있다.

 

필자는 본 내용을 Map에 대한 사전 지식에 대해 다 갖고 있다는 전제하에 글을 써볼까 한다. 

 

HashMap이 중복 key를 걸러낼 수 있는 이유

자바는 모든 객체마다 고유한 hashcode를 갖는다. 이 hashcode는 해싱 알고리즘을 이용하여 만들어낸 코드로 내부 구현은 객체의 주소를 이용하여 만들어진다. 

public class HashEx1 {

    public static void main(String[] args) {
        String str1 = "hello";
        String str2 = "world";

        System.out.println(str1.hashCode()); // 99162322
        System.out.println(str2.hashCode()); // 113318802
    }
}

실제로 출력해보면 서로 다른 hashcode를 출력한다는 것을 알 수 있다.

 

내부 구현을 보면 hash는 default가 0인 int형 변수이고 값의 주소값을 갖고 위 사진과 같은 구조로 hashcode를 int형으로 반환해주는 것을 알 수 있다.

 

그렇게 해서 HashMap은 hashcode를 이용해 중복된 key를 제거할 수 있는 것이다. 그렇다면 HashMap은 어떠한 방식으로 값을 갖고 있고 조회하고 있을까?  그리고 거기서 발생할 수 있는 문제에 대해 살펴보자

 

데이터를 O(1)만에 가져올 수 있는 HashMap

해시를 이용한 데이터 탐색은 내부적으로 O(1)이라고 책이나 여러 블로그를 보면 알 수 있다. 그렇다면 왜 그런 것일까? 해시맵은 내부적으로 LinkedList나 TreeNode로 이루어져 있다. 그치만 이해하기 쉽게 본 내용에선 테이블 형태로 보여주겠다.

 

다음 사진은 N개의 버킷이 담겨있는 해시 테이블이다. 버킷은 꼭 하나의 slot을 갖고 있고 이 slot에 데이터가 저장된다. 그래서 bucket[0][0]의 형식으로 데이터를 조회해 갖고 올 수 있는데, 내부적으로는 TreeNode를 통해 구현 되어 있기에 getNode를 통해 hash값과 key값을 갖고 루트 노드를 찾아본다. 만약에 아니라면 Node를 순회하며 해당 데이터를 찾아 반환해준다. 

 

내부 코드이다. 보면 이해가 쉬울 것 같아 가져왔다. (나름 이해하기 쉽게 코드가 짜여있다.....)

 

그렇다면 왜 TreeNode로 구현이 되있는가와 순회해서 가져오는 경우는 어떤 경우인지 알아보자.

 

해시 분포와 충돌

HashCode는 완벽하게 객체의 중복을 다 막아줄 수 없다. 그렇기 때문에 HashTable에는 HashCode가 다른 객체임에도 같아 충돌 나는 경우에 대해 대비해야한다.

 

동일하지 않은 객체 A, B가 있을 때 A.equals(B)가 거짓일 때 A.hashCode() != B.hashCode())가 성립한다면 완전 해시 함수라고 한다. 

 

하지만 HashCode는 아까 말했다싶이 int형으로 만들어진다. 32비트의 자료형이기 때문에 완전한 자료 해시 함수를 만들기란 쉽지 않다. 2^32 보다 많은 객체가 있다고 가정했을 때 각 객체마다 고유한 hashCode를 만들어 내기란 불가능일 것이다. 그렇기 때문에 HashMap에서는 완전한 해시함수를 사용할 수 있는 것은 아니다. 또한 String과 POJO같은 경우에는 완전한 해시 함수를 만들기란 더더욱 불가능이다. 그렇기 때문에 HashMap을 포함한 해시 함수를 이용하는 associative array 구현체에서는 메모리 절약을 위해 실제 해시 함수의 표현 정수 범위 보다 작은 M개의 원소가 있는 배열을 사용한다.

 

그래서 해시코드의 나머지 값을 이용해 버킷 인덱스 값으로 사용한다.

int index = A.hashcode() % m;

이와 같은 방식을 사용하면 서로 다른 해시 코드를 갖는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다. 해시 함수가 얼마나 해시 충돌을 회피하도록 잘 구현되었느냐에 상관없이 발생하는 또 다른 종류의 해시 충돌이 되는 것이다. 

 

이런 경우 보통 두 가지 방식이 존재하는데, Open Addressing과 Separate Chaining이다.

 

• Separate Chaining

Separate Chaining 방식은 동일 해시값을 유지하고 해결하는 방식으로 동작한다. 위 그림처럼 해시 충돌이 발생할 경우에 기존에 있던 값에 앞에 새로 추가되는 것을 알 수 있다. 이때 방식은 보통 LinkedList나 Tree 방식으로 동작한다. 데이터의 개수가 많아진다면 List보다 Tree를 사용하는 것이 더 좋다.

 

기본적으로 삽입 삭제 연산이 빠르다는 장점이 있다.(LinkedList로 구현되기 때문) 하지만 캐시 성능은 떨어지게 된다. 그리고 사용하지 않는 slot이 생겨 공간 낭비가 있다.

 

• Open addressing

데이터를 삽입할 때 해당 버킷에 데이터가 담겨있다면 다른 해시 버킷에 삽입하는 방식으로 동작한다. separate 방식에 비해 확실히 메모리를 덜 쓰지만 해시 함수로 얻은 주소가 아닌 다른 주소에 저장된다.

 

하나의 테이블만을 사용하여 저장하기 때문에 메모리 공간을 덜 차지한다. 하지만 삽입 삭제에 성능이 좋지 않고(클러스터링이 발생하여 공간을 찾기위한 탐색시간이 길어지고 이는 성능을 떨어트린다.) 그리고 데이터가 많은 경우에는 L1, L2 캐시 적중률이 떨어져 캐시 성능이 떨어진다. 

 

마지막으로 두 가지 방식 모두 조회 시 O(M)의 시간복잡도를 갖는다. 

Java 8에서는 Seperate Chaining방식을 사용한다. 

이유는 간단하다. HashMap에서는 삽입 삭제 연산이 자주 일어난다. 그렇기 때문에 비교적 삽입 삭제 연산이 성능이 최적화된 Separate Chaining방식을 많이 사용한다.

또한, Java 8에서 부터는 LinkedList와 데이터가 8개 이상인 경우엔 red-black-tree를 이용하여 separate Chaining을 구현해 놨다. 

 

정리

우리는 HashMap에 대해 깊게 들어가 학습을 해보며 자바는 해시 충돌이 일어나는 경우 어떻게 문제를 최소화 하는지에 대해 학습하였다. 하지만 최소화라는 것에 주목해보자, 결국 해결은 아니라는 것이다. 

결국 해시 충돌은 데이터가 많아지며 일어날 수 밖에 없지만 적어도 개발자의 실수로 발생하는 해시 충돌을 없애 해시 충돌을 최소화 해야한다. 

그러기 위한 노력은 대표적으로 equals와 hashcode의 재정의이다. 이 내용은 매우 중요한 내용이니 독자들은 꼭 이펙티브 자바에서 이 내용을 찾아 읽어보기 바란다. 

 

Reference.

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

https://yoongrammer.tistory.com/82

[자료구조] 해시 테이블 (Hash Table)

https://hwannny.tistory.com/94

HashMap은 탐색시 어떻게 O(1)의 성능을 낼까?