Map

Java Map - HashMap, TreeMap, LinkedHashMap 비교, 차이점

데이터를 모아서 관리할 수 있는 클래스를 컬렉션이라고 한다. 컬렉션은 그 타입에 따라 내부에 데이터를 저장하는 구조와 처리하는 방법이 다르다. 내부에서 처리하는 방법에 따라 데이터의 탐색이 빠른 경우가 있고, 추가/제거가 빠른 경우가 있다. 사용하는 컬렉션의 특성을 잘 알고 사용해야 불필요한 성능 저하를 피할 수 있다. 자바에서 제공하는 컬렉션의 대표적인 예로 List, Map, Set 등이 있다.

https://soft.plusblog.co.kr/70

[algorithm] LinkedHashMap - 순서를 유지하는 HashMap

릿코드의 LRU Cache 문제를 풀다가 이 자료구조를 알게 되었다. 처음에는 HashMap 으로 직접 LRU Cache에 해당하는 알고리즘을 작성하였으나, 입력값이 커지니 Time limit exceed 가 발생했다. 이 문제의 솔루션은 LinkedHashMap 을 확장하는 것으로 별다른 로직 추가 없이 LRU Cache의 요구사항을 만족시킬 수 있었다. 이런 건 그냥 지나갈 수 없다.

https://jhleed.tistory.com/178

☝️ HashMap

• 내부적으로 Entry 배열을 만들어 관리

• 객체의 hashCode() 메서드의 리턴값을 기반으로 동작

• 충돌 대비 equals() 메서드까지 사용하여 Key 값이 같은 경우에만 Value 리턴 (사용할 클래스 특성에 따라 필요한 경우 hasCode(), equals() 메서드 오버라이딩 필요)

• 데이터 전체를 사용하는 경우 순서가 뒤섞임

Map<String, String> map = new HashMap<>();

map.put("일식", "초밥");
map.put("중식", "짬뽕");
map.put("한식", "김치찌개");

map.forEach((key, value) -> {
	log.info("key: {}, value: {}", key, value);
});

결과를 보면 입력한 순서대로 출력되지 않는 것을 확인할 수 있습니다.

key: 중식, value: 짬뽕
key: 일식, value: 초밥
key: 한식, value: 김치찌개

해시 함수를 사용 → O(1) 시간 복잡도

✌️ TreeMap

• 내부적으로 RedBlack Tree로 저장 관리 → Key 값 기준으로 정렬된 상태 유지

• Key 값으로 사용될 클래스에 Comparator 인터페이스를 구현하면 정렬된 순서 조정 가능

RB-Tree 관리 → O(log N) 시간 복잡도

• 추가 및 삭제 → O(log N) 시간 복잡도

• HashMap과 비교했을 때 조금 더 느림

🤟 LinkedHashMap

• 데이터의 입력된 순서를 기억

• 각 항목은 Map.Entry 클래스를 구현한 Node 클래스 (before, after 멤버를 가지는 연결 리스트 구조)

• HashMap의 모든 기능은 그대로 사용 가능

• 순서 유지를 위해 이중 연결 리스트(Doubly Linked List)를 사용 → 메모리 사용량이 HashMap보다 높다

HashMap 클래스 확장한 클래스 → O(1) 시간 복잡도

• LinkedList의 각 항목을 순회

• 추가 및 삭제도 O(1)

• 모든 멤버 순회도 O(1)

✨ 요약

• HashMap은 순서 보장 X

• TreeMap은 Key 값으로 사용된 클래스의 비교 연산을 활용해서 순서 보장 (Comparator 인터페이스를 구현해서 순서 조정 가능)

• LinkedHashMap은 입력된 순서 보장 (불필요하게 Linked-list 유지 비용이 생길 수 있음)