[Java] Java API HashMap은 어떻게 동작할까

✅ 이 글의 전반적인 내용은 아래의 글을 정리하여 작성하였음
https://d2.naver.com/helloworld/831311

해시 시리즈 3탄
이 글을 쓰기 위해 이전의 글을 써왔고, 해시에 대해 잘 알지 못한다면 참고하는 것도 좋을 것 같다https://2jinishappy.tistory.com/230

빠른 데이터 검색을 위한 Hashing과 Hash Table

https://2jinishappy.tistory.com/231?category=920680

Hash Table에서의 Collision Handling - Linear Probing, Separate Chaining

엄밀히 말하자면 이전에 다룬 것은 ADT Hash Table (Hash Table의 정의 및 연산에 대해 다룬 것)이므로, 이번에는 실제로 자바에서 어떻게 Hash를 구현하고 사용하고 있는지 알아볼 것 이다

Hash Table은 '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array'라고 할 수 있다. 이 연관배열을 구현하기 위해 C++에서는 map, Python에서는 dictionary, Java에서는 HashMap API를 지원하고 있다

그 중에서도 Java의 HashMap API는 Hash를 어떤 식으로 구현하는지, Open/Close Addressing 중 어떤 것을 사용하여 Collision을 방지하는지, 어떻게 probe 횟수를 줄이려고 했는지 알아보자
😲

1️⃣ HashMap과 HashTable

HashMap과 HashTable 모두 Java API 이름이다

	HashMap	HashTable
등장 시기	Java2	JDK 1.0
Map Interface 구현 여부	O	O
associative array 지칭 용어	Map	Dictionary
특징	- Java Collection Framework - 보조 해시 함수(Additional Hash Function)을 사용하여 Collision을 덜 발생시킴 - 지속적으로 개선되고 있음	- JRE 1.0, JRE 1.1 환경을 대상으로 Java App이 잘 동작하도록 하위 호환성 제공

아래의 코드는 HashTable(위)와 HashMap(아래)의 선언부를 나타낸다.

public class 8ccce55530bc3477c678dd9921b60f3e.gifHashtable<K,V> extends Dictionary<K,V>  
    implements Map<K,V>, Cloneable, java.io.Serializable {

public class 928b3cc3fe40d69cd06cbe7f5f3767f8.gifHashMap<K,V> extends AbstractMap<K,V>  
    implements Map<K,V>, Cloneable, Serializable {

 

2️⃣ 해시 분포와 해시 충돌

이전의 글에서 hash function을 사용하여 key값을 table 상의 index로 mapping시켜주었다
모든 서로 다른 key에 대해 hash function으로 변환된 key가 중복되지 않는 hash function을 perfect hash function이라 하고, 이것이 이상적인 해시 함수라는 것도 알아보았다

실제 Java에서는, Boolean같이 서로 구별되는 객체 종류가 한정되어 있거나 Integer, Long, Double같은 Number형 객체는 객체가 나타내려는 값 자체를 Hash 값으로 사용할 수 있기 때문에 perfect hash function의 대상이 될 수 있다(하지만 표현 가능한 객체의 수가 2^32개로 제한된다)
하지만 String 혹은 POJO에 대해 perfect hash function을 제작하는 것은 불가능하다

또한 모든 HashMap 객체에 대해 perfect hash function을 제공하기 위해 2^32개의 공간을 가진 배열을 할당하는 것은 낭비가 된다.
따라서 필연적으로 정수의 표현 범위보다 작은 크기의 배열을 사용하고 modular hash function을 통해 이를 mapping한다. modular hash function을 통해 변환되는 key값의 중복성을 완전히 제거할 수는 없기 때문에 collision handling을 어떻게 효율적으로 해주느냐가 관건이다

Open Addressing(Linear Probing, Uniform Probing 등)과 Separate Chaining 모두 Worst Case O(M)이다 (M = Hash Table의 크기)

앞으로 편의를 위해 N = 현재 HashMap에 저장된 key-value 쌍 개수(elements 수), M = Hash Table의 크기 라고 가정한다

Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Chaining에 비해 캐시 효율이 높아 데이터 개수가 충분히 적을 때에 한해 성능이 좋다는 장점이 있다.
하지만 배열의 크기가 커질 수록 L1, L2 캐시 적중률(hit ratio)가 낮아지기 때문에 적합하지 않다.

그래서 HashMap은 Separate Chaining 방식을 채택했다.
HashMap의 특성상 remove()가 매우 빈번하게 호출될 수 있는데, Open Addressing을 사용할 시 remove()에도 worst case O(M)이 소모되기 때문이다. 또한 저장된 elements 수가 증가할 수록 wost case 발생 빈도가 높아져 separate chaining에 비해 느려지게 된다.
Separate Chaining은 해시 충돌이 잘 발생하지 않도록 조정하는 방식을 통해 Worst Case(또는 가까운 일)이 발생하는 횟수를 줄였다.

3️⃣ Java8에서의 Separate Chaining을 사용한 HashMap 구현

이전 글에서는 Separate Chaining을 구현하기 위해 각 index마다 Linked List를 둔다고 했었는데, 이 경우 대략적으로 N/M probe가 필요하다고 했다

하지만 Java 8에서는 데이터의 개수가 많아지면 Linked List대신 Tree를 사용하여 이보다 나은 log (N/M)을 보장한다 ❗❗❗❗❗

(개쩐당)

시간복잡도 공부를 하면 N^3과 N^2.87의 차이도 어마어마하다는걸 아는데 ...
기댓값이 무려 다항시간에서 로그시간으로 줄어드는 것이다

실제 해시 값은 uniformly distributed도 아니고, birthday problem에 의해 일부 해시 버킷 몇 개에 데이터가 집중될 수 있기 때문에 데이터가 일정 개수 이상일 때에는 linked list 대신 tree를 사용하는 것이 성능상 이점이 있다고 한다

static final int TREEIFY_THRESHOLD = 8; 
static final int UNTREEIFY_THRESHOLD = 6; 

Linked List vs Tree의 선택은 하나의 해시 버킷에 할당된 key-value 쌍의 개수가 몇개? 라는 기준에 따라 결정된다.
Java8 HashMap에서는 하나의 해시 버킷에 8개의 key-value 쌍이 모이면 링크드리스트를 트리로 변경하고, 데이터가 삭제되어 8개에 이르면 다시 링크드 리스트로 변경한다.
(트리는 링크드리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드리스트의 worst case 수행 시간 차이 비교는 의미가 없기 때문)

8과 6으로 상수간에 '2'의 차이를 둔 것은, 차이가 1일 경우 6-7 혹은 7-8로 삽입/삭제가 빈번히 일어날 경우 불필요한 구조 변경이 반복되어 성능 저하의 원인이 될 수 있어서이다

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);
        }

        final TreeNode<K,V> root() {
        // Tree 노드의 root를 반환한다. 
        }

        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        // 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
        }


        // 순회하며 트리 노드 조회 
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
        final TreeNode<K,V> getTreeNode(int h, Object k) {}


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


        final void treeify(Node<K,V>[] tab) {
          // 링크드 리스트를 트리로 변환한다.
        }



        final Node<K,V> untreeify(HashMap<K,V> map) {
          // 트리를 링크드 리스트로 변환한다.
        }

        // 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {}
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}


        // Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
        final void split (…)
        static <K,V> TreeNode<K,V> rotateLeft(…)
        static <K,V> TreeNode<K,V> rotateRight(…)
        static <K,V> TreeNode<K,V> balanceInsertion(…)
        static <K,V> TreeNode<K,V> balanceDeletion(…)



        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        // Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
        }
    }

Entry 클래스 대신 Node 클래스를 사용하여 링크드리스트 대신 트리를 사용할 수 있도록 하위 클래스 TreeNode를 두었다
그리고, 이 때 사용하는 트리는 무시무시한 레드-블랙 트리이다 (elements의 삽입/삭제가 발생해도 balanced를 유지하기 위해)

이 때 사용되는 대소 판단 기준은 해시 함수 값이고, total ordering 문제를 해결하기 위해 tieBreakOrder() 메서드를 두었다 (해시 함수 값이 동일해도 임의로 대소 관계를 지정)

4️⃣ 해시 버킷의 동적 확장

해시 버킷(테이블)의 개수가 적다면 메모리 사용을 아낄 수 있지만, Collision이 자주 발생해 성능상 손실의 원인이 된다
그래서 HashMap은 elements 개수가 일정 개수 이상이 되면 해시 버킷의 size를 두 배로 늘리는데, 이렇게 하면 N/M의 값도 작아져 collision으로 인한 성능 손실 문제를 어느 정도 해결 가능하다

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

(최대 개수는 2^30)
하지만 rehashing 과정을 거칠 때 마다 기존의 저장된 모든 데이터를 다시 읽어 새로 저장해야 하는 문제가 있다
그래서 "저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우" 해당 HashMap 객체의 생성자 인자로 지정하면 불필요한 확장을 막을 수 있다

Java7 HashMap에서의 해시 버킷 확장

// 인자로 사용하는 newCapacity는 언제나 2a이다.
void resize(int newCapacity) {  
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // MAXIMIM_CAPACITY는 230이다.
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];


        // 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을
        // 새 해시 버킷에 저장한다.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }


    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 모든 해시 버킷을 순회하면서
        for (Entry<K,V> e : table) {
            // 각 해시 버킷에 있는 링크드 리스트를 순회하면서
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 해시 버킷 개수가 변경되었기 때문에
                // index 값(hashCode % M)을 다시 계산해야 한다. 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

이 때 확장의 임계섬은 현재 데이터 개수가 'load factor * 현재 해시 버킷 개수'에 이를 때 이다(load factor - 0.75)
기본 생성자로 HashMap을 생성하여 많은 양의 데이터를 삽입할 때 에는, 최적의 해시 버킷을 지정한 때 보다 약 2.5배 많이 element에 접근해야 한다(따라서 성능을 높이려면 HashMap 객체 생성 시 적정한 버킷 개수를 지정해주는 것이 좋다)

그런데 M이 소수일 때 collision 발생이 줄어드는 것에 반해 버킷 크기를 두 배씩 확장하게 되면 M이 2^a 형태가 되어서,

index = X.hashCode() % M

을 계산할 때 X.hashCode의 하위 a개 비트만 사용하게 된다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 설계되어도 2의 승수로 나누면 collision이 쉽게 발생할 수 있다

5️⃣ 보조 해시 함수

위에서 언급한 것 처럼 M 값이 소수일 때 index 값 분포가 가장 균등할 수 있지만, 동적 해시 확장으로 인해 그것이 불가능해지기 때문에 HashMap API에서는 별도의 보조 해시 함수를 두어 index 분포를 가급적 균등하게 했다
보조 해시 함수의 목적은 '키'의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것 이다

// Java7 HashMap에서의 보조 해시 함수
final int hash(Object k) {  
        // Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면
        // String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로
        // 해시 함수를 사용하도록 할 수 있다.
        // 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다.
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을 
        // 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이 
        // 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
        // shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서 
        // 최대한 값이 겹치지 않고 구별되게 한다.
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    
    
    
// Java 8 HashMap에서의 보조 해시 함수
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }  

Java7과 달리 Java8에서의 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 형태의 단순한 보조 해시 함수를 사용했다

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

위와 같은 이유로, 보조 해시 함수를 단순화하고 비트 연산을 적용하여 hash function의 수행을 더욱 빠르게 하였다

6️⃣ String 객체에 대한 해시 함수

마지막으로는 String 객체를 어떻게 number로 mapping하는지 알아보자 🥱
String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례하기 때문에, JDK 1.1에서는 빠른 수행을 위해 일정 간격의 문자에 대한 해시를 누적한 값을 해시 함수로 사용했었다
하지만 웹상의 URL은 길이가 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많기 때문에, 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있다.

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;
    }

따라서 Java8에서는 Honer's method를 이용하여 String을 int형태로 hash하는 방식을 사용한다

31을 사용하는 이유는, ①31이 소수이며 ②어떤 수에 31을 곱하는 것은 빠르게 계산이 가능하기 때문 이다.

요약하자면,

- HashMap에서는 해시 충돌을 방지하기 위해 Closed Addressing 중 하나인 Separate Chaining 및 보조 해시 함수를 사용한다.
- Java8에서는 Separate Chaining에서 데이터의 수가 많아지면 Linked List 대신 Tree를 사용한다.
- String 클래스의 hashCode() 메서드에서는 성능 향상 도모를 위해 31을 승수로 사용한다.

라고 할 수 있다.

웹 어플리케이션 서버에서는 HTTPRequest가 생성될 때 마다 여러 개의 HashMap이 생성된다.
또한 수많은 HashMap 객체가 매우 짧은 시간에 생성되고 GC의 대상이 되기도 한다. 컴퓨터 메모리 크기가 보편적으로 증가함에 따라 HashMap에 더 많은 데이터를 저장하고 있다.
따라서 HashMap의 구현은 앞으로 많은 데이터를 더 효율적이고, 빠르게 연산을 수행할 수 있는 방식으로 변화할 것이다.

참고:
docs.oracle.com/javase/8/docs/api/java/util/HashMap.html