데이터를 가장 빠르게 찾을 수 있는 방법은 무엇일까? 그것은 ‘해시맵(HashMap)‘이다. 해시맵은 키값을 해시 함수를 통해 인덱스로 변환하여 배열의 특정 위치에 바로 접근하므로, 평균적인 경우 데이터 탐색을 상수 시간 O(1) 안에 수행한다.

핵심 구조와 O(1)의 원리 (JDK 8 기준)

해시맵은 본질적으로 키(Key)를 해시 함수의 결과값인 ‘해시 코드’로 변환하고, 이를 배열의 인덱스로 매핑한다.

  1. 배열(Bucket) 기반 접근: 해시 함수를 통해 도출된 인덱스로 배열에 즉시 접근하므로 이론적으로 O(1)의 속도를 가진다.
  2. 충돌 해결 (Chaining): 서로 다른 키가 같은 인덱스에 할당되는 ‘해시 충돌’이 발생하면 연결 리스트(Linked List)로 데이터를 엮는다.
  3. 성능 최적화 (Treeify): JDK 8부터는 충돌이 잦아져 하나의 버킷에 쌓인 노드가 임계점을 넘으면 연결 리스트를 레드-블랙 트리(Red-Black Tree)로 변환한다. 이를 통해 탐색 성능을 O(N)에서 O(log N)으로 개선한다.

실무에서 유용한 HashMap 고급 메서드

1. getOrDefault(K key, V defaultValue)

키가 존재하면 그 값을 반환하고, 존재하지 않으면 설정한 기본값을 반환한다.

map.put(key, map.getOrDefault(key, 0) + 1);

2. putIfAbsent(K key, V value)

키가 존재하지 않을 때만 값을 저장한다.

map.putIfAbsent(key, new ArrayList<>());

3. computeIfAbsent(K key, Function mappingFunction)

키가 존재하지 않을 경우에만 지정된 함수를 통해 값을 계산하여 저장한다.

map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

4. compute(K key, BiFunction remappingFunction)

키와 상관없이 지정된 함수를 사용하여 새로운 값을 계산하고 갱신한다.

map.compute(key, (k, v) -> v == null ? 1 : v + 1);

5. computeIfPresent(K key, BiFunction remappingFunction)

키가 존재할 때만 지정된 함수로 값을 재계산한다.

map.computeIfPresent(key, (k, v) -> v + 10);

필수 탐색 및 확인 방법

1. containKey(Object key)

특정 키가 맵에 존재하는지 확인한다.

if (map.containsKey("keyName")) {
    
}

2. 향상된 for문을 통한 전체 순회

map.entrySet()을 사용하면 키와 값을 동시에 효율적으로 순회할 수 있다.

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

JDK 1.7 vs 1.8 구조 비교

JDK 1.7과 1.8의 가장 큰 차이는 해시 충돌 처리 방식이다.

JDK 1.7 내부구조

충돌 시 LinkedList만 사용하므로 데이터가 한 버킷에 몰리면 O(N)으로 저하된다.

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

JDK 1.8 내부구조

충돌 발생 시 연결 리스트를 사용하다가, 임계점을 넘으면 트리(TreeNode)로 전환하여 성능을 보장한다.

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

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

결론적으로 JDK 1.8은 충돌이 많은 환경에서도 일관된 성능을 제공하기 위해 내부 구조를 개선하였다.