자바 HashMap의 구조 / HashTable / LinkedHashMap

자바에서 컬렉션이란 무엇인가?

Java Collection Class의 두 가지 주요 root interface는 아래와 같다.

1) Collection interface(java.util.Collection)

2) Map interface(java.util.Map)

 

https://techvidvan.com/tutorials/java-collection-framework/

 

 

HashTable

 

해시 테이블은 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킨다.

해시 테이블을 구현하는 방법에는 여러 가지가 있으나, 간단하면서 흔하게 사용되는 방식은 연결리스트(linked list)와 해시 코드 함수(hash code function)을 사용하는 것이다.

 

 

key와 value를 해시 테이블에 넣는 과정은 다음과 같다.

1. 키의 해시 코드를 계산한다.
   키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다.
2. hash(key)%array_length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
   물론 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있다.
3. 배열의 각 인덱스에는 key와 value로 이루어진 연결 리스트가 존재한다. key와 value를 해당 인덱스에 저장하는데, 충돌에 대비하여 연결 리스트를 이용해야 한다.
   여기서 충돌이란 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말한다.

 

 

키에 상응하는 값을 찾기 위해서는 주어진 키로부터 해시 코드를 계산하고, 이 해시 코드를 이용해 인덱스를 계산하는 과정을 반복한다.

그 다음엔 해당 키에 상응하는 값을 연결리스트에서 탐색한다.

 

충돌이 자주 발생한다면, 최악의 경우에 수행 시간은 O(N)이 된다. 하지만 일반적으로 해시에 대해 이야기할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정하여 이 경우 탐색 시간은 O(1)이다.

 

다른 구현 방법으로는 균형 이진 탐색 트리(balanced binary search tree)를 사용하는 방법이다.

이 경우에 탐색 시간은 O(logN)이 된다.

이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.

 

....

 

HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다.

HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다.

 

HashMap

HashMap는 Hash Function과 HashTable를 사용하기 때문에 List보다 빠르다.

List는 자료를 순서대로 저장하여 선형 검색을 해야 하기 때문에 검색에 O(n)이 걸린다.

HashMap은 Hash Function을 이용해 index를 만들어 저장하기 때문에 검색이나 삭제 시에도 index를 이용하여 O(1)이 걸린다.

 

 

* 시간 복잡도
next에서 h는 테이블의 크기이다. 잘 분배된 상황일수록 시간 복잡도는 O(1)이다.(테이블의 크기가 50이고 n이 50이라면 O(1))

	get	containsKey	next
HashMap	O(1)	O(1)	O(h/n)

 

 

HashMap의 구조

Open Addressing vs Separate Chaining

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

 

Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다. 

Separate Chaining에서 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)이다.

둘 모두 Worst Case O(M)이다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비하여 캐시 효율이 높다. 따라서 데이터 개수가 충분히 적다면 Open Addressing이 Separate Chaining보다 더 성능이 좋다.

하지만 배열의 크기가 커질수록(M 값이 커질수록) 캐시 효율이라는 Open Addressing의 장점은 사라진다. 배열의 크기가 커지면, L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문이다.

 

Java HashMap에서 사용하는 방식은 Separate Channing이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문이다.

게다가 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다.

반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 사용하여 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.

 

 

Java8 HashMap

 

Java 8 부터는 데이터의 개수가 많아지면, Separate Chaining에서 링크드 리스트 대신 트리를 사용한다.

실제 해시 값은 균등 분포가 아닐뿐더러, 균등 분포를 따른다고 하더라도 일부 해시 버킷 몇 개에 데이터가 집중될 수 있다.

그래서 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다.

 

링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다.

아래 코드블럭에서 보듯 Java 8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다.

트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

 

# Java8 HashMap의 TREEIFY_THRESHOLD와 UNTREEIFY_THRESHOLD

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

 

Java 8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다. Node 클래스 자체는 사실상 Java 7의 Entry 클래스와 내용이 같지만, 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java 7 HashMap과 다르다.

 

이때 사용하는 트리는 Red-Black Tree인데, Java Collections Framework의 TreeMap과 구현이 거의 같다. 트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다. 해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데, Java 8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결한다.

 

* Total Ordering : 임의의 두 원소를 비교할 수 있는 부분 순서 집합

** tieBreakOrder() : 클래스 명으로 먼저 비교하고, HashCode로 한번 더 비교

 

# Java8 HashMap의 Node 클래스

transient Node<K,V>[] table;


static class Node<K,V> implements Map.Entry<K,V> {  
  // 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다. 
}


// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {


        TreeNode<K,V> parent;  
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;   

        // Red Black Tree에서 노드는 Red이거나 Black이다.
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

...
}

 

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다. 이렇게 해시 버킷 개수를 늘리면

값도 작아져, 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.

해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두 배씩 증가시킨다.

버킷의 최대 개수는 2^30개다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다.

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

 

해시 버킷 크기를 두 배로 확장하는 임계점은 현재의 데이터 개수가 'load factor * 현재의 해시 버킷 개수'에 이를 때이다. 이 load factor는 0.75 즉 3/4이다. 이 load factor 또한 HashMap의 생성자에서 지정할 수 있다.

 

기본 생성자로로 생성한 HashMap을 이용하여 많은 양의 데이터를 삽입할 때에는, 최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 키-값 쌍 데이터에 접근해야 한다. 이는 곧 수행 시간이 2.5배 길어진다고 할 수 있다. 따라서 성능을 높이려면, HashMap 객체를 생성할 때 적정한 해시 버킷 개수를 지정해야 한다.

 

 

보조 해시 함수

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

 

# Java8 HashMap의 보조 해시 함수

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

 

위 코드에서 볼 수 있는 것처럼, Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다. Java 8부터는 Java 7보다 훨씬 단순한 방식의 보조 해시 함수를 사용하고 있다.

 

이유로는 두 가지가 있는데, 첫 번째는 Java 8에서는 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다.

두 번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아서 Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다. 두 번째 이유가 좀 더 결정적인 원인이 되어 Java 8에서는 보조 해시 함수의 구현이 변경되었다.

 

 

Conclusion

Java HashMap에서는 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용하며, Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다.

HashMap은 첫 등장 이후, 성능 향상을 위하여 꾸준하게 개선되어 왔다. JDK 1.4에서 처음 등장한 보조 해시 함수와 Java 8의 트리 노드가 대표적인 예다.

웹 애플리케이션 서버의 경우에는 HTTPRequest가 생성될 때마다, 여러 개의 HashMap이 생성된다. 수많은 HashMap 객체가 1초도 안 되는 시간에 생성되고 또 GC(garbage collection) 대상이 된다. 컴퓨터 메모리 크기가 보편적으로 증가하게 됨에 따라, 메모리 중심적인 애플리케이션 제작도 늘었다. 따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다.

 

 

 

LinkedHashMap?

 

HashMap을 사용하면 데이터를 넣을 때 key의 순서가 지켜지지 않는다.

만약 입력된 key의 순서가 보장되어야 한다면 LinkedHashMap을 사용하면 된다.

즉, 순서를 유지하는 HashMap이다. (자바 1.4버전부터 제공)

 

LinkedHashMap의 특징

• LinkedHashMap은 HashMap의 장점을 그대로 가지고 있기 때문에 get, put, remove, containsKey 메소드를 호출할 때 O(1)의 시간 복잡도를 갖는다.
• **doubly-linked-list로 모든 Entry를 유지한다.
• HashMap과 마찬가지로 동기화 처리가 되어있지 않기 때문에 multi-thread 환경에서 사용은 적절하지 않다.
  만약, 사용해야 하는 경우 외부에서 동기화처리되거나 아래처럼 동기화된 LinkedHashMap을 얻어올 수 있다.

Map map = Collections.synchronizedMap(new LinkedHashMap(...));

 

** doubly linked list

https://www.programiz.com/dsa/linked-list-types#doubly

 

 

참고) HashMap, LinkedHashMap, HashTable, TreeMap 정리 및 비교

HashMap

• 입력 순서를 보장하지 않는다.
• 검색기능은 O(1)의 시간복잡도를 가지며, 동기화(Synchronized) 지원하지 않음
• null Key 허용

HashTable

• 입력 순서를 보장하지 않는다.
• 검색기능은 O(1)의 시간복잡도를 가지며, 동기화(Synchronized)를 지원한다.
• null Key 허용 안함 (Null Pointer Exception 발생)
• HashMap보다는 느리다 하지만 동기화된 HashMap 보다는 빠르다.

LinkedHashMap

• 입력 순서를 보장한다.
• 검색기능 O(1) 시간복잡도, 더블링크드리스트 자료구조로 이루어져 있다.
• null Key 허용
• HashMap과 동일하게 좋은 성능을 가지지만 링크드리스트를 구성하고 있어야 한다.

TreeMap

• 입력 순서를 보장하지 않으며, 정렬된 순서로 저장되어 출력된다.
• 검색기능은 O(log(n))의 시간복잡도를 가지며, Red Black Tree 자료구조로 이루어져 있다.
• null Key 허용 안함 ( Null Pointer Exception 발생)

 

 

 

 

 

 

 

 

 

 

References

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

https://wonyong-jang.github.io/java/2020/10/16/Java-LinkedHashMap.html

Cracking the coding interview 6/E / 게일 라크만 맥도웰