Java HashMap의 내부 동작 - 실전편

관련 포스팅

1. Java HashMap의 내부 동작 - 이론편
2. Java HashMap의 내부 동작 - 실전편
3. Java HashMap의 내부 동작 - 해시 버킷 개수 조정

---

이번 글에서는 Java에 HashMap이 실제 코드로 어떻게 되어있는지 확인해보자 한다.

 

데이터 삽입(put)

put 메소드의 데이터 추가는 아래 3가지의 경우를 순서대로 처리한다.

 

1. 해당 인덱스의 해시 버킷(LinkedList) 확인

   - 해당 해시 버킷에 값이 없을 경우 새로운 Node 추가 후 종료

 

2. 해당 해시 버킷의 키 값 일치여부 확인

   - key가 일치할 경우 해당 키에 대한 값 변경해준 후 종료

 

3. 해당 해시 버킷에 값 추가

   - Tree일 경우와 / LinkedList일 경우 분기하여 처리

 

  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    
    // 데이터 삽입하는 내용 이전 생략...
    
    if ((p = tab[i = (n - 1) & hash]) == null) {
      // 해당 인덱스의 해시 버킷에 값이 없을 경우 새로운 Node 추가 후 종료
      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)))) {
        // key가 일치할 경우 해당 키에 대한 값 변경해준 후 종료
        e = p;
      } else if (p instanceof TreeNode) {
        // 해시 버킷에 Tree를 사용할 경우
        e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
      } else {
        // 해시 버킷에 LinkedList를 사용할 경우
        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;
      }
    }

 

이전 글에서 말했던 Separate Chaining을 HashMap에서는 Tree와 LinkedList를 사용하여 구현해두었다.

 

여기서 Tree와 LinkedList를 왜 분리하여 사용하는지에 대한 의문이 발생할 수 있다.

우선 둘의 특징에 대해 알아보자

 

LinkedList - 성능 BAD, 메모리 사용량 적음

Tree - 성능 GOOD, 메모리 사용량 많음

 

아니 그러면 성능을 생각한다면 Tree만 사용하면 되는거 아니에요?

 

허나 데이터의 개수가 적은 경우 Worst Case에서 LinkedList와 Tree의 성능차이는 크게 의미가 없다.

따라서 메모리를 절약하기 위해 자바에서는 LinkedList로 생성 후 데이터의 개수가 8개를 넘어갈 경우 Tree로 변환해준다.

또 데이터의 개수가 6개까지 줄어들 경우 다시 LinkedList로 변환해주는데

이는 만일 차이가 1이면 하나의 데이터가 반복하여 삭제, 추가될 경우 불필요한 변환이 반복되어 성능저하로 이어지기 때문이다.

 

---

데이터 조회(get)

get 메소드는 put 메소드에서 진행한 내용을 반대로 진행하는 내용이라 이해하는데에는 큰 어려움이 없었다.

데이터를 불러오는 내용을 정리해보자면 아래와 같다.

 

1.  테이블이 비어있는지 &  해당 인덱스의 해시 버킷(LinkedList) null 체크

   - null이거나 비어 있을 경우 중단

 

2. 해시버킷의 첫번째 값(head) 확인

   -  key가 일치할 경우 해당 값 반환 후 종료

 

3. 해시버킷에 다음값 존재할 경우 탐색 진행

   - Tree일 경우와 / LinkedList일 경우 분기하여 처리

 

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

            // 해시 버킷이 LinkedList일 경우
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 일치하는 값이 없으면 null return
    return null;
}

 

 

---

정리

HashMap의 put과 get 메소드에서 어떻게 데이터를 저장하고 조회하는지에 대한 내용을 확인해보았다.

HashMap에서는 Separate Chaining을 Tree와 LinkedList를 통하여 구현하고 있었다.

 

 

 

또 HashMap의 성능을 위해 고려해야할 개념인 해시 버킷 개수 변경은

너무 깊게 들어가는 내용이라 판단되어 다음 글에서 정리해보고자 한다.

 

---

관련 포스팅

1. Java HashMap의 내부 동작 - 이론편
2. Java HashMap의 내부 동작 - 실전편
3. Java HashMap의 내부 동작 - 해시 버킷 개수 조정