HashMap의 Rehashing과 Load factor (with. Java)

아래 2개 링크의 글을 읽고 정리한 글. GeeksforGeeks가 틈틈히 읽기 좋은 글들이 많아서 좋다.

 

Load Factor in HashMap in Java with Examples - GeeksforGeeks

Load Factor and Rehashing - GeeksforGeeks

 

1. HashMap의 정의

HashMap은 Key-Value 형태의 데이터 저장을 하는 Map을 Hash와 접목한 자료구조이다.

정리하면 Hash function에 Key를 입력으로 사용해서 Key에 대응되는 Index를 구하고 이 Index에 데이터(Value)를 저장하는 방식이다.

 

HashMap에서 사용하는 일반적인 용어는 아래와 같다.

- Index : hash function을 통해서 구한 정수값을 의미한다. 데이터가 들어갈 위치가 된다.

- Node : HashMap에서 사용하는 데이터의 최소 단위이다. HashMap은 Linked list로 이뤄지기 때문에 다음 노드를 가르키는 Next 변수가 존재한다.

- Bucket : Linked list로 이어진 Node의 집합을 나타내는 용어다.

- Capacity : 아래 그림에 있진 않지만 Capacity라는 용어도 사용되는데 Capacity는 Bucket의 수를 의미한다.

Source : https://www.geeksforgeeks.org/java-util-hashmap-in-java-with-examples/

2. Initial Capacity

자바 1.8기준 초기 Capacity는 16이다.

좋은 HashMap 알고리즘은 Node가 균일하게 HashMap에 적재되는 것이다. 이 부분은 세계의 석학(?)들이 구현을 해뒀으니 내가 고민할 부분은 아니다.

3. 성능

HashMap의 시간 복잡도를 알아보자.

먼저, Hash Function을 통해서 Key를 양의 정수 형태로 변환한다. 여기서 시간은 Key의 원본 데이터의 사이즈에 따라 달라지게 되는데 사실상 무시할 수 있는 수준이라 시간 복잡도는 O(1)이 된다.

 

Key를 통해 index를 선정했다면 Linked List에 Node를 붙여야 하는데 최악의 경우엔 모든 노드가 하나의 인덱스에 들어있기때문에 n번의 탐색을 해야한다. (Linked List는 인덱스를 가지지 않으므로 내가 원하는 노드의 위치를 알기위해선 Full Scan을 해야한다.)

 

이 경우에 O(n)까지 시간 복잡도가 높아지게 된다. 하지만 대부분의 Hash Function은 Hash Map에 적절하게 노드가 분배되도록 설계되었기 때문에 O(n)까지 가는 경우는 없고 대부분 O(1)에 수렴한다. (빠르다...)

4. Load Factor를 통한 성능 보장.

HashMap이 빠른 검색 성능을 보장하기 위해 Java에선 Load factor 개념을 도입한다.

 

아래의 예제를 보자. (Capacity가 16인 경우다)

16개의 Node가 있을때 각 bucket은 1개의 노드만 가지는 Linked List로 구성된다. 따라서 노드를 검색할때 bucket내에서 1회만에 element를 찾을 수 있다.

32개의 Node가 있을때 각 bucket은 2개의 노드를 가지는 Linked List로 구성된다. 따라서 노드를 검색할 때 bucket 내에서 최대 2회의 찾기 작업이 수행된다.

64개의 element가 있는 경우 최대 4회의 찾기 작업이 수행된다. 10,00,000개의 Node가 있는 경우 최대 62,500회의 찾기 작업이 수행된다.

 

여기서 알 수 있듯이 Capacity가 Node의 수에 비해 크기가 작다면 Key 찾기 속도가 느려진다. 따라서 성능을 위해 적절한 타이밍에 Capacity를 늘려줘야한다. 여기서 적절한 타이밍의 기준이 되는 값이 Load Factor이다.

 

Load Factor는 Capacity 사이즈에 대한 임계값(Threshold)이다. 초기 Capacity에 있는 Node의 비율이 늘어나서 Load Factor를 넘어가면 Capacity의 사이즈를 늘린다.

 

이 작업을 통해 HashMap은 시간 복잡도를 상수인 O(1)으로 유지할 수 있다. 자바에서 Load factor의 기본값은 0.75이다.

Capacity가 16일때 Node가 13개면 0.8125(13/16)의 비율을 가진다. 이때 Load factor의 기본값인 0.75보다 크므로 Capacity의 사이즈를 기존 사이즈의 2배인 32로 늘린다.

5. Rehashing

Node의 비율이 Load factor를 초과하는 경우 기존에 있던 Node를 재분배 하게 되는데 이 작업을 Rehashing이라 부른다.

직접 코드를 작성해서 Rehashing을 이해했다. 실제 자바의 HashMap 코드도 아래와 유사한데 성능을 위해서 Red black tree개념을 추가로 도입했다. (이 부분은 좀더 학습을 한 뒤에 업로드 예정)

package com.soojong.datastructure.rehash;

import java.util.ArrayList;

public class RehashingSampleMap<K,V> {

    // HashMap에서 사용할 Node의 구조를 정의한다
    class Node<K, V> {

        K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value)
        {
            this.key = key;
            this.value = value;
            next = null;
        }
    }

    ArrayList<Node<K, V>> buckets;
    int size; // 전체 Node의 개수
    int numBuckets; // 버킷의 개수

    final double DEFAULT_LOAD_FACTOR = 0.75;

    public RehashingSampleMap() {

        numBuckets = 5; //Initial Bucket Number is 5

        buckets = new ArrayList<>(numBuckets);

        for (int i = 0; i < numBuckets; i++) {
            buckets.add(null);
        }
        System.out.println("HashMap created");
        System.out.println("Number of pairs in the Map: " + size);
        System.out.println("Size of Map: " + numBuckets);
        System.out.println("Default Load Factor : " + DEFAULT_LOAD_FACTOR + "\n");
    }

    private int getBucketIndex(K key) {

        // Using the inbuilt function from the object class
        int hashCode = key.hashCode();

        // array index = hashCode%numBuckets
        return (hashCode % numBuckets);
    }

    public void insert(K key, V value)
    {
        // key와 매칭된 bucket의 인덱스
        int bucketIndex = getBucketIndex(key);

        // bucket을 가져온다. 이 뜻은 각 버켓의 Head Node를 가져온다는 뜻!!
        Node<K, V> head = buckets.get(bucketIndex);

        // bucket내에 이미 존재하고 있는 key인지 검사하고 존재한다면 value를 덮어쓰기 하고 종료
        while (head != null) {

            // If already present the value is updated
            if (head.key.equals(key)) {
                head.value = value;
                return;
            }
            head = head.next;
        }

        // 새로운 노드를 만든다
        Node<K, V> newElementNode = new Node<>(key, value);

        // 새로운 노드를 넣을 bucket을 가져온다
        head = buckets.get(bucketIndex);

        // 새로 들어온 Node의 next를 첫번째 Node로 한다
        // 원형 Linked List 구조!
        newElementNode.next = head;
        // 새로 들어온 element가 Head가 될 수 있도록 한다
        buckets.set(bucketIndex, newElementNode);

        System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n");

        // 전체 Node 개수를 1 증가 시킨다
        size++;

        // load factor를 재계산 한다.
        double loadFactor = (1.0 * size) / numBuckets;

        System.out.println("Current Load factor = " + loadFactor);

        // If the load factor is > 0.75, rehashing is done
        if (loadFactor > DEFAULT_LOAD_FACTOR) {
            System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR);
            System.out.println("Therefore Rehashing will be done.\n");

            // Rehash
            rehash();

            System.out.println("New Size of Map: " + numBuckets + "\n");
        }

        System.out.println("Number of pairs in the Map: " + size);
        System.out.println("Size of Map: " + numBuckets + "\n");
    }

    private void rehash()
    {

        System.out.println("\n***Rehashing Started***\n");

        // The present bucket list is made temp
        ArrayList<Node<K, V> > temp = buckets;

        // New bucketList of double the old size is created
        buckets = new ArrayList<>(2 * numBuckets);

        for (int i = 0; i < 2 * numBuckets; i++) {
            // Initialised to null
            buckets.add(null);
        }
        // Now size is made zero
        // and we loop through all the nodes in the original bucket list(temp)
        // and insert it into the new list
        size = 0;
        numBuckets *= 2;

        // insert 작업을 다시 수행한다!!!!
        for (int i = 0; i < temp.size(); i++) {

            // head of the chain at that index
            Node<K, V> head = temp.get(i);

            while (head != null) {
                K key = head.key;
                V val = head.value;

                // calling the insert function for each node in temp
                // as the new list is now the bucketArray
                insert(key, val);
                head = head.next;
            }
        }

        System.out.println("\n***Rehashing Ended***\n");
    }

    public void printMap()
    {

        // The present bucket list is made temp
        ArrayList<Node<K, V> > temp = buckets;

        System.out.println("Current HashMap:");
        // loop through all the nodes and print them
        for (int i = 0; i < temp.size(); i++) {

            // head of the chain at that index
            Node<K, V> head = temp.get(i);

            while (head != null) {
                System.out.println("key = " + head.key + ", val = " + head.value);

                head = head.next;
            }
        }
        System.out.println();
    }

    //Function to get an element from Map
    public V getValue(K key){
        //Get actual index of the key
        int actualIndex = getBucketIndex(key);
        Node<K,V> temp = buckets.get(actualIndex);
        //Search for key in list
        while(temp != null){
            if(temp.key == key){
                return temp.value;
            }
            temp = temp.next;
        }
        return null;
    }

}

메인 코드에서 직접 테스트를 했다.

package com.soojong.datastructure.rehash;

import java.util.HashMap;
import java.util.Map;

public class RehashingMain {

    public static void main(String[] args) {
        // Creating the Map
        RehashingSampleMap<String, String> map = new RehashingSampleMap<>();

        // Inserting elements
        map.insert("1", "Geeks");
        map.printMap();

        map.insert("2", "forGeeks");
        map.printMap();

        map.insert("3", "A");
        map.printMap();

        map.insert("4", "Computer");
        map.printMap();

        map.insert("5", "Portal");
        map.printMap();

        //Get element from Map
        String key = "4";
        String value = map.getValue(key);
        System.out.println("Value at key "+ key +" is: "+ value);

    }

}

 

출력 결과

HashMap created
Number of pairs in the Map: 0
Size of Map: 5
Default Load Factor : 0.75

1
Pair(1, Geeks) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 1
Size of Map: 5

Current HashMap:
key = 1, val = Geeks

2
Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 2
Size of Map: 5

Current HashMap:
key = 2, val = forGeeks
key = 1, val = Geeks

3
Pair(3, A) inserted successfully.

Current Load factor = 0.6
Number of pairs in the Map: 3
Size of Map: 5

Current HashMap:
key = 2, val = forGeeks
key = 3, val = A
key = 1, val = Geeks

4
Pair(4, Computer) inserted successfully.

Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.


***Rehashing Started***

2
Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.1
Number of pairs in the Map: 1
Size of Map: 10

3
Pair(3, A) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 2
Size of Map: 10

4
Pair(4, Computer) inserted successfully.

Current Load factor = 0.3
Number of pairs in the Map: 3
Size of Map: 10

1
Pair(1, Geeks) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 4
Size of Map: 10


***Rehashing Ended***

New Size of Map: 10

Number of pairs in the Map: 4
Size of Map: 10

Current HashMap:
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer
key = 1, val = Geeks

5
Pair(5, Portal) inserted successfully.

Current Load factor = 0.5
Number of pairs in the Map: 5
Size of Map: 10

Current HashMap:
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer
key = 5, val = Portal
key = 1, val = Geeks

4
Value at key 4 is: Computer

 

GitHub - 92SooJong/java-study: Java basic study with sample code