데이터를 가장 빠르게 찾을 수 있는 방법 중 하나는 HashMap이 있다.

해시맵은 키값을 해시 함수를 통해 인덱스로 변환하여 배열의 특정 위치에 바로 접근해서 O(1) 으로 찾는다.

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

  1. 해시 함수를 통해 인덱스로 배열에 바로 접근하므로 O(1)의 속도를 가진다.
  2. 서로 다른 키가 같은 인덱스에 할당되는 해시 충돌이 발생하면 Linked List로 데이터를 엮는다. (Chaining)
  3. JDK 8부터는 하나의 배열에 쌓인 노드가 임계점을 넘으면 LinkedList를 레드블랙 트리(Red-Black Tree)로 변환한다.

실무에서 유용한 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()을 사용하면 key/value를 순회할 수 있다.

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은 충돌이 많은 환경에서도 일관된 성능을 제공하기 위해 내부 구조를 개선하였다.