HashMap이 저장되는 형태와 원리, heap, stack 메모리구조

 

 

자바 11 에서 HashMap 라이브러리를 살펴보았습니다.

 

 

 

 

최종 형태부터 보자면 Array가 있고 거기에 LinkedList와 Red-Black Tree가 주렁주렁? 달려있는 모양입니다. 열매마다 key, value가 저장되어 있습니다.

 

 

 

1. 기본 방식

 

일반적인 HashMap을 사용하는 코드입니다.

 

메모리영역을 그려보면 다음과 같습니다.

 

new HashMap<>(); 을 하면 HsahMap 인스턴스가 생성됩니다.

 

put을 하게 되면 HsahMap 인스턴스 안에 Bucket Array가 생성됩니다. 한칸 한칸을 버킷이라고 합니다.

Bucket Array 는 Entry 객체 array 입니다.

 

Bucket Array의 최초 길이는 16입니다.

 

 

Node 객체는 Entry 인터페이스의 구현체입니다. key.hashCode()로 생성된 hash 값, key, value, 다음 Entry를 가리키는 포인터 개념의 next 필드를 가지고 있습니다.

 

 

put으로 들어온 데이터를 Butket Array 중 어느 버킷에 저장할지 정하기 위해 hash 값을 사용합니다.

비트연산을 통해 생성된 hash값의 하위 4비트를 인덱스로 가집니다.

 

n 은 Butket Array의 길이입니다. 최초 값이 16이니까 1을 뺀 15 = 1111 과 hash를 and 연산한 것입니다. and 연산은 두 값이 모두 1이어야 1이 나오는 연산자입니다. 그래서 hash 값의 하위 4비트를 취한 것과 같습니다. 그래서 4비트의 최솟값, 최대값인 0~15를 인덱스로 가지게 됩니다.

 

그런데 hash값은 다를지언정 하위 4비트가 같아서 같은 인덱스가 나올 수도 있겠죠?

이를 해시 충돌 이라고 합니다.

이렇게 이미 해당 버킷에 Entry Instance가 존재하는 경우 LinkedList 형태로 추가하게 됩니다.

 

 

 

 

 

2. Bucket Array 길이 늘리기, Entry 재배치

 

Bucket Array의 최초 길이는 16이라고 했습니다. 하지만 데이터가 계속 추가되면 Entry가 너무 많아져 주렁주렁 늘어지게 될 것입니다. 이를 방지하기 위해 특정 조건이 되면 길이를 늘리는 로직이 있습니다. 여기에 사용하는 "임계값(threshold)" 라는 개념이 있습니다. 현재 Bucket Array 길이 대비, Entry 개수가 일정 개수 이상이 되면 길이를 늘리는데 사용되는 값입니다.

 

현재 Bucket Array 길이 * 로드팩터(부하율) = 16 * 0.75 = 12개가 되면 배열의 길이를 2배로 늘리게 됩니다.

 

 

이렇게 해서 Bucket Array 길이가 32가 되었다면, 다음 임계값은 24입니다. 전체 Entry 개수(put한 데이터 수)가 24개가 되면 Bucket Array 길이는 64가 되고 임계값은 48이 됩니다.

 

최초 임계값을 구할때는 위의 곱하기 연산으로 12를 구하고 그 다음부터인 24, 48 ~을 구할때는 비트 연산을 사용합니다.

현재 임계값 12 = 1100 에서 비트 쉬프트 왼쪽으로 1자리 = 11000 = 24

 

좀 더 정확히 말하면 기존보다 2배의 길이를 가지는 새로운 Bucket Array를 만듭니다.

(newCap은 2배가 된 길이 입니다.)

 

그리고 기존 Entry들을 새로운 Bucket Array에 재배치합니다.

이때도 최초와 같이 비트연산으로 인덱스를 정합니다.

2배가 되었으니 32-1 = 11111

즉 hash값의 하위 5비트를 취하여 0~31 사이의 인덱스(버킷)으로 재배치합니다.

 

이렇게 새로운 Bucket Array로 재배치도 끝났다면 기존의 16의 길이를 가졌던 Array는 더이상 참조되지 않아 가비지 컬렉터에 의해 삭제됩니다.

 

 

 

 

3. LinkedList를 Red-Black Tree로 변환하기

 

위에서 인덱스가 같으면(동일한 버킷이면) LinkedList로 추가한다고 했습니다. 하지만 계속계속 추가하면 그것도 효율이 떨어지겠죠? 위에서 배열의 길이를 늘리는데 사용되는 임계값이 있었듯, 트리화를 위한 임계값도 있습니다. 그래서  LinkedList가 이 임계값인 8개가 되면 Red-Black Tree로 변환합니다. O(N) -> O(logN)

 

그런데 무조건 8개 이상이라고 변환 하는 것은 아니고 조건이 하나 더 있습니다. Bucket Array의 길이가 64 이상이어야 합니다. 64 이상이 되지 않으면 길이만 늘리고 LinkedList는 유지합니다. (더 성장해서 돌아와라!)

 

 

Bucket Array의 길이 64, 해당 버킷의 LinkedList 8개 라는 조건을 만족하면, 위와 같이 Red-Black Tree에 필요한 필드를 추가로 가지는 Entry Instance를 생성합니다.

 

 

 

 

 

 

참고 사이트

 

https://velog.io/@gkdbssla97/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-HashMap-%EB%82%B4%EB%B6%80-%EB%8F%99%EC%9E%91-1-feat.-Java

 

https://velog.io/@gkdbssla97/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-HashMap-%EB%82%B4%EB%B6%80-%EB%8F%99%EC%9E%912-feat.-Java