Maru's Study Memo

1. HashMap
   - Thread-Safe하지 못한 클래스
   - Multi-Thread 환경에서 안전하게 사용하기 위해 Collections.synchronizedMap(hashMap) 등으로 동기화 처리 필요
   - key, value에 null 허용

2. HashTable
   - 데이터 관련 메소드에 synchronized 처리가 되어있어 멀티 스레드 환경에서 안전하게 사용 가능
   - 동기화 Lock 때문에 속도가 느리다
   - key, value에 null을 허용하지 않음

3. ConcurrentHashMap
   - HashTable처럼 항상 동기화 Lock을 걸지는 않고,
       . 빈 해시 버킷에 데이터를 삽입하는 경우, CAS(Compared And Swap)를 이용하여 원자성을 보장한다
       . 이미 데이터가 존재하는 해시 버킷 서로 다른 스레드가 접근 할 때만 동기화 Lock이 걸리게 된다
       . HashTable보다 성능면에서 우수
   - key, value에 null을 허용하지 않음

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 멤버를 갖는 각 항목을 연결리스트 구조로 가지고 있음
- 데이터가 입력된 순서를 유지