Next-Squad/Interview-Question

[Java] 32. HashTable vs HashMap vs ConcurrentHashMap

CMSSKKK opened this issue · 1 comments

CMSSKKK commented

HashTable vs HashMap vs ConcurrentHashMap

키워드

Thread-Safe, Synchronized, Hash 충돌

CMSSKKK commented

공통점

  • 자바에서 사용할 수 있는 key, value로 데이터를 저장하는 자료구조입니다.

차이점

  • Thread-safe의 여부 및 동기화 방식에 대한 차이가 가장 큽니다.

  • HashTable

    • Thread-Safe 해서 멀티 스레드 환경에서 사용할 수 있습니다.
    • 하지만 data를 read, write하는 메서드들이 Synchronized 키워드가 붙어 있는 동기화 메서드로 성능적으로 좋지 않습니다.
    • 동시성을 고려하지 않아도 되는 상황 모두에서도 Lock을 걸기 때문입니다.

  • HashMap

    • 가장 자주 접하게 되는 Key, value 자료구조이지만 Thread-Safe 하지 않기 때문에 멀티스레드 환경에서의 사용은 자제해야합니다.

  • ConcurrentHashMap

    • 이름에서 부터 확인할 수 있듯이 Thread-safe한 자료구조입니다.
    • ConcurrentHashMap의 데이터를 삽입하는 put() 메서드의 경우, 기본적으로 데이터를 삽입하고자 할때 원자성을 보장하는 CAS(CompareAndSwap) 메서드를 사용합니다.
    • 하지만 이 경우는 해당 key (or hash값)이 일치하는 Node가 없을 때의 경우로, 삽입하고자하는 해쉬 버킷에 Node가 이미 존재한다면, 해당 버킷을 Lock을 겁니다. (synchronized 블록을 활용)
    • 그렇기 때문에 같은 해쉬 버킷에 접근하는 경우가 아니라면 여러 스레드가 데이터를 읽고, 쓰는 과정에서의 동기화가 보장됩니다.
    • (이전에도 HashTable보다 동기화 방식에서 효율적이었으나 Java 8에서 위 방식으로 구현이 변경이 되어 성능이 더 좋아졌음)

++ Hash 충돌을 해결하는 방법의 경우 대표적으로 Open Addressing, Separate Chaining 방식 있습니다.
++ Java는 Separate Chaining 방식으로 충돌을 해결합니다.
++ 데이터의 수가 작다면 Open Addressing, 데이터 수가 많다면 Separate Chaining 이 성능적으로 유리합니다.

Reference

  • 👍2