Map과 Hash table

Map

• key-value pair들을 저장하는 ADT

• 같은 key를 가지는 pair는 최대 한 개만 존재

• associative array, dictionary라고 불리기도

맵은 언제 쓸까?

전화번호 - 이름 매핑

영화 인기 순위 투표

영화이름 - count 맵

Map의 구현체

• hash table

• tree-based

Hash table(hash map)

• 배열과 해시 함수(hash function)을 사용하여 map을 구현한 자료 구조

• (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠름.

Hash function

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수

• (hash table에서) 임의의 데이터를 정수로 변환하는 함수

hash function에 key값을 집어넣고 나온 값이 202 % 8 , 8이 capacity

해시 충돌이 나면?

• key는 다른데 hash가 같을 때

• key도 hash도 다른데 hash % map_capa 결과가 같을 때

hash collision 해결 방법

• open addressing

• seperate chaining

HashMap의 기본 자료구조

transient Node<K,V>[] table;

• table은 배열이며, 각 인덱스가 버킷(bucket) 역할을 한다.

• 각 Node<K,V>는 key-value pair와 연결 구조를 갖는다.

Node 구조

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // key의 해시 값
    final K key; // 키
    V value; // 값
    Node<K,V> next; // 다음 노드 (충돌 시 체이닝)
}

동작 흐름 요약

put(key, value) 실행 시

1. hash()로 해시값 계산
2. index를 구해서 해당 버킷 위치 조회

3. 이미 노드가 있다면 -> node.hash == hash인지 check -> equals로 key 비교
4. 동일 key면 덮어쓰기, 없으면 next에 새 노드로 추가 //seperate chaining 방식
5. 충돌이 심하면 TreeNode로 변환

충돌이 자주 발생한다면, 최악의 경우의 수행 시간은 O(N)이 된다. (N은 키의 개수)

containsValue -> Value를 찾는 연산은 들어간 노드들 모두 비교해야 하므로 O(N)

Open addressing 방식 (linear probing)

비어있는 버킷을 활용한다. hash collision이 발생해 다음 버킷에서도 비교해봐야한다는 정보를 가지고 있어야 한다.(dummy값 -> 기존 정보가 삭제됨. 근데 해시충돌이 나 다음 버킷에 똑같은 해시값을 가진 정보가 있음)

HashMap (Java Platform SE 8 )docs.oracle.com

HashMap은 Map 인터페이스를 기반으로 한 해시 테이블 구현체이다. 이 구현체는 Map 인터페이스의 모든 선택적 연산을 지원하며, null 값을 저장할 수 있고 null 키도 허용한다. (HashMap 클래스는 HashTable 과 거의 동일하지만, 동기화되지 않았고 null 값을 허용한다는 점에서 다르다.)

이 클래스는 Map의 항목 순서를 보장하지 않는다. 특히 , 시간이 지나도 순서가 일관되게 유지된다는 보장도 없다.

HashTable보다 HashMap 쓰자. 동기화 필요할 땐 ConcurrentHashMap.

💡 성능 특성

• get() 과 put () 등의 기본 연산은 상수 시간 성능 O(1)을 제공한다. -> 단, 해시 함수가 요소들을 버킷(bucket)에 적절히 분산시킨다는 가정 하에서이다.

• 컬렉션 뷰(iterator 등) 순회 시 성능은 HashMap의 용량(capacity) + 크기(size)에 비례한다

• 따라서 순회 성능이 중요하다면 초기 용량을 너무 크게 하거나 load factor를 너무 작게 설정하면 안된다.

HashMap의 성능에 영향을 주는 두 가지 파라미터

1. initial Capacity (초기 용량) : 해시 테이블 생성 시의 버킷 수

2. Load Factor (부하율) : 테이블이 얼마나 차야 리사이징(재해싱) 할지를 결정

• 엔트리 수가 용량 x 부하율 을 초과하면, 버킷 수를 두 배로 늘리고 내부 자료구조를 다시 만든다(재해싱)

• 일반적으로 기본 부하율 0.75는 시간과 공간 비용 간의 좋은 타협점

• 3/4, 0.75의 데이터가 차게 되면 사이즈를 2배로 늘려준다. -> 리해싱 해줘야 함.

java에서 hash table 사용 예제

Map<String, String> phoneToName = new HashMap<>();
phoneToName.put("010-2222-2222", "홍진호");
phoneToName.put("010-7777-7777", "럭키짱");
System.out.println(phoneToName.get("010-7777-7777");
System.out.println(phoneToName.containsKey("010-2222-2222"));

🔐 동기화 관련

• HashMap은 동기화되지 않습니다. → 여러 스레드에서 동시에 수정이 일어날 경우 외부에서 동기화를 처리해야 합니다.

• 예시:

  Map m = Collections.synchronizedMap(new HashMap(...));

• 구조적 변경(항목 추가/삭제)이 발생하는 경우는 반드시 동기화 필요. → 단순히 값만 바꾸는 것은 구조적 변경이 아님.

Java에서 HashMap이나 ArrayList와 같은 컬렉션은 "fail-fast" 반복자를 제공합니다. 이 말은:

**"반복자(iterator)가 생성된 이후, 해당 컬렉션이 구조적으로 변경되면 즉시 예외를 던진다"**는 의미입니다.

---

🔧 구조적 변경(structural modification)이란?

구조적으로 변경된다는 것은 다음과 같은 경우를 말합니다:

• put(), remove() 등으로 항목을 추가하거나 제거

• 예: map.remove(key), map.put(newKey, value)

단순히 map.get(key)이나 map.replace(key, newValue)처럼 값만 바꾸는 것은 구조적 변경이 아닙니다.

---

🔥 왜 예외를 발생시킬까?

동시 수정 중 버그를 "즉시 감지" 하기 위해서입니다.

• Java의 반복자는 컬렉션의 **버전 정보(modCount)**를 기억해둡니다.

• 반복 도중 누군가 map.put() 등을 호출하면 modCount가 변경됩니다.

• 반복자는 next() 또는 hasNext() 호출 시 이 변경을 감지하면 ConcurrentModificationException을 던집니다.

---

🚨 예시 코드

java코드 복사Map<String, String> map = new HashMap<>();
map.put("a", "1");
map.put("b", "2");

for (String key : map.keySet()) {
    if (key.equals("a")) {
        map.remove(key);  // 🔥 ConcurrentModificationException 발생!
    }
}

위 코드는 map.keySet() 반복 도중 map.remove()가 호출되어 구조적으로 변경되므로 예외가 발생합니다.

---

✅ 안전하게 수정하려면?

1. 반복자(iterator)의 remove() 사용

java코드 복사Iterator<String> it = map.keySet().iterator();
while (it.hasNext()) {
    String key = it.next();
    if (key.equals("a")) {
        it.remove();  // ✅ 안전하게 제거
    }
}

2. 수정할 키를 따로 모아서, 반복 후 제거

java코드 복사List<String> toRemove = new ArrayList<>();
for (String key : map.keySet()) {
    if (key.startsWith("a")) {
        toRemove.add(key);
    }
}
for (String key : toRemove) {
    map.remove(key);
}

---

⚠️ 반복자(iterator)는 Fail-Fast

• 반복 도중 HashMap이 구조적으로 변경되면 ConcurrentModificationException 예외 발생.

• 반복자가 생성된 후 맵이 직접 변경되는 것을 빠르게 감지하기 위한 메커니즘.

• 단, 이것은 완벽히 보장되는 것은 아님. → "최대한 빠르게 실패하도록" 설계된 것이며, 반드시 감지할 수 있다는 보장은 없음. → 따라서 이 예외에 의존하여 프로그램을 작성하면 안 됩니다. 단순히 버그를 감지하는 용도로 사용해야 합니다.

💥 결과적으로 생기는 문제:

• 일부 요소가 반복에서 건너뛰어지거나

• 중복 처리되거나

• **NullPointerException**이나 **ArrayIndexOutOfBoundsException**처럼 예측 못한 에러 발생

• 디버깅이 매우 어려운 불안정한 프로그램이 됨

📌 요약

항목	설명
Fail-Fast	반복자 생성 후 컬렉션이 구조적으로 변경되면 ConcurrentModificationException 발생
감지 방법	내부 modCount와 반복자의 expectedModCount 비교
회피법	반복자 자체의 remove() 사용 or 수정 작업은 반복 이후에 수행