이번 글은 간단하게 HashMap에 대한 동작을 이해하고


HashTable vs HashMap vs ConcurrentHashMap에 대한 비교(성능 관점)를 할거야.


왜 ConcurrentHashMap이 성능적으로 더 좋은가?


도대체 어떻게 ConcurrentHashMap vs HashTable 두 컬렉션 모두 Thread-Safe한데 왜 ConcurrentHashMap이 더 빠른가?


이에 대해 궁금한 백붕이들은 글을 계속 읽기를 추천해~

====================================

1. HashFunction이란 무엇인가?

2. Hash를 이용하는 컬렉션을 이용하면 hashCode(), equals()를 재정의 해라!

3. HashTable vs HashMap vs ConcurrentHashMap 동작 비교

4. HashTable vs ConcurrentHashMap 성능 비교(code level)

====================================


3. HashTable vs HashMap vs ConcurrentHashMap

그렇다면 HashTable, HashMap 같은 Hash를 사용한 Map들은 과연 어떻게 동작할까?


우선 Map이란? key, value를 한 쌍을 저장하는 방식의 자료구조를 뜻해.(KEY 중복 X, 순서 X)


HashTable vs HashMap vs ConcurrentHashMap 의 차이는 너무 많아서 자세한 사항은 구글을 참고해!


이 글은 코드 레벨에서 간단하게 살펴볼게


1. Init Capacity, loadFactor, Threshold 관점



위 사진을 보면 HashTable vs HashMap vs ConcurrentHashMap의 첫 번째 차이가 명확하게 보여


Init Capacity, LoadFactor에서 차이가 있는게 보이지? 그렇다면 Init Capacity, LoadFactor는 무엇인가? 라는 질문을 해볼 수 있어


Capacity는 용량이야 Table, Map에서 뜻하는 용량의 의미는 버킷 수를 의미해



이 그림에서 0 ~ 15 Index까지의 버킷이 있는걸 확인할 수 있어 즉 이 그림에서 capacity는 16이야(0 ~ 15 = 16개)


Hashtable은 default 버킷이 11개 HashMap, ConcurrentHashMap은 16개임을 code level에서 확인 가능해.


다음은 LoadFactor야 기본 버킷 수는 16개로 가정했을 때 버킷이 가득 차면 어떻게 될까? 이 문제에 대한 답은 너무나 쉬워.


더 이상 저장을 못하는 문제가 발생하겠지. 그렇다면 어느 순간에는 버킷 수를 늘려 줘야해 그에 대한 변수가 LoadFactor야.


즉 Hash 삼총사(HashTable, HashMap, ConcurrentHashMap)들은 75% 이상의 용량을 사용하면(정확히는 임계값 변수에 영향을 미침) Capacity를 조절해


Threshold는 InitCapacity * LoadFactor야 위 경우 HashMap일 경우 Threshold는 12를 의미해


즉. 12번째 Key-Value 항목이 추가되면 일정량 만큼 Capacity를(현재 Capacity 2배) 늘려


2. Thread-Safe 관점

Thread 관점에서도 Hash 삼총사들은 차이를 보여, 예를 들어 HashTable, ConcurrentHashMap은 Thread-safe 하지만


HashMap 같은 경우는 Thread-unsafe하게 작동해 다르게 해석하면


싱글쓰레드 어플리케이션의 경우 Lock을 거는 HashTable을 사용하는 것 보다 HashMap을 사용하는게 성능적으로 유리해


그렇다면 HashTable, ConcurrentHashMap이 Thread-Safe를 구현하는 방식은 동일할까? 정답은 No야 이는 챕터4에서 확인할게


3. 해시 충돌 관점

갑자기 해시 충돌이 나와서 깜짝 놀랐을거야 해시 충돌은 어려운게 아니야 결국 해시 함수를 사용해도 그 해시 값은 충돌이 날 수 있어,


예를 들어 "김대기" HashCode(1434)랑 "웃스음" HashCode(1434)는 같을 수 있어(가정임) 이런 상황이 해시 충돌이 발생한 상황이야.


만약 "김대기", "웃스음"의 HashCode가 1434가 나왔다고 가정하면 Hash는 이 문제를 어떻게 해결하는가?에 대한 답이야


충돌을 해결하는 방법은 여러 방법이 있지만 자바에서 사용하는 방법은 Separate Chaining 방식으로 문제를 해결했어.(자세한 설명은 위키백과)


간단하게 설명하면 버킷을 연결 리스트(Linked List)로 연결해서 충돌을 해결한 방식이야




HashTable은 해시 충돌을 연결 리스트로 문제를 해결했어


HashMap, ConcurrentHashMap은 7개의 노드 까지는 연결 리스트를 사용하면서, 8개 이상이면 레드 블랙 트리 자료구조를 사용하도록 문제를 해결했어


또한, 해당 버킷 내의 레드 블랙 트리 자료구조에서 노드를 Remove하여 6개에 이르면 다시 연결 리스트 방식으로 바뀌도록 구현했어


4. Put 관점

이번에는 HashTable put 메서드 vs HashMap put 메서드를 비교할게


위 사진은 HashTable의 Put 메서드 구현이야. 동작 과정을 자세하게 설명해줄게


1. value가 Null인지 체크 (만약 Null이면 NullPointerException 발생)

2. key에 해당하는 HashCode와 Index(hash % tab.length)를 구한다

3. Entry가 Null이 아니면 4를 반복(entry = entry.next) 로직 때문에 연결 리스트를 순회함.

4. 버킷의 엔트리의 hash랑 비교 True일 시 && 조건으로 key.equals 호출( 만약 둘 다 True일 시 value를 바꾸고, old객체 반환)

5. addEntry 호출 // 엔트리 추가(설명 생략)


HashTable은 정말 쉽게 동작해 어려운거 없지?? 그렇다면 HashMap을 확인해 볼게

ㅈ나게 복잡하네 ㅋㅋ


코드 레벨에서 간단한 차이는 Hashmap은 Value에 대한 Null 체크도 없고, 레드 블랙 트리 자료구조의 방식 사용하고,


HashTable Entry는 Enumeration을 구현했지만, HashMap은 그런거 없어 ㅋㅋ


물론 위에 설명했던 Thread-Safe의 차이도 있고 더 많은 차이가 있지만 대충 여기까지만 알아볼게


4. HashTable vs ConcurrentHashMap 성능 비교

그렇다면 HashTable vs ConcurrentHashMap은 구현이 어떻게 다르길래 속도의 차이가 날까


code-level에서만 확인할게

1. HashTable은 get, put, remove 메서드에서 synchronized를 사용해


자바에서 기본적으로 제공하는 동기화 메커니즘이야 즉 HashTable은 전체 Lock을 걸어 데이터를 put, get, remove등의 메서드 연산을 수행해

그렇다면 ConcurrentHashMap은 다를까?


ConcurrentHashMap은 버킷 단위로 Lock을 걸어서(최대 16개) 병렬적으로 처리해 이것이 ConcurrentHashMap vs HashTable의 차이야



더 자세한 내용이 궁금하면 코드를 확인해봐!


오늘은 간단하게 HashMap vs HashTable vs ConcurrentHashMap에 대해 알아봤어.


진짜 개발자라면 Hash에 대한 이해가 중요해 이 글로 Hash가 궁금해졌기를 기대할게