지난 글에서는 ArrayList 를 까보면서 native 메서드에 대해 잠시 다루어보았다. 이번 글에서는 직접 HashMap 을 구현해보도록 하겠다. JDK 를 까보면서 그리고 여라 다른 블로깅을 참고하면서 내 방식으로 구현해 보았다. https://medium.com/@mr.anmolsehgal/java-hashmap-internal-implementation-21597e1efec3 https://www.devglan.com/java8/hashmap-custom-implementation-java https://d2.naver.com/helloworld/831311 우선, 핵심을 먼저 정리하고 작성해보겠다. 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차원 형태의 테이블을 이루게 된다. 아래는 JDK 11 버전의 HashMap 을 직접 까보았다. 아래와 같이 Node 는 Map.Entry<K, V> interface 를 구현하고 있다. 그리고 필드로는 hash, key, value, 그리고 LinkedList 이기에 next 를 가진다. 여기까지가 HashMap 가장 기본적인 원리이다. 하지만 가장 큰 문제가 있다. 바로 다른 객체가 동일한 hashcode 를 가질 때 이다. 예를 들어, 아래와 같이 Developer class 를 작성했다. equals() 와 h...
.png)
.png)
댓글
댓글 쓰기