Java HashMap은 어떻게 동작하는가?

원문 작성일: 2014.07.04

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

 

Java HashMap ?

• HashMap은 Java Collections Framework에 속한 구현체 클래스다.
• Java Collections Framework는 1998년 12월에 발표한 Java2에서 정식으로 선보였다.
• Map 인터페이스 자체는 Java5에서 Generic이 적용된 것 외에 처음 선보인 이후 변화가 없다.
• 하지만, HashMap 구현체는 성능을 향상시키기 위해 지속적으로 변화해왔다.

이 글의 내용은,

어떤 방식으로 HashMap 구현체의 성능을 향상시켰는가.

Amortized Constant Time을 위하여 어떻게 해시 충돌(hash collision) 가능성을 줄이고 있는가.

 

HashMap과 HashTable

공통점

1.  Java의 API 이름이다.
2.  Map 인터페이스를 구현하고 있다.
3.  정의 : '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array(= Map, Dictionary, Symbol Table)'

차이점

1.  HashTable은 JDK1.0부터 있던 Java의 API이다 / HashMap은 Java2의 Java Collections Framework에 속한 API이다.
2.  HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 HashTable에 비해 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
3.  HashTable에 반해, HashMap은 지속적으로 개선되고 있다

(HashTable은 JRE1.0, JRE1.1 환경에 하위 호환성을 제공하기 위함이므로 기능, 성능을 비교하는 것은 큰 의미가 없다)

 

해시 분포와 해시 충돌

 완전한 해시 함수(perfect hash functions) : X.equals(Y)가 '거짓'일때, X.hashcode() != Y.hashCode()인 해시 함수.

 

Boolean같이 서로 구별되는 객체의 종류가 적거나, Number 객체는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있다.

하지만, String이나 POJO에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.

 

적은 연산만으로 빠르게 동작할 수 있는 완전한 해시 함수가 있다 하더라도 사용할 수는 없다.

hashCode() 메소드가 반환하는 값의 자료형은 int(32비트 정수)인데,

1. 논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있으며
2. O(1)을 보장하기 위해 원소가 2^32인 배열을 모든 HashMap이 가지고 있어야 하기 때문이다.

따라서, 메모리 절약을 위해 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소가 있는 배열만을 사용한다.

이를 위해 다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.

int index = X.hashCode() % M;

이 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다.

이는 해시 함수의 구현 방식과 상관없이 발생할 수 있는 또 다른 종류의 해시 충돌이다.

이에 대한 대응 방법으로 개방주소법(Open Addressing)과 분리연결법(Separate Chaining)이 있다.

 

개방주소법(Open Addressing)

• 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 삽입하는 방식
• 데이터 저장/조회 시 Linear Probing, Quadratic Probing 등의 방법을 사용한다.

분리연결법(Separate Chaining)

• 각 해시 버킷 배열의 인자들은 링크드 리스트로 이루어져 있다.

둘 모두 Worst Case O(M)이다.

Open Addressing은 Separate Chaining에 비해 캐시 효율이 높기 때문에 데이터 개수가 적으면 Open Addressing이 유리하다. 하지만 배열의 크기가 커지면 L1, L2 캐시 적중률(hit ratio)가 낮아지기 때문에 캐시 효율의 장점은 사라진다.

 

Java HashMap이 사용하는 방식은 Separate Chaining이다.

1.  Open Addressing은 데이터 삭제에 있어 효율적이기 어렵다.
2.  데이터가 일정 개수 이상으로 많아지면 Separate Chaining이 더 빠르다.
3.  Separate Chaining 방식의 경우 해시 충돌이 덜 생기도록 (보조 해시 함수 등을 이용하여) 잘 '조정'하면 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.

 

Java 8 HashMap에서의 Separate Chaining

 만약 객체의 해시 함수 값이 균등 분포(uniform distribution) 상태라고 할 때,

get() 메서드 호출에 대한 기댓값은 E(N/M)이다.

그러나 Java8에서는 이보다 더 나은 E(log N/M)이다.

데이터 개수가 많아지면, Separate Chaining에서 링크드 리스트 대신 트리를 사용하기 때문이다.

Java8 HashMap에서는 키-값 쌍의 수가 6개까지는 링크드 리스트, 8개부터는 트리를 사용하도록 상수로 정해져있다.

(2개의 격차를 둔 이유는 어떤 한 키-값 쌍이 반복적으로 삽입/삭제되는 경우 자료구조 변환에서 오는 성능 저하를 피하기 위해서이다)

 

Java8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다.

Node 클래스는 Java7의 Entry 클래스와 내용이 같지만,

링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java7 HashMap과 다르다.

 

이때 사용하는 트리는 Red-Black Tree인데, Java Collections Framework의 TreeMap과 구현이 거의 같다.

트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다.

해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데,

Java8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결한다.

(TreeNode에서 어떤 두 키의 comparator 값이 같다면 서로 동등하게 취급된다. 그런데 어떤 두 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 임의로 대소 관계를 지정할 필요가 있는 경우가 있다)

 

해시 버킷 동적 확장

 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다.

그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다.

 

그런데 이렇게 버킷 개수가 두 배로 증가할 때마다,

모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다.

HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.

 

해시 버킷의 기본값은 16이고, 최대 개수는 2^30개다.

해시 버킷 크기를 두 배로 확장하는 임계점은 현재의 데이터 개수가 load factor * 현재의 해시 버킷 개수에 이를 때다.

load factor는 0.75 즉 3/4이다. 이 load factor 또한 HashMap의 생성자에서 지정할 수 있다.

 

기본 생성자로 생성한 HashMap을 이용하여 많은 양의 데이터를 삽입하면, 최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 키-값 쌍 데이터에 접근해야 한다. 즉 수행 시간이 2.5배 길어지는 것이다.

따라서, 성능을 높이려면 HashMap 객체를 생성할 때 적정한 해시 버킷 개수를 지정해야 한다.

 

그런데 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다.

해시 버킷의 개수 M이 2^a 형태가 되기 때문에,

index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다.

즉, 해시 함수가 32비트 영역을 고르게 사용하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.

이 때문에 보조 해시 함수가 필요하다.

 

보조 해시 함수

 index = X.hashCode() % M을 계산할 때 사용하는 M값은 소수일 때 index값 분포가 가장 균등할 수 있다.

그러나 M값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index값 분포가 가급적 균등하도록 해야 한다.

 

보조 해시 함수(supplement hash function)의 목적은 키의 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것이다.

JDK1.4에 처음 등장한 보조 해시 함수는 Java8부터 새로운 방식으로써 사용되고 있다.

 

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Java8 HashMap 보조 해시 함수는 Java7보다 훨씬 더 단순하다.

상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다.

1. Java8에서는 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다.
2. 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다.

 

String 객체에 대한 해시 함수

 String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.

JDK1.1에서는 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산하여 누적한 값을 문자열에 대한 해시 함수로 사용했다.

그러나 이 방식은 앞 부분이 동일하게 구성되는 URL에 있어 해시 값이 같아지는 빈도가 높아지는 문제가 있다. 

따라서 이런 방식은 곧 폐기되었고, 다음의 방식을 Java8까지도 계속 사용하고 있다.

public int hashCode() {
    int h = hash;
    if(h == 0 && value.length > 0) {
        char val[] = value;
        
        for(int i=0; i<value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다.

32는 2^5이므로 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다.

따라서 N에 31을 곱한 값은 (N << 5) - N과 같다.

 

마치며

 웹 애플리케이션 서버의 경우에는 HTTPRequest가 생성될 때마다, 여러 개의 HashMap이 생성된다.

수많은 HashMap 객체가 1초도 안 되는 시간에 생성되고 또 CG(garbage collection)의 대상이 된다.

컴퓨터 메모리 크기가 보편적으로 증가하게 됨에 따라, 메모리 중심적인 애플리케이션 제작도 늘었다.

따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다고 할 수 있다.