Java HashMap 구조와 동작 방식 정리

1.1 HashMap이란?

HashMap은 Java 컬렉션 프레임워크 중 가장 많이 사용하는 자료구조 중 하나다.
Key-Value 형태로 데이터를 저장한다.

특징:

• Key는 유일해야 한다.
• Value는 중복 가능하다.
• 빠른 검색 성능을 가진다 (평균 O(1)).

---

1.2 HashMap 내부 구조

저장 방식 요약

1. Key의 hashCode()를 호출하여 해시값을 얻는다.
2. 배열의 인덱스를 결정한다 ((n-1) & hash).
3. 해당 인덱스에 Node(Entry)를 저장한다.

Node 구조:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

충돌 발생 시?

• 같은 인덱스에 여러 Entry가 들어올 수 있다.
• 이때 연결 리스트로 연결한다 (체이닝 방식).

---

1.3 Java 8 이후 최적화

• 만약 한 버킷(bucket)에 너무 많은 데이터가 몰리면 (기본 8개 이상)
  ➔ 연결 리스트를 트리(Balanced Tree, 빨간-검은 트리) 로 변환한다.
• 탐색 속도가 O(n) → O(log n)으로 개선된다.

---

1.4 시간 복잡도

연산	평균	최악
조회 (get)	O(1)	O(n)
삽입 (put)	O(1)	O(n)
삭제 (remove)	O(1)	O(n)

※ 최악의 경우는 모든 Key가 충돌할 때.

---

1.5 예제 코드

Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);

System.out.println(map.get("two"));  // 2

• "two"의 hashCode()를 통해 배열 인덱스를 찾고, 빠르게 접근한다.

---

1.6 총정리

• HashMap은 hashCode()와 equals()를 기반으로 Key를 관리한다.
• 해시 충돌이 발생하면 연결리스트 → 트리로 최적화한다.
• Key는 유일해야 하고, Value는 중복이 가능하다.
• 동기화를 지원하지 않기 때문에 멀티스레드 환경에서는 ConcurrentHashMap 사용을 추천한다.

---