Java - HashMap (feat. LinkedList, Tree.. maybe Later)

지난 글에서는 ArrayList 를 까보면서 native 메서드에 대해 잠시 다루어보았다.

이번 글에서는 직접 HashMap 을 구현해보도록 하겠다.
JDK 를 까보면서 그리고 여라 다른 블로깅을 참고하면서 내 방식으로 구현해 보았다.



우선, 핵심을 먼저 정리하고 작성해보겠다.

HashMap 은 Key Value 저장소이다. 분할상환방식에 의해서 get() put() 메서드는 상수 시간의 시간복잡도 O(1) 을 가진다.

HashMap 은 내부적으로 key, value 를 지닌 Node 의 배열을 가진다. Node 의 개념과 일치하는 class 는 Entry<K, V> class 이다. HashMap 은 get(), put() 메서드 호출 시  객체의 hashcode 를 통해 index 를 계산하고  Node 배열의 Node 를 배치시킨다. 



그렇다면 같은 index 를 가지는 객체들은 어떻게 관리를 할까? 바로 LinkedList 를 배열의 index 마다 가지며, 2차원 형태의 테이블을 이루게 된다.

Image for post

아래는 JDK 11 버전의 HashMap 을 직접 까보았다. 아래와 같이 Node 는 Map.Entry<K, V> interface 를 구현하고 있다. 그리고 필드로는 hash, key, value, 그리고 LinkedList 이기에 next 를 가진다.


여기까지가 HashMap 가장 기본적인 원리이다. 하지만 가장 큰 문제가 있다. 바로 다른 객체가 동일한 hashcode 를 가질 때 이다.

예를 들어, 아래와 같이 Developer class 를 작성했다. equals() 와 hashCode() 메서드를 확인해보자.
name, age, sex, language 가 모두 동일할 경우 바로 같은 hashCode 를 가지게 된다.
ndg 와 ndg2 는 서로 다른 객체이다. new 연산자를 통해서 생성했기 때문에, 내부 필드의 값은 같지만 결론적으로 다른 주소를 가진다. 따라서 다른 객체이다. 하지만 Developer 의 hashCode() 메서드는  내부의 필드가 같으면 같은 hashcode 를 생성한다. HashMap 에 담는 데이터가 증가할 수록 일어날 수 있는 확률이 높아지기 때문에 hash 전략은 매우 중요하다.




그 다음에 중요한 개념으로 LOAD_FACTOR 개념을 들 수 있다. 아래 JDK 11 에서 확인할 수 있듯이 Default 는 0.75 이다. 이는 무슨 숫자일까?
이는  HashMap 크기를 증가시킬 때 언제 증가시켜야 하는지를 알려주는 임계점이다.
0.75 는 3/4 로 현재 HashMap 에 3/4 가 채워졌을 경우, HashMap 의 크기를 증가시켜야 하는지 알려주는 수치이다.

아래의 resize() 함수를 확인해보자. Node array 의 사이즈를 증가시키는 메서드이다.
내부에서 resize() 메서드를 여러군데에서 호출하고 있어서 각각의 디테일은 전부 캐치하지 못했지만,
내가 파악한 요지는 이전 배열의 크기를 loadFactor 에 따라서 Capacity 를 통해 계산하고 있다.

이번 글은 여기서 마무리하도록 하겠다.
내부적으로 LinkedList 이외에 Tree 를 사용하고 있는데 이는 더 공부하고 정리를 해보도록 하겠다.
자료구조를 다시 공부하면서 여러모로 기본에 더 충실할 필요를 느꼈다.

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째