TreeSet, TreeMap vs HashSet, HashMap

어떤 상황에서 어떤 자료구조를 써야할까!

TL;DR

특별한 사유가 없다면 검색 성능이 좋은 HashMap을 사용
순서를 보장하고 싶다면 LinkedHashMap을 사용
키값을 일정하게 iterate 하고자한다면 TreeMap을 사용

TreeMap과 HashMap의 차이점

TreeMap은 HashMap과 유사한 자료 구조이지만, TreeMap은 데이터가 정렬되어 있다는 점이 다르다
HashMap은 데이터가 정렬되어 있지 않기 때문에, TreeMap보다 데이터 검색 속도가 느릴 수 있다
but, HashMap은 TreeMap보다 메모리 사용량이 적다

순서 보장 측면

HashMap은 순서를 보장하지 않는다
- LinkedHashMap 은 입력된 순서를 보장한다!
TreeMap은 Key 값으로 사용된 클래스의 비교 연산을 활용하여 순서를 보장한다
- key 값에 따라 자동으로 sort 되는 방식

속도 측면

HashMap 의 시간 복잡도는 O(1) 이다
- 해시 값을 사용하기 때문
TreeMap 의 시간 복잡도는 O(log n) 이다
- 대신, 정렬된 순서를 얻을 수 있다

Key에 `null` 허용 여부

HashMap 은 key에 null 허용
TreeMap 은 key에 null 허용 X

TreeMap은 언제 쓰지?

순서가 있는 데이터를 저장하고 검색해야 하는 경우
- 동기화 처리가 되어있어 Thread-safe 하다
데이터를 정렬된 순서대로 검색해야 하는 경우
데이터에 대한 삽입, 삭제, 검색 연산이 자주 수행되는 경우

TreeMap이 효율적이지 않은 경우

데이터의 크기가 매우 큰 경우
데이터에 대한 삽입, 삭제, 검색 연산이 자주 수행되지 않는 경우