[Java] HashMap, HashTable, ConcurrentHashMap 자료구조에 대해서 알아보자

오늘은 Map Interface의 구현체의 일종인 HashMap, HashTable, ConcurrentHashMap 자료구조에 대해 알아보려고 합니다. 

싱글 스레드 환경에서만 사용하는 HashMap에 대해 먼저 알아보겠습니다.

 

 

1. HashMap 

• key, value에 null값 허용
• 동기화를 보장하지 않기에 싱글 스레드 환경에서만 사용
• HashTable, ConcurrentHashMap보다 데이터 검색 속도를 빠르지만, 신뢰성과 안정성이 저하됩니다.

이제 해시맵에 데이터를 쓰는 과정에 대해 알아보겠습니다.

 

1. 먼저, 배열 tab이 비어있거나 길이가 0이면 resize() 메서드를 통해 배열의 크기를 조정
2. 배열의 특정 index에 node가 없으면, 새로운 node 생성하여를 해당 index에 할당
3. 해당 index에 node가 존재하는 경우, key가 동일한 node를 찾아 값을 업데이트하고 treenode인 경우 적절한 위치에 새 node를 추가
4. 노드 추가 후에는 afterNodeInsertion 메서드를 호출하여 마무리 작업을 수행합니다., 만약, 키-값 쌍이 존재하는 경우에 onlyIfAbsent가 false거나 기존 값이 null일 경우에만 새로운 값으로 업데이트 

 

2. HashTable

• key, value에 null 허용 X
• 동기화 보장
• thread-safe하기에, 멀티 쓰레드 환경에서 사용할 수 있으며, 데이터를 다루는 메소드(get(), put(), remove()) 레벨 synchronized 키워드가 붙어있습니다.
• synchronized: 메서드를 호출하기 전에 쓰레드간 동기화 락을 걸기에 multi-thread 환경에서 데이터의 무결성을 보장하지만 매우 느립니다. (Thread 간 lock을 걸기 때문에)

 

1. value값이 null이면 NullpointerException을 발생하는 것을 확인하실 수  있습니다.
2. key, index를 결정한 값을 기반으로 연결 리스트들을 순회
3. key가 일치하는 node를 찾으면, node의 값을 새로 값으로 업데이트하고 기존 값을 반환
4. 주어진 key를 찾지 못하면, 새 Entry 추가

 

3. ConcurrentHashMap

• Hashtable과 마찬가지로, key, value에 null을 허용하지 않고, 동기화를 보장
• ConcurrentHashMap은 thread-safe 하기 때문에, 멀티 쓰레드 환경에서 사용 가능
• HashMap의 동기화 문제를 개선하기 위해 등장했고, 특정 Entry에 대해서만 락을 걸기에 HashTable보다 데이터를 다루는 속도가 빠릅니다.
• ConcurrentHashMap에는 HashTable과는 다르게 synchronzied 키워드가 메서드 전체에 붙어있지 않습니다. get() 메서드에는 아예 synchronized가 존재하지 않고, put() 메서드에는 중간에 synchronized 키워드가 존재합니다.
• 읽기 작업에서는 여러 쓰레드가 동시에 작업이 가능하지만, 쓰기 작업에서는 특정 세그먼트 or 버킷에 대한 Lock 사용

 

1. 가변 배열을 순회
2. 가변 배열이 null이거나 길이가 할당되어 있지 않으면, initTable() 메서드를 호출하여 테이블 초기화
3. 그렇지 않으면, 새로운 노드를 삽입하기 위해, 해당 버킷 값을 가져와 비어 있는지 확인
4. 다시 node를 담고 있는 volatile 변수에 접근하여 Node와 기댓값을 비교하여 같으면, 새로운 node에 생성해서 넣고, 다르면 (1)번 과정으로 돌아갑니다.
5. 데이터를 쓰는 경우에만 synchronized 키워드가 붙어있는 것을 확인할 수 있으며 동일한 key이면, 새로운 node로 교체해 줍니다.
6. 해시 충돌이 일어난 경우에는 Separate Chaining에 추가해 줍니다.

 

HashMap, HashTable, ConcurrentHashMap 자료구조를 비교해 보았고, 각 자료구조의 put() 메서드 과정을 알아보았습니다. 

 

<참고 자료>

https://tecoble.techcourse.co.kr/post/2021-11-26-hashmap-hashtable-concurrenthashmap/

HashMap vs HashTable vs ConcurrentHashMap