[항해 취업코스] 개발자 취준 기록 11 - Java Map 내부 구현 파악

Java에는 Map이라는 인터페이스 도구가 있다.

대표적으로 Map, HashMap, TreeMap, LinkedHashMap이 있다.

---

Map

기본적으로  Map은 key-value의 구조로 구성되어 데이터를 저장한다.

key를 가지고 저장된 value를 찾을 수 있다.

 

key를 이용한 데이터 검색에 최적화되어 있으나, 동일한 key에 다른 데이터 value가 저장되어 있을 경우 기존에 저장된 데이터는 덮어씌워져 사라진다.

 

중복된 key는 존재 할 수 없다.

---

HashMap

가장 일반적으로 사용되는 방식 중 하나이다.

HashMap은 자료구조로 배열(array)을 사용한다. 배열은 '인덱스'를 통해 바로 접근이 가능하다는 장점이 있다.

HashMap은 해싱(Hashing)을 통해 Map 데이터가 저장될 위치의 인덱스를 구한다. 그래서 이름이 HashMap이다.

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

key가 해싱을 통해서 인덱스를 구하고 그 인덱스를 통하여 내부 배열에 접근하기 때문에 저장되는 데이터가 많을수록, 내부 배열의 크기가 작을수록 인덱스 충돌이 발생할 가능성이 높다.

---

TreeMap

TreeMap은 Node들의 연결로 이루어져 있으며, LinkedList와 유사하다.

루트라는 최상위 Node가 존재하며 부모 Node와 자식 Node로 구성되어 있다.

Node에는 key와 value가 같이 저장되며, key 값을 기준으로 좌측 우측으로 구분하여 저장된다.

위 사진에서 5의 key 값을 가진 Node를 기준으로 봤을 때 5보다 작은 key(2)는 좌측 자식 Node, 큰 key(6)은 우측 자식 Node로 저장되어 연결한다.

---

LinkedHashMap

LinkedHashMap은 HashMap을 상속하여 만들어진 클래스다.

따라서 HashMap의 특징을 그대로 가지고 있는데 HashMap과 다른점은 Node 객체를 Entry 객체로 감싸서 저장된 key의 순서를 보존하고 있다는 점이다.

---

참고

https://jindevelopetravel0919.tistory.com/44

---

항해 개발자 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

IT 커리어 성장 코스 항해99, 첫 취업부터 현직자 코스까지