HashMap vs Hashtable 그리고 ConcurrentHashMap

Hashmap, Hashtable, 그리고 ConcurrentHashMap은 모두 Map 인터페이스를 상속받습니다.
Key - Value 자료구조에 해싱을 사용하여 검색 속도가 O(1) 수준으로 빠른 것이 장점입니다.

본 글에서는 각 자료구조의 차이점에 대해 자세히 알아보려고 합니다.

1. 동기화(Synchronization)

HashMap

Hashmap은 동기화를 지원하지 않습니다. 따라서 단일 스레드 환경에서 적합합니다.

Hashtable

동기화를 지원합니다. 다만 동기화 처리 비용으로 인해 Hashmap 보다는 속도가 느린 편입니다.
모든 메서드에 synchronized가 걸려있습니다.

ConcurrentHashMap

읽기에는 synchronized가 걸려있지 않아 여러 쓰레드가 동시에 읽을 수 있습니다.
쓰기 작업에는 synchronized가 걸려 있습니다.
쓰기 작업 또한 세그먼트 단위로 락이 잡히기 때문에 병목현상 발생 위험을 줄일 수 있다.

2. Iteration

HashMap

• Fail-Fast iteration.
• 순환 중 데이터가 변경되면ConcurrentModificationException이 던져지면서 작업이 중지된다.

Hashtable

• Enumeration 방식의 순회. 지금은 잘 쓰이지 않는다.

ConcurrentHashMap

• Fail-Safe iteration.
• Iterator 자체가 실제 Collection의 복제본이다. 이 때문에 원본에 변경 사항이 발생해도 Iterator는 그대로 유지되어 Fail-Safe해진다.

3. Hashing

HashMap & ConcurrentHashMap

• 초기에는 Seperate Chaining 방식을 사용

  • 링크드 리스트를 사용한다

• Chain이 일정 값 (Threshold) 이상으로 커지면

  • 레드 블랙 트리 자료구조를 사용하는 트리 방식을 사용하여 검색 시간을 O(logN)으로 유지한다.

• 해시 함수의 균등 분포 성능이 높아짐에 따라 JDK 1.8부터는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 함수로 변경되었다고 합니다.
  참고 자료 : adam2님의 자료구조해시-테이블 포스팅

Hashtable

• Open Addressing