Какая скорость доступа к значениям в HashMap?

Скорость доступа к значениям в HashMap

HashMap — одна из самых важных структур данных в Java, и критически важно понимать её производительность.

Быстрый ответ

Средняя временная сложность HashMap:

• get(key): O(1) в среднем, O(n) в худшем случае
• put(key, value): O(1) в среднем, O(n) в худшем случае
• remove(key): O(1) в среднем, O(n) в худшем случае

Как работает HashMap

HashMap использует hash table — массив "buckets" (корзин):

Процесс доступа:

1. key → hashCode() → int
2. int % bucket.length → индекс bucket'а
3. В bucket'е найти элемент с нужным ключом

Пример:
key = "Alice"
hashCode() = 2017398376
indexSize = 16
index = 2017398376 % 16 = 8

бuckets[0] → null
buckets[1] → null
buckets[2] → null
...
buckets[8] → {key: "Alice", value: Person(...)}
      ↓
    Найдено! → return Person(...)

Идеальный случай: O(1)

Когда hash function распределяет ключи равномерно:

import java.util.*;

public class HashMapPerformance {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        
        // Добавить 1000 элементов
        for (int i = 0; i < 1000; i++) {
            map.put("key" + i, "value" + i);
        }
        
        // Получить элемент
        long startTime = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            map.get("key500"); // Случайный ключ
        }
        long time = System.nanoTime() - startTime;
        
        System.out.println("Time for 1M gets: " + time + " ns");
        System.out.println("Average per get: " + (time / 1_000_000) + " ns");
    }
}

Результат: ~10-20 наносекунд на операцию get()

Худший случай: O(n)

Когда hash function плохая и все ключи попадают в один bucket:

public class BadHashFunction {
    static class BadKey {
        String value;
        
        public BadKey(String value) {
            this.value = value;
        }
        
        // Плохая hash function — всё идёт в один bucket!
        @Override
        public int hashCode() {
            return 0; // ПЛОХО!
        }
        
        @Override
        public boolean equals(Object obj) {
            return value.equals(((BadKey) obj).value);
        }
    }
    
    public static void main(String[] args) {
        HashMap<BadKey, String> map = new HashMap<>();
        
        // Добавить элементы
        for (int i = 0; i < 1000; i++) {
            map.put(new BadKey("key" + i), "value" + i);
        }
        
        // Поиск в худшем случае
        long startTime = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            map.get(new BadKey("key999")); // Нужно сравнить все 1000!
        }
        long time = System.nanoTime() - startTime;
        
        System.out.println("Worst case: " + (time / 1000) + " ns per operation");
        // Результат: 50000+ ns! В 5000 раз медленнее!
    }
}

Почему O(n) может произойти

Java 8+ решение: Red-Black Tree

Java 7 и ранее:
- Все коллизии хранились в связном списке (LinkedList)
- При много коллизий: O(n) в худшем случае

Java 8+:
- Когда bucket содержит > 8 элементов — преобразуется в Red-Black Tree
- Поиск даже при коллизиях: O(log n) вместо O(n)

// HashMap.java (JDK 8+)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Для linked list (first 8)
}

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;
    // Red-Black Tree для коллизий
}

Фактическая сложность

Размер HashMaap и Load Factor

HashMap<String, String> map = new HashMap<>();
// HashMap(initialCapacity, loadFactor)
HashMap<String, String> map2 = new HashMap<>(16, 0.75f);

initialCapacity = 16 — начальный размер массива buckets loadFactor = 0.75 — при достижении 75% заполнения произойдёт rehash

int threshold = capacity * loadFactor; // 16 * 0.75 = 12

// При добавлении 13-го элемента:
// capacity → 32 (в 2 раза больше)
// Все элементы переходят в новые позиции
// Операция: O(n)

Сравнение с другими Map'ами

*В среднем при нормальной hash function

Практический пример: HashCode

public class Person {
    String name;
    int age;
    
    // ❌ Плохая реализация
    @Override
    public int hashCode() {
        return name.hashCode() % 10; // Распределение: 0-9 (много коллизий!)
    }
    
    // ✅ Хорошая реализация
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + age;
        return result; // Хорошее распределение
    }
}

Или используй IntelliJ автогенерацию (Cmd+N → equals() and hashCode())

Как ускорить HashMap

// 1. Установи правильный initialCapacity
HashMap<String, Integer> map = new HashMap<>(1000); // Если знаешь размер

// 2. Используй правильный loadFactor
HashMap<String, Integer> map = new HashMap<>(1000, 0.75f);

// 3. Реализуй хороший hashCode()
// - Распределяй равномерно
// - Используй prime numbers
// - Комбинируй несколько полей

// 4. Для многопоточности используй ConcurrentHashMap
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 5. Если нужен порядок — LinkedHashMap
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

Итого

✅ HashMap имеет O(1) в среднем случае ✅ Худший случай O(n) в Java 7, O(log n) в Java 8+ ✅ Правильная реализация hashCode() критична ✅ Для многопоточности используй ConcurrentHashMap ✅ Установи initialCapacity если знаешь размер

HashMap — это оптимальный выбор для большинства случаев работы с key-value парами.