Implementations of Map

Overview

---

Map 구현체들에대한 특징 설명

HashMap

---

• 자료구조: HashTable
• 알고리즘: Hasing
• 설명: hashCode() 메소드를 통해 해시 코드를 취득, 이를 사용해 배열의 인덱스를 계산하고 계산된 인덱스에 키값의 쌍을 정의 해시코드를 취득하는과정에서 충돌이 발생할 수 있고(같은 인덱스에 여러 엔트리 저장), 이때, 연결리스트 or 트리를 사용해 충돌을 처리
• 특징:
  1. 시간복잡도 O(1)
  2. 저장순서 미보장
  3. Null키 Null값 허용
• 사용 시나리오: 순서가 중요하지 않고, 키를 통해 값을 빠르게 찾고싶을 때 사용

TreeMap

---

• 자료구조: Red-Black Tree
• 알고리즘: 트리 기반 정렬 및 탐색
• 설명: 키를 기준으로 정렬된 상태로 데이터를 저장하고, Comparator에 의해 정렬 각 연산은 트리의 높이의 비례하는 시간복잡도(O(log n))
• 특징:
  1. 저장 순서 보장(항상 정렬된 상태로 유지)
  2. Null키 허용X
• 사용 시나리오: 키를 기준으로 데이터를 정렬해야할 때 or 범위의 키값 쌍을 검색해야할 때

LinkedHashMap

---

• 내부 자료구조: HashTable + Double Linked List
• 알고리즘: Hashing 해싱 및 연결 리스트 순서 유지
• 설명: HashMap의 구조를 기반으로 하며, 추가적으로 모든 엔트리를 이중 연결 리스트로 연결해 삽입순서 혹은 접근 순서를 유지 삽입 순서는 엔트리가 맵에 삽입된 순서이고, 접근 순서는 엔트리가 삽입되거나 마지막으로 접근된 순서
• 특징: HashMap과 동일한 특성을 가지면서도, 접근 순서를 보장함 다만, 순서를 유지하기위해 추가적인 메모리 오버헤드가 있음
• 사용 시나리오: 순서가 중요하며, 동시에 빠른 삽입/삭제/검색 성능이 필요할 때 사용

Sumarry

---

Map 구현체	내부 자료구조	순서 보장	주요 특징	성능 (평균)	null 키/값
HashMap	해시 테이블	X	빠른 접근	O(1)	키 O, 값 O
TreeMap	레드-블랙 트리	O (키 기준 정렬)	정렬된 데이터, 범위 검색	O(log n)	키 X, 값 O
LinkedHashMap	해시 테이블 + 이중 연결 리스트	O (삽입/접근 순서)	빠른 접근 + 순서 유지	O(1)	키 O, 값 O

HashMap, TreeMap, LinkedHashMap은 모두 Map 인터페이스를 구현하지만, 내부적인 자료구조와 동작 방식에서 큰 차이를 보입니다. 이러한 차이점은 각 구현체의 성능 특성과 사용 시나리오를 결정하는 중요한 요소입니다.