HashMap vs TreeMap

🎉Map이란?

• key와 value이 하나의 쌍으로 연결되어 있어 키를 통해 값에 접근을 할 수 있도록 만들어진 자료 구조

🎉HashMap이란?

• 내부적으로 Entry<K,V>[] Entry 의 array로 되어 있으며, 해당 array에 index는 내부 해쉬 함수를 통해 계산된다.
• HashMap은 Map 인터페이스의 한 종류로 Key와 Value 한 쌍을 데이터로 가지고 있으며 Key를 통해 Value에 접근한다.
• HashMap은 그 안에 들어있는 데이터를 Set 구조 저장하기 때문에 Set의 원칙대로 중복된 데이터를 허락하지 않으면서 순서가 없다.
• hashing을 사용하기 때문에 많은양의 데이터를 검색하는데 뛰어난 성능을 가지고 있다.
• 시간복잡도 O(1)

*Set : 중복된 데이터 x, 순서 x

🎉TreeMap이란?

• key 값에 따라서 자동으로 Sort가 되는 방식
• 동기화(synchronized) 처리가 되어 있어 Thread-safe 하다.
• HashMap과는 다르게 Key 값으로 null을 허용하지 않는다.
• 내부적으로 RedBlack Tree로 저장되며, 키값에 대한 Comparator 구현으로 정렬 순서를 바꿀수 있음
• 시간복잡도 O(logN)

• RedBlack Tree : 자가 균형 이진 탐색 트리

🎉HashMap과 TreeMap의 차이

• HashMap은 key로 null 허용, TreeMap은 key로 null 허용하지 않음
• HashMap은 정렬되어 있지 않은 상태, TreeMap은 정렬된 상태
• HashMap 시간복잡도 O(1), TreeMap 시간복잡도 O(logN)

참고

Red Black Tree
HashMap vs TreeMap