자료구조 - HashMap 들여다보기(2)

 

이전 포스팅에서 해싱과 충돌에 대해서 살펴보았으니 이러한 기본적 바탕 지식을 갖고 자바의 HashMap에 대해서 들여다보자. 해싱과 충돌에 대해 쓴 포스팅은 아래 링크를 참조하여 확인할 수 있다.

https://hongjw1938.tistory.com/16?category=884192

자료구조 - HashMap 들여다보기(1)

 

HashMap은 자바에서 Map 인터페이스를 구현하여 설계되었다. 다른 자료구조와 다르게 O(1), 즉 상수 시간의 데이터 검색/삽입을 할 수 있는 기능을 제공한다. 해싱을 사용하여 Key / Value 형태의 자료를 저장할 수 있는데 HashMap은 put(key, value) 메소드를 통해 자료를 저장하고, get(key) 메소드를 통해 저장한 자료를 반환할 수 있다.

 

# HashMap의 동작 방식

이전 포스팅에서도 설명했지만, HashMap이 지원되기 이전에는 Java 1.0 부터 지원되던 HashTable을 주로 사용하였다. HashMap과의 차이점은 HashTable은 Synchronized이며 null 값은 저장할 수 없었다. 

그렇다면, HashMap이 내부적으로 어떻게 동작할까? 가장 기본적으로 해싱의 원칙을 수행하여 동작한다. 잠깐 해시 함수의 원칙을 살펴보자.

 

---

1) 충돌이 최소한으로 발생해야 한다.

해시 함수는 수많은 Key - Value 데이터를 상대적으로 작은 크기의 table에 효과적으로 저장하기 위해 설계된다. 이 때 발생하는 충돌은 운이 좋다면 정말 거의 없을 수 있지만 완전히 회피하는 것은 거의 불가하다. 수학적으로 충돌이 일어날 확률 또한 구할 수 있으며 그 확률이 낮더라도 0이 되기는 거의 불가하다.

2) 균등하게 데이터가 분포되어 저장되어야 한다.

기본적으로 해시 함수를 설계 시에 입력될 키의 배포에 대해서 미리 아는 것이 불가능하다. 그렇기 때문에 저장될 Key - Value 쌍의 데이터가 클러스터링(군집) 현상을 이루지 않고 균등하게 저장할 해시 함수를 선택해야 한다. 그것을 통해 시간적 / 공간적 효율을 최대화할 수 있기 때문이다.

---

 

HashMap 클래스는 데이터를 저장하기 위해 put(key, value) 메소드를 사용하고 데이터를 반환하기 위해 get(key) 메소드를 사용한다. 

 

① HashMap의 삽입 (put 메소드)

put 메소드를 사용해 데이터를 삽입할 때는 hashCode 메소드를 호출해서 Key를 기반으로 해싱을 진행해 고정된 크기의 int 값을 반환받는다. 그러면 자바는 해당 Key - Value 쌍의 데이터를 Map.Entry Object 형태로 생성해 내부적으로 구현되어 있는 배열(Bucket)에 저장한다. 해당 배열은 고정된 크기로  생성되어 있다.(최초 생성 시 16의 크기)

아래는 실제 HashMap의 put 메소드의 내부 로직이다.

public class HashMap<K, V> extends AbstractMap<K, V>
    implements Map<K, V>, Cloneable, Serializable{

    ...

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        ....
    }
    
    ....
}

 

② Map.Entry Object

HashMap은 내부적으로 Key / Value를 하나의 Map.Entry형태의 Object로 만들어서 Bucket에 저장한다. Entry는 Map의 중첩(Nested) 인터페이스이다.(또는 내부 인터페이스, Inner Interface)

Map 인터페이스의 실제 내부가 어떻게 구성되어 있는지 아래의 코드를 보자.

public interface Map<K, V> {
    int size();
    boolean isEmpty();
    
    ...
    
    interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        
        ...
    }
    
    ...
}

 

위 코드는 실제 자바의 Map 인터페이스의 일부이다. 이를 보면 Map 내부에 Entry 라는 인터페이스가 또 존재하는 것을 알 수 있다. 자바에서 HashMap에 데이터를 저장하기 위해 put 메소드를 사용하면 Map.Entry Object에 Key / Value를 넣고 저장하는 방식으로 설계되어 있다.

---

※ 중첩 인터페이스(내부 인터페이스)

중첩 인터페이스는 인터페이스 또는 클래스 내에 선언되는 static 인터페이스를 의미한다. 이러한 인터페이스는 내부에 구현되기 때문에 public에서 직접 접근할 수는 없고 dot(.)을 통해 해당 인터페이스가 구현된 클래스나 외부 인터페이스 뒤에 붙여서 사용해야 한다.

왜 중첩 인터페이스를 사용할까? 주 목적은 연관이 있는 인터페이스 또는 클래스를 Grouping하여 그 연관된 집합들의 namespace를 사용하기 위해서이다. 보통 UI 프로그래밍에서 이벤트 처리를 위한 목적으로 많이 사용되는데 그 목적은 아래와 같다.

① 논리적으로 Interface를 그룹화하여 하나의 위치에서만 사용하도록 함
② 캡슐화를 통해 불 필요한 관계 Class를 별도로 생성하지 않고 내부적으로만 활용 가능하게 제한
③ 유지 보수 및 가독성에 유리한 코드 작성

 

Map 인터페이스는 자료구조를 구현한 Map 형태의 클래스가 반드시 구현하는 인터페이스로, 해당 Map 형태의 저장소, 즉 일종의 저장 컨테이너에 대한 View를 제공하기 위해 사용할 수 있다. Entry 인터페이스는 해당 저장소의 다른 형태의 View를 제공한다(예 : EntrySet).

즉, Map 범위의 개체와 Entry 범위의 개체가 다를 수 있으나 Entry에 있는 개체는 Map과 밀접한 연관이 있도록 설계한 형태라고 볼 수 있다.

---

 

 

③ 충돌 대처

만약 저장하고자 하는 두 Object의 Key가 동일한 hash code를 갖는다면 충돌을 일으킬 것이다. 자바에서는 equals() 와 hashCode() 메소드를 통해 해당 두 Object가 동일하지 않다는 것을 확인할 것이다. Key 값이 다르더라도 hashCode() 메소드에 의해 같은 해시 값으로 바뀔 수 있다.

하지만 결국 key 값을 equals() 메소드를 통해서 비교한다면 Key Object가 서로 다르다는 것을 내부적으로 확인할 수 있다. 그렇다면 동일한 해시 값에 의해 동일한 위치에 어떻게 저장할까?

이전 포스팅에서 설명한 Chaining 방식을 통해서 수행된다. 실제 자바에서 저장소가 될 Bucket은 LinkedList를 이용하여 구현되었기 때문에(Java 8 부터는 성능적으로 더 좋은 Tree 형태로 바뀌었다고 함) 동일한 Bucket의 위치에 저장된 Object 들끼리 연결되어 있는 방식으로 저장이 된다.

이해를 돕기 위해 이전 포스팅에서 사용한 이미지를 다시 사용한다. 아래를 참고.

Chaining 예시. 출처 : geeksforgeeks

 

④ 데이터 찾는 법(get method)

그렇다면, 충돌이 일어났을 때, 어떤 데이터가 찾고자 하는 데이터인지를 어떻게 알 수 있을까? HashMap은 데이터를 반환받기 위해서 get(Key) method를 사용한다. 딱 봐도 알 수 있듯이, Key 값을 전달해서 그에 맡는 Value 값을 가져오는 것이다.

Key 값이 전달되면 해당 Key를 해싱하여 고정된 숫자값으로 Bucket의 위치를 찾게 되고 그 안의 LinkedList에 있는 Object 중 올바른 Object를 찾아 반환해야 한다. 이 때, LinkedList 내의 Object들을 순회하며 찾고자 하는 데이터를 탐색하게 된다.

어떤 데이터가 찾고자 하는 데이터인지 어떻게 알까? 그것은 equals() 메소드를 사용한다. Key를 해싱한 해시 값은 동일하더라도 정작 원본 Key 값이 다르다면 다른 Object임을 알 수 있기 때문이다. 위의 put 메소드를 다시 살펴보게 되면 putVal 메소드에 해싱된 Key 값과 원본 Key값이 전달되는 것을 알 수 있다. 실제 Bucket의 Map.Entry Object에는 Key - Value가 모두 저장된다.

아래의 코드를 통해 실제 어떻게 구현되어 있는지 보자. 

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    ...
    
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    ...
}

이는 실제 HashMap의 get / getNode 메소드이며, get 메소드에서는 getNode 메소드를 호출하여 hash 값과 key를 모두 전달하여 해당 Node가 있는지 판단하여 반환한다.

getNode 메소드는 좀 복잡한데 해당 전달된 Key의 해시 값과 원본 Key 값을 기반으로 해당 Node를 찾는 방식이다. 코드를 보면 지금은 Tree 방식으로 Bucket이 구현되어 있다는 것을 알 수 있다.

 

⑤ Load Factor

Load Factor는 HashMap의 capacity 즉, 수용 가능한 크기가 어느 정도까지만 유지될 수 있는지에 대한 threshold 값을 의미한다. 쉽게 말해,  전체 capacity, 즉 HashMap의 전체 크기가 Default 값인 16이라고 생각해보자. 그리고 Load Factor는 HashMap을 생성할 때 별도로 변경하지 않아 Default 값인 0.75 라고 해보자.

그렇다면 전체 크기 16 중에 약 75%의 저장소가 이미 사용중이라면, 저장소의 크기를 늘릴 시점이라고 보는 것이다. 위에서 설명했듯이, Key 값이 어떠한 값이 들어올 것이라고 예상하고 미리 HashMap 을 구현하지는 않는다. 모든 경우에 어울리게 만들 수도 없다.

따라서, 어떠한 데이터들은 저장할 때 특정 Bucket의 위치에 군집(clustering) 현상이 발생할 수 있다. 최대한 균등하게 Bucket이 저장되더라도 일부 Bucket은 성능이 상대적으로 느릴 수가 있다. 따라서, Load Factor 값을 통해 데이터를 삽입 시, 현재 수용 가능한 수준인지 판단 하는 것이다.

그렇다면, 신규 데이터 삽입 시, Load Factor로 계산한 값 보다 수용량이 늘어나게 되면 어떻게 할까? 자바의 HashMap은 기존의 Bucket의 전체 크기의 약 2배가 되도록 새로이 저장소를 구성하고 다시 데이터를 저장한다. 이 과정이 Re-Hashing이라고 불린다.

 

⑥ HashMap 생성 시 유의사항

자바의 HashMap을 사용할 때, 최초의 HashMap Capacity / Load Factor 값을 생성자를 통해 전달할 수 있다. 아래의 코드를 보자.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
}

위 코드는 실제 HashMap 코드 중 생성자 부분이다. 최초 Capacity와 Load Factor 값을 사용자가 설정할 수 있다.

Capacity의 기본값은 16이고, Load Factor의 기본값은 0.75이다. 만약 Capacity를 너무 크게 설정하면 공간이 매우 낭비될 것이다.

Load Factor가 작다면 그만큼 자주 Re-Hashing이 일어나 전체 크기가 빠르게 늘어나게 된다. 그래서 메모리 공간이 낭비된다.

Load Factor가 크다면 데이터가 많이 저장되어도 Re-Hashing이 일어나지 않을 수 있어 메모리의 낭비는 줄이더라도 검색 속도가 느려질 수 있다.

따라서, 사용자는 효율적으로 활용하기 위해 최초에 어느 정도의 데이터를 저장할 것인지 예측하고 이 HashMap을 생성하는 것이 좋으며, Load Factor는 자바의 문서에서 권고하는 Default 값을 쓸지, 아니면 값을 변경할지 잘 고려해서 코드를 설계해야 한다.

 

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.