[자료구조] HashMap 파헤치기 1 (Linked List + Red Black Tree)

 

 

 

 

나는 HashMap이 잘 이해되지 않았다.

 

인덱스가 없으니 배열이나 List에 비해 확실히 더 어렵고 직관적으로 이해하기가 힘들었다. 그래서 오늘 HashMap 자료구조가 어떤 원리로 돌아가는지 파헤쳐볼까 한다.

 

 

Map

Map 자료구조의 특징은 키(Key)와 값(Value)이다.

키를 통하여 값에 접근할 수 있는 구조이다.

 

List나 배열은 인덱스로 접근한다. 인덱스는 단순히 순서만 나타낸다. 그러나 Map의 키는 개발자가 의미를 부여할 수 있다.

 

 

 

 

현재 내가 포스팅하고 있는 글의

글쓰기 창의 주소이다.

 

Redirect = Write & categoryNo = 6

 

Redirect와 categoryNo는 Key이다.

그리고 Write와 6은 Value이다.

 

 

이런 원리로 key는 개발자가 부여한 의미를 갖고 그 key는 value를 나타낸다. 이와 같이 key와 value가 쌍을 이루는 자료구조가 Map이다.

 

 

HashMap

JAVA에서 Map은 인터페이스이다.

Map의 구현체 중 하나가

HashMap이다.

 

데이터를 저장하려면 자료구조가 필요하다. HashMap은 자료구조로 배열(array)을 사용한다. 배열은 '인덱스'를 통해 바로 접근이 가능하다는 장점이 있다. HashMap은 해싱(Hashing)을 통해 Map 데이터가 저장 될 위치의 인덱스를 구한다. 그래서 이름이 HashMap이다.

 

key(X)를 해싱함수(function)에 넣어 인덱스(Y)를 산출한 후, 해당 인덱스에 Map 데이터를 저장하는 것이 HashMap의 기본 원리이다.

 

 

 

해싱은 인덱스를 구하는 것이 목적이다. 그러므로 지켜야 될 조건이 있다.

 

1. hasing의 결과는 정수여야 한다.

2. hasing의 결과는 배열의 크기를 넘어서면 안 된다.

 

JAVA의 컬렉션 프레임워크 HashMap 클래스에서 자세히 확인해보자.

 

 

1. hasing의 결과는 정수여야 한다.

 

 

key를 매개변수로 받은 hash 함수는 key의 해쉬코드와 key의 해쉬코드를 오른쪽으로 16비트 shift한 결과를 ^(xor)한 값을 반환한다. 이는 정수(int)다.

 

2. hasing의 결과는 배열의 크기를 넘어서면 안 된다.

 

 

hash는 hash(key)의 반환값이다. 빨간상자를 보면 인덱스 i 에 (n-1) & hash 의 결과를 넣어주는 것을 볼 수 있다. (n-1)&hash 는 hash%n과 같은 결과를 낸다. n은 tab.length로 배열의 크기를 나타낸다. hash에 n을 % 연산하면 그 결과는 n보다 작은 정수가 된다. 그러므로 배열의 크기보다 작은 정수가 인덱스가 된다.

 

hash%n이 아닌 (n-1)&hash가 사용된 이유는 비트연산이기에 속도면에서 더 좋은 성능을 보이기 때문이 아닐까? 추측해본다. 그리고 hash%n과 (n-1)&hash가 같은 결과를 내는 이유는 잘 모르겠다.

 

Why HashMap insert new Node on index (n - 1) & hash?

 

해당 사이트에 그 이유가 나와 있으니, 궁금하신 분은 참고하기를 바란다.

 

 

이렇듯, HashMap은 key만 있다면 해싱함수를 통해 바로 해당 인덱스의 위치로 이동할 수 있다. key를 통해 인덱스를 산출 후, 데이터에 접근하면 시간복잡도가 O(1)이다. HashMap의 데이터접근성능이 정말 뛰어나다고 할 수 있다.

 

여기서 이 배열을 버킷(bucket)이라 부른다. 앞으로 HashMap에 사용된 배열을 버킷이라 부르겠다. 버킷 안에 저장된 Map 데이터를 자바에서는 Node객체로 만들어 관리한다.

 

 

 

 

실제로 HashMap은 Node 배열을 table이라는 이름으로 관리한다. 이 table이 버킷이다.

 

 

 

버킷 안에 저장된 데이터는 Node 객체이다. Node 객체는 필드로 hash값, key, value 그리고 next가 있다.

 

충돌(collision)

 

key만 있으면 해싱함수를 통해 바로 데이터에 접근할 수 있다는 장점이 있지만 이로 인해 생기는 단점이 있다. key는 무궁무진하지만 인덱스는 한계가 있다.

 

 

 

key는 문장부터 숫자까지 무한대로 존재한다. 하지만 인덱스는 배열의 크기보다 작은 정수로 한정되어 있다. 그러므로 key들 사이의 충돌(collision)은 불가피하다. 서로 다른 key들이 같은 인덱스를 부여받는 것이다.

 

그래서 JAVA에서는 크게 두 가지 방법으로 충돌을 관리한다.

 

threshold

 

첫 번째는 버킷 사이즈를 조절하는 것이다. 버킷의 75%가 채워지면 충돌 확률은 크게 늘어난다. 그래서 기본적으로 HashMap은 버킷의 입실률이 75%가 넘으면 버킷의 사이즈를 늘린다.

 

 

버킷을 생성할 때, threshold를 지정한다. threshold란 버킷의 크기를 resize()할 때의 임계점을 의미한다. 만약 threshold가 12이면 버킷 안에 저장된 데이터가 12개를 넘어가면 버킷의 사이즈를 2배 더 늘린다.

 

threshold( newThr )는 빨간 상자에서 처음 크기가 지정된다.

 

(int)DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY

 

DEFAULT_LOAD_FACTOR 는 0.75

DEFAULT_INITIAL_CAPACITY는 16이다.

 

그러므로 threshold는 12가 된다.

 

고로 HashMap이 처음 생성되면 버킷사이즈는 16이고 16의 75%가 임계점이므로 threshold는 12가 된다. 만약 버킷에 데이터가 저장되어 그 수가 12를 넘어가면 버킷의 사이즈는 원래 사이즈의 2배인 32가 된다. 그럼 threahold도 2배 커진 24가 된다.

 

 

HashMap에 정수를 두 배 늘린 때, << 쉬프트 연산자를 사용한다. 정수를 왼쪽으로 1비트 이동시키면 원래값의 두 배가 된다. 0000 1011 은 11이다. << 1하면 0001 0110이된다. 이는 22이다. 이렇게 두 배가 된다.

 

 

newCap이 oldCap의 << 1 하여 두 배 사이즈로 만든 후, 새로이 배열(버킷)을 새로 생성한다. 이렇듯 JAVA는 HashMap의 버킷 입실률이 75%가 넘지 않도록 버킷의 사이즈를 조절하면서 충돌이 일어나지 않도록 관리한다.

 

Linked List + Red Black Tree

 

버킷의 사이즈를 조절한다고 충돌이 안 일어나는 것은 아니다. 그래서 충돌 시 어떻게 대응하는지 아는 것이 중요하다. JAVA에서는 충돌의 횟수에 따라 충돌한 데이터들의 저장방식을 달리 한다.

 

충돌 초기에는 Linked List 방식으로 충돌에 대응한다. 이를 separate chaining 방식이라 부른다.

 

 

버킷이 가리키는 Node 객체는 next 필드를 갖고 있다. 어떤 Node 객체와 인덱스가 같아 충돌이 일어나면, 이미 자리잡고 있던 Node 객체의 next 필드 안에 새로 들어온 Node 객체의 참조 주소를 저장한다.

 

 

이렇게 Node 객체는 충돌을 대비해 next 필드를 갖고 있다.

 

 

버킷에 객체를 저장하는 메소드인 putVal 메소드이다. 빨간 상자를 보면 binCount가 있다. binCount는 충돌이 일어나는 횟수를 체크한다. 충돌횟수가 ( TREEIFY-THRESHOLD -1 ) 을 넘으면 Linked List 방식의 데이터 저장방식은 효율이 떨어진다.

 

 

 

 

만약 어떤 Node 객체가 n번 충돌되어 n번째 Node의 next에 저장된다면 해당 Node를 탐색하는데 시간복잡도는 O(n)이 된다. 충돌이 많아지면 많아질수록 그 효율이 떨어지는 것이다. 그래서 일정 충돌 수가 넘어가면 데이터 저장방식이 바뀌는데 그것이 Red-Black Tree이다.

 

Linked List 방식은 Node 객체여야 하지만 충돌이 심해져 Red-Black Tree로 바뀌면 단순 Node 객체로는 Red-Black Tree를 구현 할 수 없다. 그래서 Node 객체를 TreeNode 객체로 바꾸어 주어야 한다. 말이 바꾸어 준다는 의미지 실상은 Node 객체에 기능을 몇 가지 추가한 것이다.

 

 

 

TreeNode 클래스는 LinkedHashMap의 중첩 클래스 Entry를 상속하는데 Entry 클래스는 HashMap의 Node 클래스를 상속한다. 그래서 자식 클래스인 TreeNode의 객체가 생성되면 super()에 의해 부모 클래스인 Node의 객체도 생성된다.

 

한마디로 TreeNode 객체와 Node 객체는 연결되어 있다는 말이다.

 

 

treeifyBin 메소드는 Node객체를 TreeNode객체로 바꾸어 주는 메소드이다.

 

 

replacementTreeNode 메소드에 의해 Node객체가 TreeNode 객체로 바뀐다. do-while 반복문의 첫 반복일 때, 실인수로 들어간 e는 충돌이 발생한 인덱스에 저장된 첫번째 Node 객체이다. do-while 반복문을 돌면서 인덱스에 Linked List 방식으로 저장된 Node들을 하나씩 TreeNode로 바꾸어준다.

 

 

 

 

replacementTreeNode 메소드에서 TreeNode 객체를 생성하는데 생성자의 매개변수로 Node 객체의 hash 값, key값, value값을 받는다. 이는 TreeNode 클래스의 부모클래스인 Node 클래스의 객체를 생성할 때 사용될 실인수다.

 

 

 

 

이로써, 기존의 Node 객체는 TreeNode 객체와 연결이 되면서 Red-Black Tree를 구성할 수 있는 요소들을 갖추게 된다. Node 객체들을 TreeNode 객체로 모두 전환을 완료하면, treeify 메소드를 통해 트리화를 마무리 한다.

 

 

 

treeify 메소드에서는 parent, left, right 필드와 red 필드에 Red-Black Tree 로직을 위한 적절한 값을 넣어주는 작업을 한다. replacementTreeNode 메소드로 Node 객체를 TreeNode 객체로 전환하고 treeify 메소드를 통해 Red-Black Tree 로직을 위한 적절한 데이터를 TreeNode 필드 안에 채우면 트리화는 완료된다.

 

이렇게 트리화가 완료되면, 데이터를 탐색하는데 걸리는 시간 복잡도는 O(log n)이 된다. (왜 O(log n)이 되는지는 다음 포스팅에서 정리하겠다.) 그러므로 Linked List의 O(n)보다 효율적인 자료구조가 되는 것이다.

 

---

정리

 

1. HashMap은 해싱함수를 통해 인덱스를 산출한다.

2. HashMap은 인덱스를 통한 접근으로 시간 복잡도 O(1)의 빠른 성능을 자랑한다.

3. key는 무한하지만 인덱스는 한정되어 있어 충돌은 불가피하다.

4. 충돌을 줄이기 위해 HashMap은 버킷의 사이즈를 조절한다.

5. 충돌이 일어날 시, 충돌 수가 적으면 LinkedList 방식으로 충돌된 객체들을 관리하다가, 임계점을 넘으면 Red-Black Tree 방식으로 객체들을 저장한다.

6. 시간 복잡도는 Linked List가 O(n), Red-Black Tree가 O(log n)이다.

 

 

---

 

참고자료

 

 

What Are Initial Capacity And Load Factor Of HashMap In Java?

why is loadFactor in HashMap is set to 0.75 by default?

Why use 1<<4 instead of 16?

해시맵에 있는 tiebreakorder는 어떤 메소드일까요?

java hashset은 key의 해쉬 코드가 모두 같을 때 최악 복잡도가 어떻게 될까요?

Why HashMap insert new Node on index (n - 1) & hash?