[Data Structure] HashMap key, value 데이터 관리

해당 게시물은 기존에 만들어진 자료 구조인 HashMap 내의 데이터가 어떻게 동작하는지를 이해하기 위해 작성되었습니다.
개인적인 바램으로 대규모 시스템에서의 데이터를 다룰 때의 인사이트를 얻을 수 있었으면 좋겠습니다.
후에 인증/인가에 도움이 되실 수 있습니다!! 한번 읽어보시고 간절히 피드백 부탁드립니다!!

HashMap 자료구조를 사용할 때, 어떻게 key, value만 넣으면 데이터가 딱딱 들어가는걸까요?? 내부에서 어떻게 데이터를 다루고 동작하는지에 대해 이해해보도록 하겠습니다!

HashMap

정의 ( Hash + Map )

해싱

: 산술적인 연산을 통해 key가 있는 위치를 계산해서 찾아가는 검색방식

 

해시 함수

: 키 값을 인풋으로, 원소 위치를 아웃풋으로 하는 함수

참고) 해시 함수의 조건
1. hashing의 결과는 정수값 이여야 한다.
2. hashing의 결과는 배열의 크기를 넘어서면 안된다.

실제 HashMap 내부에서도 쓰이는 해시 함수

- 해시 함수는 key를 인풋으로 받으면, (null 이 아닌경우) 먼저, key의 해시코드 자기 자신을 오른쪽으로 16비트 시프트 합니다. 즉, 고정된 0을 왼쪽에서 밀어 넣어 오른쪽으로 비트를 이동시키는 것입니다.

- 그리고, 원래의 해시코드와 시프트된 해시코드를 XOR연산(^) 해서 각 비트가 서로 다르면 1, 같으면 0을 반환합니다.

즉, 키의 해시코드를 활용해 오른쪽 16 비트 시프트 연산과 XOR연산을 통해 해시 충돌의 가능성을 줄이는 것입니다!

 

그런데 해시 충돌이 발생하면, 왜 위험할까??

해시 충돌은 보통, 서로 다른 키가 동일한 해시코드를 가질 때 발생하는데 이가 발생하면 아래 문제점이 야기될 수 있습니다.

1. 충돌이 발생 시, 특정 버킷에 키-쌍 데이터가 쌓임으로써 버킷의 모든 엔트리를 순차적으로 확인해야 합니다. 따라서, 원래 O(1)의 시간 복잡도를 가졌지만 O(n)으로 성능 저하가 발생할 수 있습니다.

 

2. HashMap은 내부의 버킷의 수가 증가함에 따라 데이터 구조가 바뀔 수 있는데, 이 때 해시 충돌이 너무 많이 발생해버리면 버킷 내 엔트리 수가 증가하기 때문에 무의미한 데이터 구조 변화로 인한 메모리 낭비로 이어질 수 있습니다.

해시 충돌이란??
: 해시 함수 내에서, 두 개의 서로 다른 입력값에 대해 같은 출력값을 나타내는 경우

 

 

Map

: - 키-쌍(key-value) 형태로 맵핑되어 있는 자료구조를 뜻합니다.

맵핑이란??
: key, value가 매칭되어 있는 것을 뜻함, 맵핑은 key의 중복을 허용하지 않음

 

Hash + Map

: 그럼 이렇게 정의할 수 있겠습니다. 해시맵은 "키-값(key-value)의 쌍을 구조를 띄는 자료구조로써, 내부적으로 해시함수를 씀으로써, 데이터를 저장하는 자료구조" 입니다.

- HashMap은 Map의 구현체로써 사용이 되고 있었습니다..!!

 

---

추가적으로 알아야 할 키워드

버킷

: key를 인풋으로 하는 해시함수를 통해 얻은 index에 위치하는 저장 공간입니다.

- 이 공간은 특정 key에 해당하는 key-value 쌍을 저장합니다.

- 따라서, key의 같은 해시 값을 지닌다면 여러 key-value 쌍 데이터가 같은 버킷에 위치할 수도 있습니다.

- 정말정말 간단하게 말해서는, 해시 맵 내에서 데이터를 구분할 수 있는 공간이기도 합니다.

 

HashMap의 버킷은 어떻게 저장되어 있을까??

- K는 해시맵에서 유니크한 식별자로 사용되는 key입니다. - (key-value쌍에서의 key)

 

- hash는 key의 해시코드를 저장하는 공간입니다. key가 해시맵 내부의 어떤 버킷에 속할지 결정해야하기 때문에 내부에 저장되고 있는 것 같습니다.

 

- V는 K와 연관된 데이터를 나타냅니다. - (key-value쌍에서의 value)

 

- next는 같은 버킷 내의 다음 노드를 가리키는 포인터 역할을 합니다.

예를 들어, 여러 개의 키-쌍이 같은 해시코드를 가지는 경우 / 해시 코드가 다르더라도 같은 버킷에 매핑될 때 내부적으로 연결 리스트로 구현이 되어있는데 이 때 다음 노드를 탐색하기 위해 존재하는 것 같습니다.



---

HashMap 내부 로직

기본적으로 데이터를 키-쌍 형태의 맵 형태로 저장하는 putVal함수와 그 때의 관리되고 있는 데이터를 살펴보겠습니다.

큰 전체 흐름을 설명드릴게요!!

HashMap 데이터 삽입

put 내부 로직

- 가장 먼저 저희가 흔히 쓰는 put 메서드를 살펴볼게요.

- 이 메서드를 보면, putVal에 key와 value를 전달하고 있는 것을 확인할 수 있는데 독특한 점이 하나 있습니다.

- 바로 hash(key)라는 부분이죠. 이것이 바로 위에서 알려드렸던 해시함수입니다.

- 즉, 사용자가 입력한 key를 이용해서 인덱스를 구하기 위해서 해시함수를 미리 호출하여 그 결과값을 putVal로 넘겨주고 있습니다.

 

 

putVal 내에서 사용되는 변수

- Node<K,V>[] tab : 해시맵의 내부에서 데이터를 관리하기 위한 key-value형태의 버킷입니다.

- Node<K,V> p : 해시맵의 내부에서 버킷 내의 엔트리를 뜻합니다.

- n : 테이블 전체의 길이를 나타냅니다.

- i : 현재 가리키고 있는 인덱스를 나타냅니다.

 

 

1. 해시 테이블의 해당 인덱스에 값을 넣을 수 있는 경우

1-1 해시 테이블 자체가 비어있다면??

1-1 그림

- 먼저, 기존 해시 테이블이 비어있을 수 있기 때문에 해시 테이블 자체가 비어 있는 경우 재할당(resize)을 함으로써, n에 새로운 table 길이를 할당시켜줍니다.

 

어떻게 resize(재할당) 시키는거지??

- 해시맵은 일정 갯수가 되면 버킷의 수를, 일정 갯수 이상일 때 2배 이상 늘린다고 합니다. 그런데, 정확히 어떻게 이를 실행시키는 걸까요??

 

버킷의 용량이 얼마나 될까요?

- "1"을 이진수로 표현하면 0001입니다. 1을 왼쪽으로 시프트시킨다면 10000이 되어 2^4 즉 10진수로 16입니다. 즉, 16 bit 용량입니다.

- 이렇게 초기에는 작은 용량이라 유동적으로 해시맵의 크기를 늘려주는군요!!

 

어떻게 2배를 증가시키는걸까요?

- 해시 버킷의 개수가 일정 개수 이상이 되면 버킷의 수를 두 배로 늘린다 했는데 그럼 일정 개수는 어떻게 정할까? HashMap 클래스에 들어가 load factor에 0.75f이라고 설정된 것을 볼 수 있습니다.

- 이 의미는 데이터의 개수가 현재 버킷 개수의 0.75 즉 3/4 이 되었을 때 2배로 확장하는 것입니다.

 

 

 

1-2 삽입할 인덱스, 값(Node 객체) 생성

1-2 그림

인덱스 결정

- [인덱스] 길이를 가진 배열의 기존 길이(n)-1 과 (기존 key를 통해 해시 함수에 넣어 얻은 인덱스인) hash를 다시 한번 AND 연산합니다.

- 즉, 테이블 크기랑 해시값을 기반으로 해시 테이블 내에 새로운 데이터를 삽입할 위치(인덱스)를 결정합니다. - 해시 충돌 가능성 저하

 

Node 객체 결정

- [노드] 버킷에서 해당 인덱스에 해당하는 엔트리가 비어있다면, 기존에 받은 값(key, value)를 가지고 노드를 생성해서 해시 테이블의 [인덱스] 부분(버킷 내 엔트리)에 새로운 Node 객체를 생성해줍니다.

참고) 만약, 여기에서 버킷이 null이 아닌경우라면, 이미 해시 맵내에 버킷이 존재한다는 것을 의미하겠죠?

 

---

2. 이미 해시 테이블에 값이 존재하는 경우(=비어있지 않은 경우)

: 새로운 데이터(key, value)를 해시맵에 넣기 위해, 해시 맵 내에서 특정 위치를 찾고 그 위치의 키와 값에 접근합니다. 

- e : 해시 테이블에 넣기 위한 버킷내부에 저장되는 엔트리를 뜻합니다.

- k : 현재 처리 중인 엔트리의 키를 뜻합니다.

 

2-1. 동등성, 동치성 비교

- 새로운 데이터를 넣을 자리(인덱스)를 검색하기 위해서 기존 해시 테이블 배열을 관련된 로직(동등성, 동치성을 비교)을 실행시킵니다.

- 동등성과 동치성에 대해 잘 이해가 되시지 않으신다면! 아래 게시물을 확인해주세요!!

Java - equals, hashCode()

 

위 코드는 아래 세가지 과정을 거쳐, 새로운 데이터의 hash와 key를 활용해서 이미 존재하는 객체와 같은지 확인합니다. 왜냐하면, 이미 같은 객체가 존재한다면, 더이상 로직을 거치지 않고 바로 기존 해시맵에 있는 엔트리에 접근해서 새로운 값을 할당시킬 수 있기 위해서입니다!

 

1. p.hash == hash 로 먼저 해시 테이블 내 엔트리의 해시 값과 key를 통해 얻은 해시값을 해시코드이 같은지 확인합니다.

하지만, 해시 충돌로 인해 해시코드가 같다고 해서 같은 객체라고 보장하기는 힘듭니다.

2. 기존 엔트리의 키와 key가 메모리 상에서의 참조하는 메모리 주소가 완전히 같은 객체인지 확인합니다. - 동치성 비교

3. equals 메서드를 통해 두 객체의 값이 같은지 확인합니다. - 동등성 비교

 

---

 

  2-2. 해시 테이블 배열에 기존의 Node객체와 동치성을 띈다면??(=같은 인덱스와 다른 값을 띈다면)

 - 새로들어온 key, value로 새로운 노드를 생성합니다. 와 기존의 객체가 띄면(동등성을 의미), 그 노드를 업데이트 해줍니다.

 

 

 2-2. 두 키가 같은 객체를 띄지 않으면??

- 만약에 기존 해시맵에 없는 생애 처음 들어오는 값이라면, 이제 새로운 데이터가 들어갈 수 있는 엔트리를 찾기 위해 해시맵을 순회하기 시작합니다!

- 연결리스트를 탐색하면서 조건에 맞게 찾은 엔트리(e)를 찾았다면, 이제 그 데이터를 다루기(ex. 갱신)위해 p에 할당시킵니다.

 

 

조건은 어떤게 있을까??

조건 1) 이전과 같이 동일한 객체가 있다면, 바로 찾았음을 감지하고, 곧바로 해당 객체를 다룰 수 있도록 합니다. - 동등성에 관한 충돌 해결

조건 2) 특정 임계값(TREEIFY_THRESHOLD-1)을 넘어버리면, 연결 리스트가 트리 구조로 재구성(treeifyBin) 되는 것도 확인해볼 수 있군요! 리스트는 각 노드가 다른 한노드로만 연결되는 링크를 포함하지만, 트리를 쓰면 각 노드가 여러 노드로의 링크를 포함할 수 있습니다!!) 이러한 방법을 충돌기법 방식 중 Seperate Chaining 기법이라고 합니다.

 

참고) 내부적으로 TREEIFY_THRESHOLD는 8로 지정되어 있으며, 해시 테이블 내 8개 이상의 (키-쌍)데이터가 모이면, 연결 리스트를 트리로 변경합니다. 다시, 버킷의 데이터를 삭제돼어 (키-쌍)데이터가 6개가 되면, 연결리스트로 바뀝니다. 이는 차이가 1일 경우에는 삽입/삭제가 반복되어 불필요한 Seperate Chaning 기법을 방지하기 위함입니다.

 

2-3. 특정 키에 대한 Node객체를 찾았다면??

- 찾은 데이터를 보관(oldValue)해놓고, 새로운 데이터로 갈아끼워줍니다!

- afterNodeInsertion 메서드는 HashMap 클래스에서는 아무 작업도 수행하지 않습니다.. 다만, LinkedHashMap처럼 HashMap을 확장하는 클래스에서 이를 오버라이드 시켜서 L..RU..? 캐시 정책을 수행시킬 수 있다고 합니다..!!

 

LRU 캐시 정책이란??
: 운영체제의 페이지 교체 알고리즘 중 하나로써, 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법

---

3. 검색할 해시 테이블이 트리구조라면??

원래 해당 과정은 로직 상에서는 2-2로 가야했지만, 이해를 돕기 위해 이후에 설명드리는 거에요!

2-3 그림

- 기존 2-2 설명에서 리스트가 너무 길어서, 트리 구조로 이미 바뀐 구조라면 더욱 빠르게 탐색을  하기 위해 TreeNode 인스턴스에 속하는지 검색합니다.

- 만약 트리구조로 되어있다면, 검색 성능 향상 효과를 두둑히 볼 수 있습니다!

 

---

 

4. 모든 연산 마무리 이후...

- 모든 연산이 마무리 된다면 해시맵이 수정된 횟수를 증가시킵니다.

- 만약 16비트(or 향후 늘어난 데이터 용량)보다 현재 사이즈가 크다면, resize() 메서드를 통해 현재 배열의 용량을 늘립니다! 이를 통해서 해시 충돌 가능성을 또 줄이고 데이터 검색의 효율성을 증가시키기 위함입니다!

 

 

 

느낀 점

 

HashMap의 동작원리를 이해하기 위해 코드를 보긴 했지만, 모든 게 깔끔히 이해가 되진 않았습니다. 다만, 그 과정에서 학습한 것을 헛되게 하지 않아야겠다는 생각을 했습니다. HashMap에 데이터를 삽입할 때면, 내부적으로 해시 충돌을 방지하기 위해서 애쓰고 있다는 점을 알게 되었습니다. 해싱 함수나 용량 증가, 자료구조 변경(연결리스트 -> 트리)와 같이 내부 검색 속도를 늘리고, 데이터가 동일한지 검증을 해서 새로운 데이터를 삽입할 위치를 이렇게 많이 생각할 수도 있겠구나를 느낄 수 있었던 좋은 시간이였습니다.

 

HashMap을 데이터 관점으로 조금이나마 알아보았는데.. 4시를 넘었습니다..

그만큼 낯설고 어려운 개념(버킷, 해시, 해시충돌 등등)이 많았었고 자세한 설명이 부족한 부분도 있을 것 같습니다.. 하지만, 이 글을 읽고 여러분이 HashMap을 이해하시는 데에 큰 틀이 잡히셨으면 좋겠습니다..!!

 

아래 공부하는 습관 관련한 게시물 소개드리고 마치겠습니다..!!!

https://www.joongang.co.kr/article/23878585#home

 

 

Reference

https://medium.com/swlh/a-comprehensive-guide-to-hashmap-in-java-363b6a2a2a3e

https://medium.com/shell-tharsis/hash-collision-5891d7dde54f

https://tecoble.techcourse.co.kr/post/2021-11-05-hash-hashmap/

https://lordofkangs.tistory.com/78

https://simplex3510.tistory.com/318

https://tecoble.techcourse.co.kr/post/2021-11-05-hash-hashmap/

https://jjungwoos.tistory.com/24