[Java] HashMap VS TreeMap

HashMap

• Map 인터페이스의 여러 구현 중 하나는 해시 테이블(hash table)에 기반을 두는데 지금까지 발명된 자료구조 중 단연 으뜸이다.
• 핵심 메서드(put, get)의 실행시간이 상수 시간이다. 
• 가변 객체를 키로 사용하는 것은 위험하다.
• HashMap 클래스의 연산이 상수 시간이라 해도 해싱이 느릴 수 있다. 즉, 상수가 커질 수 있다.
• 해시 함수가 키를 고루 분배하면 잘 동작하지만 좋은 해시 함수를 설계하는 것은 쉬운 일이 아니다. 키의 중복이 많이 일어나면 성능이 나빠진다.
• 해시 테이블에 있는 키는 순서대로 저장되지 않는다. 순서는 테이블이 커지고 키가 재 해시될 때 변하기도 한다.

TreeMap

• TreeMap은 해시 함수를 사용하지 않는다. 따라서 해싱 비용과 해시 함수를 고르는 것을 피할 수 있다.
• TreeMap 내부에서 키는 이진 탐색 트리에 저장되는데, 선형 시간으로 키를 순서대로 순회할 수 있다.
• 핵심 메서드의 실행시간은 log n에 비례하며 상수 시간만큼 우수하지는 않지만, 여전히 꽤 쓸만하다.
• 트리가 불균형해질 때 이를 탐지하고 노드를 재배열해야 한다.(자가 균형 트리(AVL, 레드 블랙트리))

출처 - Think Data Structures - 앨런 B. 다우니 저
소스코드 - https://github.com/kkyu8925/java-study/tree/master/ThinkDataStructures