HashTable, HashMap, ConCurrentHashMap 차이

정민기·2021년 4월 25일

목록 보기

2/3

HashTable, HashMap, ConCurrentHashMap은 기본적으로 Map 인터페이스를 구현한 클래스이다. Map 인터페이스는 키(key)와 값(value)로 데이터를 관리하며 키를 이용하여 데이터를 추출할 수 있다.

Separate Chaning, Open Addressing

Hash의 기본적인 구조는 key를 hash function을 통해 특정 값으로 변환 후 그 값에 맞는 index를 가진 bucket안에 value를 넣어주는 구조이다. 하지만 넣어주려는 bucket에 이미 값이 있는 경우 충돌을 처리하는 방법에는 2가지 방법이 있다. Separate Chaning와 Open Addressing이다.
Separate Chaning
Separate Chaning 방식은 bucket이 list의 포인터를 저장하고 있고, value는 linked list의 헤드에 저장된다. 만약 충돌이 발생했을시 linked list의 헤드의 앞에 추가하는 식으로 구현된다. 하지만 worst case로 한 bucket에만 저장되는 경우 마지막 데이터는 O(N)의 속도를 가지게 되는데 이 문제는 Java 8에서 Red-Black 트리를 사용하여 worst case에도 O(logN)로 탐색이 가능하다
Open Addressing
Open Addressing 방식은 bucket에 value를 저장하는 방식이다. 만약 충돌이 발생하면 비어있는 bucket을 찾는 탐색을 하고 빈 bucket에 value를 넣어준다. 탐색 방법에는 Linear Probing, Qudratic Probing, Double Hashing이 있다.
- Linear Probing : 충돌 발생 지점부터 +1씩 bucket을 탐색한다. 주변의 bucket이 전부 차있는 Primary Clustering 문제가 있다. 캐싱에는 유리하지만 bucket이 가득찰 경우 효율은 급격하게 감소한다.
- Qudratic Probing : Primary Clustering을 개선하기 위한 방법으로 충돌 발생 지점부터 n2씩 증가시켜 탐색한다. 하지만 초기 hash값이 동일하다면 탐색 과정이 동일하다는 Secondary Clustering 문제가 있다.
- Double Hashing : 위의 탐색방법들은 규칙성이 생겨 Clustering 문제가 생긴다 따라서 규칙성을 없애기 위해 2차 Hash Function을 이용하여 다음 탐색을 정하게 된다.

1. HashTable

HashTable의 모든 Data 변경 메소드는 syncronized로 선언되어 있다. 따라서 메소드 호출 전 thread간 동기화 lock을 통해 multi thread 환경에서도 data의 무결성을 보장한다. 하지만 이 동기화 락이 매우 느린 동작이어서 단일 thread 환경에서는 HashMap을 사용하는 것이 훨씬 빠르다.

2. HashMap

HashMap은 HashTable과 동일한 내부 구조를 가지고 있지만 HashTable은 syncronized 키워드가 없기 때문에 동기화가 보장되지 못한다. 하지만 동기화 처리를 하지 않기 때문에 value를 찾는 속도는 상당히 빠르다. 또한 HashTable과는 다르게 key와 value가 null값을 허용한다.
HashMap은 충돌 문제를 Separate Chaning을 사용하여 처리한다. 또한 worst case 문제는 java8에서 bucket에 적은 data라면 linked list를 사용하지만 많은 data가 쌓이면 Red-Black tree로 변환한다. 따라서 worst case에도 O(logN)의 속도를 보장한다.