Какие сложности основных операций HashMap

Какие сложности основных операций HashMap

HashMap — одна из самых важных структур данных в Java. Давайте разберём временную сложность всех основных операций и внутреннее устройство.

Временная сложность основных операций

Средний случай: O(1)

В нормальных условиях HashMap работает за O(1) благодаря хэшированию.

public class HashMapAverageCase {
    
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // put() — O(1)
        map.put("key1", 100);  // Вычисляет hashCode, ищет индекс, вставляет
        map.put("key2", 200);
        map.put("key3", 300);
        
        // get() — O(1)
        Integer value = map.get("key1");  // O(1) в среднем
        
        // remove() — O(1)
        map.remove("key2");  // O(1) в среднем
        
        // containsKey() — O(1)
        boolean exists = map.containsKey("key3");  // O(1) в среднем
        
        // Как это работает:
        // 1. Вычисляет hashCode("key1")
        // 2. Преобразует hashCode в индекс массива
        // 3. Ищет элемент в бакете по этому индексу
        // 4. Обычно бакет содержит 1 элемент -> O(1)
    }
}

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

Худший случай возникает при множественных hash-коллизиях.

public class HashMapWorstCase {
    
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Сценарий худшего случая:
        // Если все ключи имеют одинаковый hashCode()
        
        // До Java 8: LinkedList в каждом бакете
        // При n элементов с коллизией: нужно пройти LinkedList -> O(n)
        
        // Java 8+: При 8+ элементов в одном бакете, LinkedList -> Red-Black Tree
        // Но в крайнем случае всё ещё O(n)
        
        // Пример: вставляем элементы, которые конфликтуют
        for (int i = 0; i < 1000; i++) {
            // Если у них одинаковый hashCode, они в одном бакете
            map.put(i, "value" + i);
        }
        
        // get() в худшем случае: O(n) — нужно пройти все элементы в бакете
        String value = map.get(999);  // O(n) если все в одном бакете
    }
}

Внутреннее устройство HashMap

HashMap использует массив бакетов с цепочками или деревьями для разрешения коллизий.

public class HashMapInternals {
    
    /**
     * Упрощённое внутреннее представление HashMap
     */
    static class SimpleHashMap<K, V> {
        private static final int INITIAL_CAPACITY = 16;
        private Entry<K, V>[] table;
        private int size;
        
        @SuppressWarnings("unchecked")
        public SimpleHashMap() {
            table = new Entry[INITIAL_CAPACITY];
        }
        
        public void put(K key, V value) {
            // 1. Вычисляем hash функцию
            int hash = hash(key);
            
            // 2. Определяем индекс в массиве (hash & (capacity - 1))
            int index = hash & (table.length - 1);
            
            // 3. Вставляем в цепочку (LinkedList или Red-Black Tree)
            Entry<K, V> entry = table[index];
            
            // Если коллизия, добавляем в цепочку
            while (entry != null) {
                if (entry.key.equals(key)) {
                    entry.value = value;  // Обновляем
                    return;
                }
                entry = entry.next;
            }
            
            // 4. Вставляем новый элемент в начало
            table[index] = new Entry<>(key, value, table[index]);
            size++;
        }
        
        public V get(K key) {
            // 1. Вычисляем hash
            int hash = hash(key);
            
            // 2. Ищем индекс
            int index = hash & (table.length - 1);
            
            // 3. Проходим по цепочке
            Entry<K, V> entry = table[index];
            while (entry != null) {
                if (entry.key.equals(key)) {
                    return entry.value;
                }
                entry = entry.next;
            }
            
            return null;
        }
        
        private int hash(K key) {
            return key == null ? 0 : key.hashCode();
        }
        
        static class Entry<K, V> {
            K key;
            V value;
            Entry<K, V> next;
            
            Entry(K key, V value, Entry<K, V> next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }
    }
}

Коллизии и разрешение

public class HashMapCollisions {
    
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        
        // Пример коллизии:
        // Если hashCode("AB") == hashCode("BA")
        // Они попадают в одинаковый бакет
        
        map.put("AB", "value1");  // Вставляется в бакет[hash("AB")]
        map.put("BA", "value2");  // Коллизия! Вставляется в цепочку
        
        // Структура в памяти (Java 7):
        // table[i] -> Entry("AB") -> Entry("BA") -> null
        
        // Java 8+:
        // Если 8+ элементов с коллизией -> Red-Black Tree
        // table[i] -> Red-Black Tree {
        //   "AB" (значение),
        //   "BA" (значение),
        //   ...
        // }
        
        // При поиске:
        // Java 7: O(1 + length of chain) = O(1 + коллизии) = O(n) в худшем
        // Java 8+: O(log n) благодаря Red-Black Tree, но всё ещё может быть O(n)
    }
}

Load Factor и Рехэширование

Load factor = size / capacity. По умолчанию = 0.75

public class HashMapLoadFactor {
    
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // Рехэширование (rehash) — когда коллизии становятся частыми
        
        // Начальная capacity = 16
        // Load factor = 0.75
        // При 12 элементах (16 * 0.75) -> рехэширование
        
        for (int i = 0; i < 12; i++) {
            map.put("key" + i, i);
            // После 12-го элемента -> capacity становится 32
            // Все элементы перехэшируются!
        }
        
        // Рехэширование = O(n) операция
        // Но это происходит редко, поэтому amortized O(1)
        
        // Рехэширование:
        // 1. Создаёт новый массив большего размера (2x)
        // 2. Перепроцесирует hashCode для всех элементов
        // 3. Перераспределяет элементы по новым индексам
    }
}

Сравнение с другими структурами

Best Practices

public class HashMapBestPractices {
    
    public static void main(String[] args) {
        // 1. Используй правильный hashCode() в ключах
        Map<Person, String> map = new HashMap<>();
        
        Person p = new Person("John", 30);
        map.put(p, "Developer");
        
        // Если hashCode() некорректный, O(1) становится O(n)
        
        // 2. Избегай частого рехэширования
        // Если знаешь размер, передай в конструктор:
        Map<String, Integer> largeMap = new HashMap<>(1000);  // Capacity 1024
        
        // 3. Не модифицируй ключи после вставки!
        Set<StringBuilder> keys = new HashSet<>();
        StringBuilder key = new StringBuilder("mykey");
        keys.add(key);
        
        key.append("modified");  // ОПАСНО! hashCode изменился
        // Теперь найти элемент невозможно!
        
        // 4. Используй Strings как ключи (иммутабельные, хороший hashCode)
        Map<String, Value> config = new HashMap<>();
        
        // 5. Для многопоточности используй ConcurrentHashMap
        Map<String, Value> concurrent = new ConcurrentHashMap<>();
    }
    
    static class Person {
        String name;
        int age;
        
        Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return age == person.age && Objects.equals(name, person.name);
        }
    }
}

Вывод

• Средний случай: O(1) — благодаря хэшированию
• Худший случай: O(n) — при массовых коллизиях (редко в нормальных условиях)
• Java 8+: Red-Black Tree при 8+ коллизиях улучшает худший случай
• Рехэширование: Amortized O(1) — происходит редко
• Правильный hashCode(): Критичен для производительности