[Java] HashMap, LinkedHashMap, TreeMap

데이터를 전송하거나 저장할 때 Map을 많이 사용합니다!

Map에는 HasMap, LinkedHashMap, TreeMap, HashTable 등 다양한 종류가 있습니다. 

이 중에서 HashMap, LinkedHashMap, TreeMap의 개념과 차이점을 알아보겠습니다.

 

 

우암 뒤로가기

Map이란,
키-값(Key-Value)쌍을 저장하는 자료구조로 키를 기준으로 데이터를 빠르게 조회할 수 있다. 

 

 

HashMap

해시 테이블을 기반으로 키-값(Key-Value)을 저장하며, 순서를 보장하지 않는 자료구조

 

• 해시 함수(hashCode() 기반)로 키를 저장하며, 순서를 보장하지 않음 
  • 즉, hashcode() 값을 바탕으로 해시 버킷을 결정하기 때문에 입력 순서와 상관없이 데이터가 저장됨
• 같은 순서로 데이터를 넣어도 해시 충돌이 다르게 발생하면 다른 순서로 배치될 수 있음
• 해시 충돌이 발생하면 연결리스트 or 트리로 관리되므로 순회 순서가 바뀔 가능성이 있음
  • Chaining : 충돌이 많을 경우, 해시 버킷내에서 정렬 방식이 달라질 수 있음
• 특정 크기를 초과하면 리사이징(Rehasing)과정에서 요소들이 새로운 위치로 재배치됨
• KeyInterator를 활용하여 객체를 순회

 

HashMap 구조

 

- HashMap은 내부적으로 Entry<K, V>[]의 Entry Array로 구성됨

- Array의 인덱스를 해시함수를 통해 계산

- 해시 값에 의해 어떤 버킷(Bucket)에 담길지 결정됨

- 만약 Hash값이 같다면 같은 버킷에 List로 연결됨 (LinkedList처럼 Entry안에 Next Entry를 저장하는 변수가 있음)

 

우암 벌써 하나 공부했다

 

---

 

LinkedHashMap

HashMap을 확장한 클래스이며 이중 연결 리스트(Doubly Linked List)를 추가로 사용하여 삽입 순서를 유지하는 자료구조

 

• HashTable을 사용하면서도 이중 연결 리스트(각 엔트리가 이전 요소와 다음 요소를 가리키는 링크)를 추가적으로 유지
• before, after 엔트리를 저장 ⇒ LinkedHashMap의 엔트리는 이중 연결 리스트로 구현되어 있음
  • LinkedHashMap.Entry<K, V>는 before와 after 포인터를 사용하여 삽입 순서를 보장
• LinkedHashIterator를 사용 이중 연결 리스트를 따라 객체를 순회
  • LinkedHashMap.keySet()은 입력된 순서대로 키가 반환됨 

☑️ HashMap vs LinkedHashMap

자료구조	삽입/삭제 속도	조회 속도	순서 유지
HashMap	O(1)	O(1)	유지되지 않음
LinkedHashMap	O(1)	O(1)	유지됨 (입력 순서 or 접근 순서)

 

 

남았다.하나더

 

---

 

TreeMap

HashMap과 다르게 Entry가 트리(Tree)구조로 저장된 자료구조

 

• TreeMap은 SoretedMap 인터페이스를 구현하고 있어 Key값을 기준으로 정렬되어 있음
  • 이는 Comparator를 구현하여  정렬 순서를 변경할 수 있음
• 트리구조의 특성상 특정 Entry에 접근하려면 O(logN)의 성능을 보임
  • Red-Black Tree(균형 이진 탐색 트리)를 사용하므로 탐색, 추가, 삭제가 모두 O(logN)
• Key는 Null을 허용하지 않음

▶️ 메서드

메서드	설명
put(K key, V value)	Key-Value 쌍을 삽입
get(Object key)	특정 Key의 Value를 반환
remove(Object key)	특정 Key를 삭제
containsKey(Object key)	해당 Key가 존재하는지 확인
containsValue(Object value)	해당 Value가 존재하는지 확인
firstKey()	가장 작은 Key 반환
lastKey()	가장 큰 Key 반환
higherKey(K key)	주어진 Key보다 큰 Key 중 가장 작은 Key 반환
lowerKey(K key)	주어진 Key보다 작은 Key 중 가장 큰 Key 반환
subMap(K fromKey, K toKey)	fromKey 이상, toKey 미만의 Key-Value 서브맵 반환
headMap(K toKey)	toKey 미만의 Key-Value 서브맵 반환
tailMap(K fromKey)	fromKey 이상 모든 Key-Value 서브맵 반환
descendingMap()	내림차순 정렬된 TreeMap 반환

 

 

▶️ Comparator 적용

import java.util.*;

public class CustomComparatorTreeMap {
    public static void main(String[] args) {
        // Key를 내림차순 정렬하는 Comparator
        TreeMap<Integer, String> treeMap = new TreeMap<>(Comparator.reverseOrder());

        treeMap.put(10, "Ten");
        treeMap.put(20, "Twenty");
        treeMap.put(5, "Five");

        System.out.println(treeMap); // {20=Twenty, 10=Ten, 5=Five}
    }
}

 

 

특징	TreeMap	HashMap	LinkedHashMap
내부 구조	Red-Black Tree (BST)	해시 테이블	해시 테이블 + 이중 연결 리스트
Key 정렬	자동 정렬	정렬 없음	삽입 순서 유지
탐색 속도	O(log N)	O(1) 평균, O(N) 최악	O(1)
Key null 허용 여부	❌ (허용 안 함)	✅ (허용)	✅ (허용)
동기화	❌ (비동기)	❌ (비동기)	❌ (비동기)

 

 

잊지마 나의 뇌야