java.util.HashMap equals, hashcode, resize

이전 글로 Map interface에 대해서 기록한 적이 있습니다. : https://duooo-story.tistory.com/18

 

Map중에서도 학생때부터, 그리고 실무에서도 진짜 많이 사용하는 HashMap을 기준으로 put을 진행했을때, 내부 코드가 어떻게 진행되는지에 대해서 이번에 기록하려 합니다. 

 

먼저 hashMap 이란 에 대해서 간략하게 정리하겠습니다. HashMap은 key,value pair로 데이터를 저장하며, key의 중복을 허용하지 않습니다.  또한 순서를 보장하지 않으며 key,value 값으로 null을 허용합니다. 

내부적으로 데이터를 Burket이라는 걔념을 통하여 데이터를 저장합니다. key값 Object의 key.hashCode() 함수를 이용하여 어떤 버켓의 데이터 리스트에 저장이 될지 결정이 되며, 내부적으로 key값의 equals()도 사용하여 중복된 key값이 있는지 확인 및 적재 작업을 진행합니다. 마지막으로 hashTable과는 다르게 멀티스레드 환경에서 thread-safe를 보장하지 않습니다.

 

ref : https://blog.csdn.net/ccj659/article/details/52797739

 

 

 

이제 코드로 돌아와서 가장 기초 부분으로 HashMap 생성자 부분을 보면 다음과 같습니다.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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

해당 생성자들을 보면 loadFactor, threshold가 set되는 것을 볼 수 있는데, 두개의 기능은 각각 다음과 같습니다.

loadFactor = (key,value Mapping Pair) elements 수 / bucket의 수 , 이 수치 * bucket의 수를 넘어가면 Hashmap resize발생( 두 배로 증가)

threshold = resize가 필요한 수, 이 수치를 넘으면 resize발생

 

별도로 지정하지 않으면 Default bucket의 수 : 16, loadFactor = 0.75f threshold = 12 로 초기 세팅이 됩니다.

해당 두개의 변수가 사용되는 부분은 다른 기능을 통하여 같이 알아보겠습니다.

 

해당 부분을 통해 HashMap을 선언하고, 데이터를 Insert할때 다음과 같은 동작을 취하게 됩니다.

 

map.put("key1","value1");

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


// java 8버전 이상의 모습이라고 합니다.
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

이 putVal 메서드를 보면 기본적인 HashMap의 동작구조를 설명할 수 있습니다.

 

먼저 해당부분에서 저음 resize()를 통해 bucket 16크기를 가지는 tab(table)를 생성하게 됩니다.

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

그다음 if문(5번 라인) 을 통해서 먼저 선택된 bucket이 null인 경우, 새로운 Node를 생성하여 해당 버켓에 넣어줍니다.

 if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

 

만약 bucket이 null이 아닌경우, else 문에서 추가또는 변경작업을 위해서 코드를 타게됩니다.

if문(9번 라인)에서 코드는 아래에 if문(22번 라인) 과 유사한것을 볼 수 있는데 만약 해시코드가 같고, bucket 안에 있던 key과 equals를 통해서 겹치게 되면, 이때는 key가 동일하다고 판단하여 value값의 업데이트를 수행하게 됩니다. 이부분으로 인하여 만약 직접 만든 객체에 대해서 key값으로 사용할 경우 hashcode(), equals 함수를 반드시 올바르게 구현해줘야 같은 객체로 인식을 하게 됩니다.

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) { p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

else if(12번 라인) 부분에서는 Bucket이 TreeNode로 되어있는지 확인합니다. Bucket은 처음 처음에는 LinkedList 처럼 Node를 저장(Open Addressing 방식)하다가 bucket안에 들어있는 element가 TREEIFY_THRESHOLD ( 8개를) 넘는 순간, List에서 이진 트리노드인 Red-Black Tree 방식(Separate Chaining 방식)으로 데이터를 저장방식을 변경하게 됩니다. ( List로 계속 Bucket이 커지게 되면 속도가 줄어들게 됩니다.)

 

반대로 remove과정에서는 UNTREEIFY_THRESHOLD (6개)보다 작아지면 Tree를 다시 List방식으로 저장을 변경하게 되는데 숫자 2의 차이를 두는점에선 빈번하게 insert,delete가 일어날때 bucket 저장방식의 변경과정에서 발생되는 비용을 줄일 수 있습니다. 

 

마지막으로 else부분에서는 버킷안에 매핑되는 key값이 없을 때, 또는 값을 찾았을때 에 대해서 합수를 끝내게 되고 만약 새로운 노드를 추가하면서 bucket size가 TREEIFY_THRESHOLD를 넘게되면 tree로 변경하는 코드를 포함하고 있습니다.

 

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);

마지막으로 Bucket 사이즈를 수정하고 만약 threshold를 넘게되면 resize를 통해서 size를 두배로 증가시키게 됩니다.

그리고 현재 hashMap에서 afterNodeAccess는 비어있습니다. (HashMap을 상속받는 LinkedHashMap을 위한 post처리 용 으로 작성이 되어 있습니다. 추후에 LinkedHashMap을 기록하며 같이 작성할 계획입니다.)

 

 

resize에서는 만약 threshold를 넘기게 되면 2배로 증가가 되는부분을 살펴보면 table size도 두 배로 증가하면서 theshold size또한 두 배로 증가되게 됩니다.

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold
    
    .....
    
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 테이블 업데이트

그리고 resize시 이전 table에서 가지고 있던 bucket 그리고 그 안에 기록된 내용들에 대해서 다시 이전하는 작업을 진행하게 되면서 오버해드 발생 부분이 될 수 있습니다.

 

간략하게 HashMap put 부분을 통해 정리를 해보면서( 뭔가 중요한걸 잊은거 같은데..) 동작원리에 대해서 복습도 되었고, 추후엔 ConcurrentHashMap과의 비교라던가, 다른 구현체의 차이점과도 비교하여 같이 작성해야겠습니다.

 

 

 

 

 

참고 사이트

http://egloos.zum.com/iilii/v/4457500

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

관련 글

Java Map Interface (java version 1.2, 8, 9, 10) : https://duooo-story.tistory.com/18