목표

• Red-Black 트리를 구현한 자바 Collection 자료구조를 알아본다.

treeSet

• Set 인터페이스 구현, 중복 불가, 순서 없음
• Red-Black 트리를 통해 구현
• Red-Black 트리를 통해 구현됐기 때문에 삽입, 삭제 시 균형을 맞추는 연산에 따라 속도가 상대적으로 느리지만 높이가 전부고 속도가 특징인 트리답게 검색과 정렬에 굉장히 빠르다.

treeMap

• abstractMap을 구현, 키와 값을 통해 Map.Entry 객체를 저장
• get, put, remove에 대해 $O(logN)$의 속도를 보장
• 동기화 되지 않는 연산
• 삽입 시 Natural Order에 따라 자동 정렬
  삽입 시 자동 정렬로 인해 HashMap보다 속도가 많이 떨어진다.
  정렬 된 데이터를 Map으로 유지시켜야 하거나, 이미 정렬된 데이터를 key기반 검색이 필요할 때 사용
  • HashMap이 검색 속도가 $O(1)$로 빠르기 때문에 보통 HashMap을 사용한다.

treeMap 값 기준 정렬

• Comparator를 구현하여 정렬

entrySet vs. keySet

entrySet()

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    entry.getKey(); 
	entry.getValue();
}

• Key, Value 쌍을 Map.Entry<K, V> 객체로 반환
• 각 Entry 객체에서 getKey()와 getValue()로 직접 접근 가능
• 불필요한 get() 호출 제거

keySet()

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

for (String key : map.keySet()) {
	map.get(key);
}

• Map의 모든 Key 반환 Set<K>
• map.get(key)를 통해 값을 가져옴
• keySet()을 사용할 경우 각 키에 대해 추가적인 get() 호출이 발생

결론

✅ 키와 값이 모두 필요한 경우 get() 호출을 방지할 수 있는 entrySet()을 사용

참고

JDK9 TreeMap
JDK9 TreeSet