TreeMap, LinkedHashMap

TreeMap

- Key-value 쌍을 내부적으로 RedBlack Tree로 저장된다. Key값 기준으로 정렬된다.

- O(log N)

- 레드 블랙 트리

• 부모노드보다 작은 값을 가지는 노드는 왼쪽, 큰값을 가지는 노드는 오른쪽으로 배치하여 균형을 맞춘 이진탐색 트리
• 루트는 블랙, 레드의 자식노드 양쪽은 언제나 블랙이다.
• 어떤 노드부터 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드 제외 모두 같은 블랙 노드가 있다.

LinkedHashMap

- 입력된 순서를 기억한다. Node 클래스 내부에 before, after 멤버를 갖는 이중 연결리스트 구조로 되어있다.

- O(1)  but Linked-list를 유지하는 비용이 발생할 수 있다.