[JAVA] HashMap에 대해서(Thread Safe, 해시맵 동작 원리, chaining, 해시 충돌(Hash Collision), Fail-Fast ) - 컴도리돌이

---

 

사용자의 요청을 받고, 요청을 전달할 때 저는 대게 다음과 같이 HashMap을 사용합니다😓

 

@GetMapping("/")
public String main(@RequestParam HashMap<String,Object> reqMap) { ... }

 

 

물론 위와 같이 사용하는 건 굳이 좋은 방식이 아닙니다. 필요한 값만 정의한 DTO 클래스를 사용하는 것이 일반적으로는 훨씬 더더더 좋죠 😊 하지만 개발하다 보면 필요했던 값이 필요하지 않아 지고, 생각하지 않은 값이 필요하게 되는 상황이 대게 많기 때문에 저는 HashMap을 사용합니다. 😔 (시간이 부족해...)

 

그런데 이렇게 자주 사용한 HashMap이 사실 어떻게 작용하는지 알지 못합니다. 물론 알지 못해도 지금까지 잘 사용했지만, 그래도 알고 사용하는 것과 무지로 사용하는 거의 차이는 비교도 안되기 때문에 이번 기회에 HashMap에 대해 포스팅하려고 합니다. 

 

---

 

해시 맵(HashMap)

1. 해시맵은 해시 테이블을 기반으로 동작하며, 이는 키와 값의 쌍을 저장하고 키를 사용하여 값에 빠르게 접근할 수 있는 데이터 구조입니다.

HashMap<String, Integer> hashMap = new HashMap<>();

 

2. 해시 맵은 평균적으로 O(1)의 시간 복잡도를 가지며, 키를 사용하여 값에 빠르게 접근할 수 있습니다.

hashMap.put("key", 10);
int value = hashMap.get("key");

 

3. 해시 맵은 키와 값을 null 값을 허용합니다. 

HashMap<String, Object> hashMap = new HashMap<>();
hashMap.put(null, "value1");
hashMap.put("key2", null);

 

4. 해시 맵은 요소의 순서를 보장하지 않으며, 삽입 순서나 정렬된 순서를 유지 하지 않습니다. 내부 구현에 따라 순서가 변할 수 있습니다.

 

5. 해시맵은 스레드 간 동기화를 지원하지 않습니다. 따라서 동시에 여러 스레드가 접근할 때, 추가적인 동기화 작업이 필요합니다. 

해시맵은 멀티 쓰레드 환경에서 Thread Safe하지 않은 현상을 발생할 수 있습니다.  왜냐하면 해시맵은 스레드 간 동기화를 지원하지 않기 때문입니다. 그렇기에 여러 스레드가 동시에 HashMap에 접근하고 수정한다면, 예기치 않은 결과를 발생시킬 수 있습니다. 그렇기에 아래 코드처럼 멀티 스레드 환경에서는 ConcurrentHashMap과 같은 동기화된 맵을 사용해야 합니다.

Map<String, Integer> synchronizedMap = Collections.synchronizedMap(hashMap);

 

 

6. 해시맵의 반복자는 컬렉션을 수정할 때, ConcurrentModificationException을 던집니다.

Iterator<String> iterator = hashMap.keySet().iterator();
while (iterator.hasNext()) {
    String key = iterator.next();
    hashMap.remove(key); // ConcurrentModificationException 발생
}

 

---

 

해시 맵 예시(HashMap Example)

다음 예시를 살펴보면, HashMap에 다음과 같이 (Key, Value) 쌍을 put() 메서드를 사용해서 저장을 했습니다. 

public void test() {
    HashMap<String, Object> map = new HashMap<>();
    map.put("Amen", 19);
    map.put("Sunny",29);
    ...
}

 

put() 메서드를 호출할 때, Key, value 쌍이 HashMap에 저장되는 인덱스를 살펴보면, put() 메서드는 key "Amen"의 해시 코드를 계산합니다. "Amen"의 해시 코드가 2657860이라고 가정해 보면, 키를 메모리에 저장하려면 인덱스를 계산해야 합니다. 

 

index = hashcode(key) & (n-1)

 

여기서 n은 배열의 크기를 나타내며, Amen의 인덱스 값을 다음과 같이 계산할 수 있습니다. 

 

index = 2657860 & (16-1)

 

위에 수식을 계산하면 인덱스 값이 4가 나오는데, 해당 값으로 그림과 같이 (Key, Value)가 저장돼요.  

 

 

위에 그림에서 왜 배열 크기를 16으로 설정되어 있을까요? 🤔

HashMap은 내부 버킷 배열의 크기를 동적으로 조절할 수 있으며, 일반적으로 HashMap은 일정한 임계값을 기준으로 배열 크기를 자동으로 조절합니다. 이 임계 값은 기본적으로 0.75으로 설정되어 있으며, 해시 맵이 얼마나 많은 항목을 담을 수 있는지를 결정하는 비율입니다. 

따라서 항목을 추가할 때마다 해시 맵은 현재 저장된 항목의 수와 임계 값을 고려해서 배열의 크기를 동적으로 할당합니다. 기본 배열 크기 수는 16이며 항상 2의 제곱 수 설정됩니다. (ex. 16, 32, 64, 128 등) 
크기 조정 과정에서는 새로운 배열을 할당하고 기존의 항목을 새 배열로 이동시킵니다. 이러한 동적 크기 조정 과정은 사용자에게 숨겨져 있으며, HashMap은 내부적으로 이를 관리합니다.

 

---

 

해시충돌(Hash Collision)

그렇다면 계산된 인덱스 값이 두 개 이상의 키에 대해 동일한 경우 어떻게 처리를 해야 할까요?  🤔🤔

 

public void test() {
    HashMap<String, Object> map = new HashMap<>();
    map.put("Amen", 19);
    map.put("Sunny",29);
    ...
}

 

위에 예시를 다시 갖고 오면, 다음 "Sunny"의 해시코드가 63281940이라고 가정하면, 이 키를 메모리에 저장하려면 인덱스를 계산해야 합니다. 

 

index = 63281940 & (16-1) = 4

 

이전과 동일한 인덱스 값이 나왔네요. 이런 경우 equals() 메서드가 두 개의 키가 동일한지 여부를 확인합니다. 키가 동일한 경우 현재 값으로 이전 값을 대체가 됩니다. 그렇지 않은 경우, 이 노드 객체를 기존의 노드 객체와 연결된 링크드 리스트를 통해 연결합니다. 

 

 

그림은 4인덱스를 향하고 있어야해요 🥲

 

위에 그림처럼 연결리스트로 데이터들을 연결하는 방식을 체이닝(Chaining)이라고 합니다. 그 외에 방식으로 개방 주소법(Open Addressing)이 있는데, 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 합니다. 

 

개방 주소법은 대표적으로 3가지가 존재하는데, 선형탐색, 제곱 탐색, 이중 해시가 존재하며, 각각의 특징은 다음과 같습니다. 

 

• 선형 탐색(Linear Probing): 해시 충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
• 제곱 탐색(Quadratic Probing): 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입한다.
• 이중 해시(Double Hashing): 해시 충돌 시 다른 해시함수를 한번 더 적용한 결과를 이용한다. 

 

 

---

 

간단하게 값을 저장하는 방법을 어느 정도 익혔으니, 값을 가져오는 방법을 살펴볼까요? 😤

 

값을 가져올 때는 get() 메서드를 통해 키를 사용하여 값을 가져옵니다. 당연히 키를 알지 못할 경우에는 값을 가져올 수 없어요. 

다음과 같이 "Amen" 키를 가져와야 한다고 가정할 때, get() 메서드를 호출합니다. 

 

map.get("Aman");

 

해시 코드는 2657860으로 생성되며, 이제 위에서 계산한 인덱스 공식을 사용하여, 2657860의 인덱스 값을 계산합니다. 위에서 계산된 것처럼 인덱스 값은 4이며, get() 메서드는 인덱스 값 4를 검색합니다. 

 

그다음에는 요소의 키를 지정된 키와 비교를 하며, 두 키가 동일하면 값을 반환하고, 그렇지 않으면 다음 노드 요소가 있는지 확인합니다. 위에 예시에서는 첫 번째 요소로 찾아지고 값 19를 반환하게 됩니다. 

 

---

 

Barclays Java Spring-Boot Micro-service Interview Question with answer 2024

 

Working of HashMap in Java | How HashMap works - javatpoint