[JAVA] HashMap의 내부 구현 방식

✅ HashMap이란?

• key와 value로 짝지어 저장
  • 이 set를 하나의 Node로 본다
  • 이 Node의 배열이 곧 HashMap이다
• key값은 고유
• 데이터 넣은 순서 보장 X

✅ 성능과 관련있는 변수 3개

1. initialCapacity

• 초기 HashMap의 용량 = 버킷 갯수를 의미
• 미리 잘 설정해놓으면 rehashing이 일어나지 않음
• DEFAULT_INITIAL_CAPACITY= 1 << 4 = 16
• MAXIMUM_CAPACITY = 1 << 30

2. load factor

• HashMap이 어느정도 차야 자동으로 확장할지 정한 값
  • 0 ~ 1 사이의 값
• DEFAULT_LOAD_FACTOR = 0.75
  • 75% 차면 HashMap의 크기를 늘리겠다
  • 값이 커질수록
    • 공간의 오버헤드는 감소하지만
    • HashMap에 여유 공간이 없어 해시 충돌 등으로 인해 조회, 넣기 등의 대부분의 작업 비용이 증가

3. threshold

• = 현재 Capacity X load factor 값
  • 내부적으로 resize() 메서드 실행 시, 해당 HashMap의 확장 여부를 정하는 값

• default 상황에서는 capacity = 16, **load factor = 0.75** → **threshold = 12**가 된다
• 즉, HashMap에 12개 원소가 들어오면 HashMap의 capacity를 2배로 늘리고, 모든 원소를 rehashing해서 리턴
  • 이때도 역시나 새로운 객체 만들어서 참조값 바꿔치기

✅ 구현 방식

1. HashMap도 내부적으로 Node<K,V>의 배열로 구현되어 있다

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    ...
}

• Node 클래스는 key, value, hash, next
• next는 해시 충돌 시, 연결리스트 또는 트리 구조에서 다음 노드의 참조값 저장

2. hash() 메서드로 저장 위치 선정

• 기존 hash()메서드의 문제점
  • 기존 해시함수들은 modular 연산인데 나누는 값이 버킷의 갯수다.
  • 근데 이 HashMap은 확장될 때 2배씩 커지므로 버킷의 수는 $2^n$ 이다.
  • 그래서 modular 연산을 하면 하위 n개 비트만 사용하게 된다
  • 결국 해시 충돌이 쉽게 발생함
• 이를 해결하기 위해 JDK 1.4, Java 5, Java 7까지 보조 해시 함수를 사용했다
• Java 8부터 단순한 새로운 보조 해시 함수 사용
  • key의 hashCode() 값과 이것의 상위 16비트를 XOR 연산한 값이다
• Java 8부터 바뀐 이유
  • Java 8부터는 충돌 발생해도 tree를 써서 충돌로 인한 성능이슈가 완화됨
  • 기존의 보조 해시 함수의 효과가 크지 않아서 -> 이게 주요 이유라고 함

3. resize() 를 통한 해시 버킷 동적 확장

• threshold값 초과하면 resize() 메서드 실행
• 주로 현재 용량의 2배로 Node<K,V>[] Node 배열 생성해서 기존 HashMap의 Node들 모두 rehashing 해서 리턴한다
  • 데이터 개수 예측 가능한 경우 rehashing을 피하기 위해 생성자 인자로 초기 capacity 지정하자

✅ 해시 충돌 해결 방법 2가지

• 자바 HashMap은 Separate Chaining 방식으로 구현
  • 버킷 수가 일정 값 넘어가면 Separate가 더 빠름
  • Open Addressing보다 삭제연산 더 효율적

1. 연결 리스트

• 전체 용량이 64개 미만일 때는 해시 충돌 시 → 항상 연결 리스트로 구현
  • MIN_TREEIFY_CAPACITY = 64

2. 트리

• 전체 용량이 64개 이상이고 연결리스트 길이가 8개 이상인 경우, 기존 연결 리스트에서 red-black tree로 변환
  • TREEIFY_THRESHOLD = 8
• 트리의 노드가 6개 이하인 경우 다시 연결 리스트로 변환
  • UNTREEIFY_THRESHOLD = 6
  • 노드 수가 작으면 트리 구조가 더 비용 많이 발생
• TREEIFY_THRESHOLD와 UNTREEIFY_THRESHOLD의 차이가 2인 이유
  • 차이가 1이면 같은 Node를 넣다뺏다하면 불필요하게 연결리스트 ↔ 트리 변경이 반복되어 성능이 저하되기에

충돌 시 조회 방법

• 우선 key의 hash 값으로 버킷 찾고 equals()로 key 비교하면서 찾기

해시 충돌 정리

• 애초에 resize를 통해 해시 충돌이 줄어들어 연결 리스트 길이도 짧게 유지할 수 있음
• 많이 충돌 발생하더라도 8개 넘어가면 red-black tree로 구현했기에 $O(logN)$ 소요

✅ 주요 메서드의 시간 복잡도

get() , put(), remove(), containsKey()

• 평균 : $O(1)$
• 최악 : $O(logN)$ (8개 넘어가면 tree로 바뀌니깐)

containsValue()

• $O(n)$ : 최악의 경우, map 전체를 순회해야되니까

한 줄 정리

HashMap도 내부적으로 배열로 구현되어 있고, 동적으로 확장 시 2배의 크기로 확장되고, 새로운 객체를 생성해서 리턴한다