[JAVA] HashMap

HashMap 이란?

HashMap은 Map 인터페이스를 구현하고 있는 대표적인 클래스 입니다.

Map의 구조인 key-value 쌍으로 구성 되어 있는게 특징입니다.

 

HashMap의 사용 이유

- 탐색 속도가 빠르다 (평균 O(1))

  - key를 기준으로 데이터를 매우 빠르게 조회할 수 있습니다.

  - 내부적으로 배열+해시 함수를 사용해 위치를 계산하기 때문에 성능이 뛰어납니다.

  - 대량의 데이터를 다룰 때, 순차 탐색보다 훨씬 빠릅니다.

- Key-Value 구조로 데이터 저장

  - 하나의 key에 하나의 value를 매핑합니다.

  - 중복된 key를 넣으면 이전 value를 덮어쓰기 합니다.

- 중복 없는 key 관리

 - 같은 key를 두 번 넣으면 마지막 value로 덮어쓰게 되므로 자연스럽게 중복 제거 기능도 제공됩니다.

 

HashMap class를 확인 해보자!

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

    @java.io.Serial
    private static final long serialVersionUID = 362498820763181265L;
    
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
     static final int MAXIMUM_CAPACITY = 1 << 30;
     static final float DEFAULT_LOAD_FACTOR = 0.75f;
     static final int TREEIFY_THRESHOLD = 8;

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

 

HashMap의 초기 용량은 16, 로드팩터는 0.75 입니다. (로드팩터 = (데이터의 개수)/(초기 용량)) 버킷 하나에 여러 개의 값을 가지는 것, 즉 충돌을 피하기 위해서 설정한 것입니다.

 

HashMap<String, Integer> stringIntegerHashMap = new HashMap<>(); //생성
stringIntegerHashMap.put("1",1); //HashMap put

 

생성을 하게 되면 로드팩터에 0.75가 들어가며

 hashMap에 put 할 시 해시맵의 사이즈가 만들어 집니다.

 

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) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; //첫 put 호출 시 resize 호출
        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;
    }
---------------------------------------------------------------------
        final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

 

 

아래 HashMap의 클래스를 보게 되면 

첫 put 호출시 putVal이 호출이 되며

 if ((tab = table) == null || (n = tab.length) == 0)
     n = (tab = resize()).length; //첫 put 호출 시 resize 호출

resize 를 호출 하게 됩니다.

 

resize의 이 부분을 호출 하며 

    else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY; //16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //16 * 0.75
        }

      Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

16개의 배열 크기로 생성이됩니다.

※그러나 13개 이상을 담게 되면 리사이즈를 진행 합니다.

왜 16개를 만들었는데 13개 이상 담으면 리사이즈를 할까?

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        
        if (++size > threshold) //12
            resize();

• HashMap은 데이터를 해시값 기반으로 배열의 인덱스에 분산시킵니다.
• 충돌이 적을수록 탐색 속도는 O(1)에 가까워집니다.
• 하지만 배열을 꽉 채우면 충돌이 늘어나고, 성능이 O(n)에 가까워질 수 있습니다.

즉, 배열의 75%까지만 사용하자는 뜻입니다.

공간 낭비처럼 보여도 성능 최적화를 위한 설계입니다.
만약 메모리를 아끼고 싶으면 loadFactor를 1.0으로 지정할 수도 있지만, 일반적으로는 성능 때문에 0.75가 권장 값입니다.

 

 

HashMap에서는 해시 충돌을 어떻게 할까?

    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;
           1. if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            2.else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            3. 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;
    }

 

1. 동일한 key인지 확인

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

 

• 해시값과 키가 동일한 경우 → 기존 노드를 덮어씁니다 (충돌 X, 같은 키)
• 여기서는 실제 충돌이 아닙니다 (동일한 키인 경우)

 

2.Tree 구조일 경우

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

 

 

• 해당 버킷이 트리 구조이면 → 트리 탐색 및 삽입
• 트리화 이후의 충돌 처리 방식

 

3.LinkedList 방식으로 충돌 처리 (체이닝 방식)

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); //버킷 안에 노드 8개 이상이면 트리로 변환 시도
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

 

 

• p.next == null이면 리스트 끝 → 새 노드 추가 (충돌 발생!)
• binCount가 TREEIFY_THRESHOLD - 1 (기본 7)이면 → 트리화 시도
• 이미 같은 키가 있다면 → 덮어쓰기 위해 break

 

 

즉  하나의 버킷에 충돌된 항목에 8번째가 들어 오면 트리화를 시도 합니다.

단, 버킷 배열 크기가 64 이상이어야 트리화가 되며 배열이 작을 경우 리사이즈를 먼저 진행합니다.