[Java] HashMap, TreeMap, LinkedHashMap

1. HashMap
- 내부적으로 Entry 배열을 만들어 관리 (key-value 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array)

- 객체의 hashCode() 메소드의 리턴 값을 기반으로 동작하되, 해시 충돌(Hash Collision)을 대비해 equals() 메소드까지 사용해서 key값이 정말 같은 경우에만 value를 리턴

- 키 값으로 사용할 클래스의 특성에 따라 필요한 경우 hashCode()메소드와 equals()메소드를 오버라이드

- 입력 순서나 key값의 정렬 순서는 지켜지지 않음
- 해시 함수를 사용하기 때문에 데이터 탐색에 O(1)의 시간복잡도를 갖는다
- Java HashMap의 동작 방식(Seperate Chaning): https://d2.naver.com/helloworld/831311 

  . 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용
  . 데이터가 많아지면, 충돌 시 성능 상 이점을 위해 데이터를 트리에 저장하여 관리
    ~Java 8에서는 Separate Chaning에서 하나의 해시 버킷에 8개 이상 키-값 쌍이 모이면 링크드 리스트를 트리로 변경
    ~버킷에 있는 데이터를 삭제하여 다시 개수가 6개에 이르면 다시 트리를 링크드 리스트로 변경 

 

 

2. TreeMap
- 내부적으로 RedBlack Tree로 저장하여 관리
- key로 사용할 클래스에 Comparator 인터페이스를 구현하면 key값을 기준으로 정렬된 상태를 유지할 수 있다

- 데이터 탐색에 O(logN)의 시간복잡도를 갖는다

 

3. LinkedHashMap
- Map.Entry 클래스를 구현한 Node 클래스로 내부에 before, after 멤버를 갖는 각 항목을 연결리스트 구조로 가지고 있음
- 데이터가 입력된 순서를 유지