A HashMap is a data structure that allows for finding values in constant time O(1) on average by mapping keys to indices via a hash function.

Core Structure and O(1) Principles (JDK 8)

A HashMap maps a key to a ‘hash code’, which then points to an array index.

  1. Array-based Access: Direct access to array indices via hash function provides O(1) performance.
  2. Collision Resolution (Chaining): If multiple keys map to the same index, they are stored in a Linked List.
  3. Performance Optimization (Treeify): Since JDK 8, if a bucket exceeds the threshold, the Linked List is converted to a Red-Black Tree, improving search performance from O(N) to O(log N).

Advanced Java HashMap Methods

1. getOrDefault(K key, V defaultValue)

Returns the value if the key exists, otherwise returns the default.

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

2. putIfAbsent(K key, V value)

Stores the value only if the key is missing.

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

3. computeIfAbsent(K key, Function mappingFunction)

Computes and stores a value only if the key is missing.

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

4. compute(K key, BiFunction remappingFunction)

Computes and updates the value regardless of existence.

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

5. computeIfPresent(K key, BiFunction remappingFunction)

Recomputes the value only if the key exists.

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

Essential Lookup and Iteration

1. containKey(Object key)

Checks if a key exists.

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

2. Iteration using Enhanced For-loop

Iterates over entries efficiently.

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

JDK 1.7 vs 1.8 Comparison

The primary difference lies in handling hash collisions.

JDK 1.7 internal structure

충돌 시 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 internal structure

충돌 발생 시 연결 리스트를 사용하다가, 임계점을 넘으면 트리(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;
}

In summary, JDK 1.8 provides consistent performance even under heavy collision environments.