HashMap 이해

참고 링크

• https://strong-park.tistory.com/entry/HashMap%EC%9D%B4-%EB%8F%99%EC%9E%91%ED%95%98%EB%8A%94-%EC%9B%90%EB%A6%AC%EB%A5%BC-%ED%8C%8C%ED%97%A4%EC%B3%90%EB%B3%B4%EC%9E%90-putVal%EB%A9%94%EC%86%8C%EB%93%9C

• https://mangkyu.tistory.com/430

1. HashSet 초기화

HashSet 은 내부적으로 HashMap 을 사용하는데, HashSet 의 동작방식이 HashMap 의 키 값과 동일하기에, "동일한 코드를 2번 만들 필요가 없지 않을까?" 라는 판단이 있었을 것 같다.

내부 구현을 보면, PERSENT 라는 더미 값을 만들어 값 추가시 사용하는 것을 볼 수 있다.

HashMap 은 배열로 되어 있어서 CRUD 작업에 O(1) 이 걸린다고 알고 있다.

HashMap 의 기본 생성자를 보면 다음과 같이 초기용량(capacity = 16) 과 로드팩터(0.75) 를 설정한다는 것을 알 수 있다.

• 로드 팩터는 용량 대비 실제 데이터 저장 사이즈의 비율(size/capacity) 을 의미하며,

• 해당 비율이 지정된 비율을 넘어서면 capacity 를 2배씩 증가한다.

HashMap 은 내부적으로 버킷의 배열로 이루어져 있다.

• 실제로는 Node 라는 클래스 배열로 선언되어 있다.

Node 는 HashMap 의 내부클래스로 아래처럼 저장되어 있다.

• hash : 키 값의 해시코드

• key : 버킷에 저장된 키

• value : 키에 매핑된 값

• next : 해시 충돌과 연관된 필드

2. HashMap 의 초기화와 버킷 생성

put() 메서드는 내부적으로 hash() 메서드를 호출한 뒤, putVal() 메서드를 호출한다.

hash() : 해시 생성

hash() 메서드를 살펴보면 키 객체의 hashCode() 메서드를 호출한 후 비트 연산자를 통해 새로운 해시 코드를 생성한다.

• 키 객체에서 오버라이딩한 hashCode() 그대로 사용하는 것이 아니다!

• 그 이유는 해시 코드의 분포를 개선하고, 해시 충돌을 최소화하고자 함이다.

putVal() : 데이터 저장 메서드 분석

putVal() 메서드는 크게 3가지 경우의 조건문으로 나뉜다.

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

• 현재 table 이 할당되지 않았거나, 길이가 0이라면 resize() 를 호출해서 새로운 table 을 할당

• 처음 데이터를 넣을 때 테이블을 생성하기 위해서 실행 (초기화 시점에 table 을 할당하지 않는것을 알 수 있다)

2. if ((p = tab[i = (n - 1) & hash]) == null)

• 비트 연산을 사용해 나머지 연산처럼 구현하고((n-1) & hash),

• 해당 인덱스에 버킷의 데이터가 없다면 새로운 Node 를 할당

• 현재 버킷에 처음 들어가는 데이터일 경우 실행

비트 연산자는 어떤 원리로 나머지 연산과 같은 결과를 만들어내는 것일까?

핵심 원리는 n(테이블 크기) 이 항상 2의 거듭제곱(2, 4, 6, 8, 16, 32, ...) 이라는 사실에 있다.

"왜 (n-1) & hash 가 hash % n 과 같을까?"

이 원리를 이해하기 위해서는 두 가지 개념을 먼저 살펴보자.

• 2의 거듭제곱의 이진수 표현

• 비트 AND 연산(&) 의 특징

1. 2의 거듭제곱과 n-1 의 이진수 표현

n 이 2의 거듭제곱일 때, n 과 n-1 을 이진수로 표현하면 아주 특별한 패턴이 나타난다.

예를 들어, n = 16 이라고 가정해보자.

• n = 16 의 이진수 : 0001 0000

• n-1 = 15 의 이진수 : 0000 1111

여기서 확인할 수 있듯이 n이 '1' 뒤에 '0' 이 쭉 붙는 형태라면, n-1은 n의 자릿수만큼 모두 '1'로 채워진 형태가 된다. 이것이 바로 2의 거듭제곱 이진수의 패턴이다.

2. 비트 AND 연산(&) 의 작동 방식

비트 AND 연산은 두 개의 비트를 비교하여 둘 다 '1'일 경우에만 '1'을 반환하는 연산이다.

실제 예시로 살펴보기

이제 이 두가지 원리를 조합해서 실제 코드가 어떻게 동작하는지 보자.

• 테이블 크기 : n = 16

• 어떤 객체의 hash = 27 이라고 가정해보자.

우리가 찾고 싶은 인덱스 i는 27 % 16의 결과인 11이 나와야 한다.

이제 비트 연산으로 동일한 결과를 얻어보자.

1. 값을 이진수로 변환한다.

• hash = 27 → 0001 1011

• n - 1 = 15 → 0000 1111

2. 두 값을 AND(&) 연산 후 10진수로 변환하자.

• 0000 1011 -> 11

정확히 27 % 16 의 동일한 11 이 나왔다.

왜 이렇게 사용할까?

가장 큰 이유는 성능 때문이다. CPU 는 나눗셈과 나머지 연산(%) 보다 비트 연산(&) 을 훨씬 더 빠르게 처리한다.

1. 나머지 연산 - 여러 클럭 사이클이 필요한 작업

CPU 가 나머지(%) 연산을 수행할 때는 실제로는 나눗셈을 해야 한다. a 를 n 으로 나눈 뒤, 그 나머지를 구하는 과정이다.

CPU 에게 나눗셈은 꽤나 부담스러운 작업이다. 마치 우리가 긴 나눗셈을 푸는 것과 비슷하게 여러 단계를 거친다.

1. 반복적인 뺄셈과 비교 : 내부적으로 숫자를 여러번 빼고, 비교하고, 자릿수를 이동시키는(shift) 복잡한 마이크로 코드 알고리즘이 실행된다.

   1. CPU 입장에서 나눗셈은 사람 입장에서의 나눗셈이 아니라,

   2. 나누는 숫자만큼 반복적으로 뺀다.

2. 많은 클럭 사이클 소모 : 이 과정은 CPU의 동작 단위인 클럭 사이클(clock cycle)을 수십, 많게는 수백 번까지도 소모할 수 있다.. CPU가 한 클럭에 하나의 단순한 명령을 처리한다고 가정하면, 나눗셈은 수십 개의 명령을 처리하는 것과 비슷한 시간이 걸리는 셈이다.

2. 비트 AND 연산(&) - 단 1클럭 사이클에 끝나는 작업

반면, 비트 AND 연산은 CPU 에게 가장 기본적인 작업 중 하나이다.

1. 단순한 논리 게이트(Logic Gate): CPU 내부의 ALU는 AND, OR, NOT 같은 논리 연산을 수행하는 매우 단순하고 빠른 하드웨어 회로(논리 게이트)로 구성되어 있다.

2. 병렬 처리: hash & (n-1) 명령을 받으면, CPU는 두 숫자의 각 비트 쌍을 수많은 AND 게이트에 동시에 입력합니다. 전기 신호가 회로를 통과하기만 하면 즉시 결과가 나옵니다.

3. 단일 클럭 사이클: 이 모든 과정은 일반적으로 단 1 클럭 사이클 만에 완료된다. 나눗셈에 비해 비교할 수 없을 정도로 빠르다.

HashMap 과 같이 수많은 데이터에 대해 해시값을 계산하고 인덱스를 찾아야 하는 자료구조에서는 이런 작은 성능 차이가 전체 시스템의 속도에 큰 영향을 미칠 수 있다.

3. else

• value 를 대체하거나, 해시충돌이 발생할 때 실행

resize() : 데이터 추가를 위한 준비

처음 데이터를 넣었을 때는 table 이 할당되지 않은 상태이기 때문에, resize() 를 통해 tab 변수를 초기화 해주어야 한다.

그러면 resize() 메서드 호출이 어떻게 되는지 살펴보자.

1. 현재 사용중인 table 의 용량과 임계값을 old 변수에 할당하고, new 변수의 값을 0으로 초기화해준다.

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;

2. new 변수에 값을 초기값으로 할당해준다.

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

• 기본 용량 상수 초기화 부분을 살펴보면 그냥 16으로 초기화하는 것이 아니라, 비트 연산을 사용하는 것을 볼 수 있다.

• 이렇게 표현하는 의도는 HashMap 의 용량이 2의 거듭제곱이어야 한다는 중요한 설계 규칙을 시각적으로 제공한다.

• 기본 로드펙터 상수는 0.75로 초기화 되어 있는 것을 확인할 수 있다.

3. 임계값을 새로 계산된 값으로 할당하고, newCap 의 용량만큼 새로운 테이블을 생성한다.

threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

• threshold : resize() 가 필요한 시점의 임계값 (용량 * 로드펙터)

• 임계값은 HashMap 의 용량에 따라 동적으로 조절되고, 해시 충돌 등의 상황에서 동적으로 조절된다.

가장 처음 resize() 를 통해서 버킷이 생성된다고 생각하면 된다.

resize() 할 때, 데이터를 이동하는 원리는 무엇이고, 왜 그것이 가능한 것인가?

HashMap 의 라사이징 시 데이터 이동 원리는 비트 연산의 특성을 매우 효율적으로 활용하는 것이다. 모든 데이터의 해시를 다시 계산하여 새로운 인덱스를 찾는 비효율적인 방식 대신, 기존 계산 결과를 최대한 재사용하는 아주 영리한 방법이다.

이것이 가능한 이유는 HashMap 의 용량(capacity) 가 항상 2의 거듭제곱으로 증가하기 때문이다.

왜 리사이징을 할까?

먼저 리사이징이 일어나는 이유는 HashMap 에 데이터가 계속 추가되어 로드팩터, 즉 임계값을 넘어서면 데이터 충돌 가능성이 높아진다. 이로 인해 하나의 인덱스에 여러 데이터가 연결 리스트(LinkedList)나 트리 형태(Tree)로 늘어져 검색 성능이 저하된다.

이를 해결하기 위해, 용량을 2배로 늘리고 데이터를 더 넓은 공간에 재배치하여 충돌을 줄이고 성능을 다시 O(1) 에 가깝게 유지하는 것이 바로 리사이징이다.

데이터 이동의 핵심 원리 : 단 하나의 '비트' 확인

용량이 2배로 늘어날 때, 예를 들어 16에서 32로 늘어난다고 가정해보자. 인덱스를 결정하는 계산이 어떻게 변하는지 살펴보자.

• 기존 용량 (16): 인덱스 = hash & (16 - 1) → hash & 15

  • 15의 이진수: 0000 1111

• 새로운 용량 (32): 인덱스 = hash & (32 - 1) → hash & 31

  • 31의 이진수: 0001 1111

두 비트 마스크를 비교해보면, 새로운 마스크(0001 1111) 는 기존 마스크(0000 1111) 보다 왼쪽에 1인 비트가 하나 더 추가되었다. 바로 이 새로운 비트가 모든 것을 결정한다.

리사이징 시, HashMap 은 각 데이터의 기존 해시값(hash) 를 가져와 이 새로운 비트 위치의 값이 0인지 1인지 확인한다.

Case1 : 새로운 비트 위치의 해시값이 0인 경우

해당 위치의 비트가 0이라면, 새로운 마스크(0001 1111) 와 AND(&) 연산을 해도 결과는 기존 인덱스와 동일하다.

• 예시 : hash 의 5번째 비트가 0

• 결론 : 이 데이터는 원래 있던 인덱스에 그대로 머문다.

Case2 : 새로운 비트 위치의 해시값이 1인 경우

해당 위치의 비트가 1이라면, 새로운 마스크(0001 1111)와 AND(&) 연산을하면 그 비트가 1로 살아남게 된다. 이 1의 값은 10진수로 정확히 '기존 용량(old capacity)' 과 같다.

• 예시 : hash 의 5번째 비트가 1

• 결론 : 이 데이터는 기존 인덱스 + 기존 용량 위치로 이동합니다.

왜 이것이 가능한가?

이 모든 과정이 가능한 근본적인 이유는 바로 HashMap 의 용량이 항상 2의 거듭제곱 형태를 유지하기 때문이다.

1. 예측 가능한 패턴: 용량이 2배가 되면 인덱스 계산에 사용되는 비트가 정확히 하나만 늘어납니다. 이 덕분에 기존 인덱스에서 그대로 머물거나, 혹은 기존 용량 만큼 떨어진 곳으로만 이동하는 매우 단순하고 예측 가능한 패턴이 생깁니다. 만약 용량이 10에서 20으로 늘어난다면 이런 비트 연산 트릭은 사용할 수 없습니다.

2. 재해싱(Rehashing)의 불필요: 이 원리 덕분에 모든 데이터의 해시값을 % newCapacity 와 같이 복잡하게 다시 계산할 필요가 없습니다. 단순히 기존 해시값의 특정 비트 하나만 확인하면 되므로, 리사이징 과정이 엄청나게 빨라집니다.

리사이징 시 모든 인덱스의 해시값을 비교해 인덱스를 재설정하는 작업이 무겁지 않은가?

여기서 중요한 포인트는 '모든 데이터를 확인하는 작업은 피할 수 없다' 는 것이다. 어쨌든 모든 데이터를 새로운 배열로 옮겨야 하지 않는가.

리사이징 최적화는 "데이터를 확인하는 과정" 을 생략하는 것이 아니라, "각 데이터를 어디로 옮길지 결정하는 과정" 을 극도로 빠르게 한 것이다.

• 비효율적인 방식 : 모든 데이터에 대해서 hash % newCapacity (느린 나머지 연산) 를 다시 수행해서 새로운 위치를 계산한다.

• 효율적인 방식(현재 HashMap 방식) : 모든 데이터에 대해서 hash & oldCapacity (매우 빠른 비트 연산) 을 수행하여 위치를 결정한다.

결론적으로, 리사이징은 모든 데이터를 순회해야 하므로 어느 정보 비용이 드는 작업인 것은 맞다. 하지만 그 과정에서 이루어지는 각각의 연산을 가장 빠른 비트 연산으로 대체함으로써, 피할 수 없는 작업을 최대한 효율적으로 수행하도록 설계한 것이다.

3. HashMap 에 데이터 저장하기

데이터 저장하기1 (첫번째 데이터)

resize() 후 아직까지는 버킷을 생성했을 뿐, 데이터를 버킷에 넣지는 않았다.

그렇다면 이제 데이터가 저장되는 과정을 살펴보자.

가장 처음 임의의 데이터를 넣어보자.

// map.put 이라는 행위에 집중하자. 
map.put(new Person("gugbab1", 29), "person1"); 

위 코드를 실행하게 되면 putVal() 메서드의 2번째 조건문에 들어가게 된다.

• table 변수는 resize() 메서드를 통해 크기가 16인 Node 배열로 초기화되었다는 것을 기억하자.

• 인덱스 i 는 비트 연산(&) 을 통해 나머지 연산과 동일한 결과를 갖는다.

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

가장 처음 데이터를 넣게 되면 들어있는 원소가 없으므로, 버킷에 노드를 삽입하는 코드가 실행된다.

데이터 저장하기2 (기존과 다른 데이터)

그러면 두 번째 데이터를 넣으면 어떻게 되는지도 살펴보자.

// map.put 이라는 행위에 집중하자. 
map.put(new Person("gugbab2", 30), "person2"); 

위 코드를 실행하게 되면 해시 충돌이 발생하지 않는 경우 putVal() 메서드의 2번째 조건문에 들어가게 된다.

• 해당 케이스에서는 해시 충돌이 발생하지 않았다고 가정하자.

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

해시 충돌이 발생하지 않은 경우, 해당 인덱스에 가장 처음 들어가는 데이터이기 때문에, 버킷에 노드를 삽입하는 코드가 실행된다.

데이터 저장하기3 (동등한 세번째 데이터, value 대체)

그렇다면 동등한 Key 값을 가진 데이터를 저장할 땐 어떻게 동작하는지 살펴보자.

// map.put 이라는 행위에 집중하자. 
map.put(new Person("gugbab1", 29), "person3"); 

putVal() 메서드의 첫번째, 두번째 조건에 걸리지 않기 때문에 else 부분으로 오게되고, else 부분은 3가지 부분으로 나뉜다.

1. 기존 노드와 해시 값이 같고, 키 값이 동등한 경우 e 에 기존 노드를 할당한다.

• 동등한 객체일 경우, 값(value) 대체

2. TreeNode 클래스인 경우 트리 기반의 삽입 로직을 수행

• 해시 충돌이 발생했는데, p 가 트리노드 기반일 경우

3. 연결 리스트인 경우, 반복문을 통해서 노드를 탐색하면서 새로운 노드를 추가

• 해시 충돌이 발생했는데, p 가 트리노드 기반이 아닐 경우

해당 케이스의 경우 첫번째 조건을 타게 되고, e 값을 기존 노드 값으로 초기화 후 e 가 null 이 아닐 경우 값을 대체해주는 과정을 거친다.

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

동등한 키에 대해서 새로 들어온 값으로 덮어쓴다.

• map.put() 메서드에 같은 키를 사용해 값을 넣었을 경우, 반환 값으로 기존 값이 리턴되는 이유가 oldValue 가 리턴되는 부분 때문이다.

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

데이터 저장하기4 (해시충돌)

동등한 객체를 집어넣을 때는 값(value) 을 덮어쓰는 것을 확인했다. 그러면 해시가 동일하고 내용은 다른 상황에서 어떻게 동작할까?

결론적으로 각 Node 는 기본적으로 연결리스트로 저장한 뒤, 연결리스트의 길이가 일정 임계값을 넘으면 해당 버킷의 노드들을 Tree 구조로 변환한다.

일반적으로 HashMap 은 내부적으로 배열(Node 의 배열)로 되어 있어서 CRUD 작업에 O(1) 이 걸린다고 알고 있다.

하지만 해시가 충돌하는 경우 배열의 인덱스마다 새로운 자료구조를 사용해 데이터를 저장하게 되고 자료구조에 따라 다음과 같은 성능 차이가 난다.

• 연결 리스트 : O(N)

• Tree : O(log N)

그러면 해시값이 동일한 네번째 데이터를 넣어면 어떻게 되는지도 살펴보자.

// 해시 값이 동일하다고 가정! 
// 여기서 말하는 해시값은 객체 내부 hashCode() 메서드가 아니라, 
// HashMap.hash() 메서드에서 나온 값을 의미
map.put(new Person("gugbab4", 100), "person4"); 

일단 해시 충돌이 난 상황이고, 트리노드 기반이 아니기 때문에 3번째 else 문부터 시작할 것이다.

else 문을 순서대로 살펴보자.

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

binCount 는 연결리스트의 노드 개수를 의미한다. 0부터 시작해서 연결 리스트를 순회하는 반복문으로서 사용된다.

for (int binCount = 0; ; ++binCount) {

현재 노드 p.next 를 e 에 할당한 뒤, null 인 상황이므로 next 에 새로운 노드를 생성한다.

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}

하지만, 해시충돌이 계속되고 연결리스트의 길이가 임계값(TREEIFY_THRESHOLD - 1)에 다다를 경우, 버킷의 노드들을 트리노드로 변환한다.

• 임계값이 8을 넘으면 treeifyBin() 메서드가 실행되면서 기존의 노드들을 트리노드로 변환한다.

• 원래 Java7 까지는 노드를 연결리스트로만 저장해서 시간복잡도가 O(N) 으로 고정이었다.

• 하지만 Java8 부터는 임계값을 넘어설 경우 트리노드로 변환되며 시간복잡도가 O(logN) 으로 변경되었다.

하지만, treeifyBin() 메서드가 실행된다고 해서 무조건 연결리스트가 트리노드 구조로 변경되는 것은 아니다.

HashMap 전체 크기가 64보다 적은 경우는 먼저 해시 버킷 배열을 확장한다.

• 왜냐하면 해시 버킷 배열 크기 자체가 작은 경우에는 충돌이 자주 발생할 수밖에 없기 때문이다.

Java 는 이러한 방향으로 HashMap 내부를 구현하여 최적화를 진행하고 있으며, 버킷 충돌이 자주 발생하는 경우 트리화를 통해 시간 복잡도를 O(log N) 까지 낮출 수 있었다.

하지만 이 때 키가 String, Number 클래스 같은 Comparable 타입이어야만 트리로 변환이 가능하다는 점은 주의할 필요가 있다!