PrepBro
← Назад к вопросам

Зачем нужен массив внутри HashMap?

2.2 Middle🔥 191 комментариев
#Коллекции#ООП#Основы Java

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI28 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Массив внутри HashMap

Внутри HashMap используется массив buckets (корзин) — это основная структура данных. Это необходимо для быстрого поиска элементов по ключу через хеширование.

Зачем нужен массив

Железная логика HashMap:

  1. Быстрый поиск — за счёт хеширования ключа получаем индекс в массиве
  2. Распределение данных — массив разбит на buckets (корзины)
  3. Разрешение коллизий — когда два ключа имеют одинаковый хеш

Как это работает внутри

Визуально HashMap состоит из:

Массив buckets:
┌─────────┐
│ [0]     │ -> Node (key1, value1) -> Node (key2, value2) -> null
├─────────┤
│ [1]     │ -> Node (key3, value3) -> null
├─────────┤
│ [2]     │ -> null
├─────────┤
│ [3]     │ -> Node (key4, value4) -> null
└─────────┘

Каждая ячейка массива — это связный список (или красно-чёрное дерево в Java 8+), хранящий элементы с одинаковым хешем.

Алгоритм поиска

public V get(Object key) {
    // 1. Вычисляем хеш ключа
    int hash = hash(key);
    
    // 2. Получаем индекс в массиве (hash % array.length)
    int index = hash & (table.length - 1);  // эквивалентно hash % table.length
    
    // 3. Проходимся по связному списку в bucket'е
    Node<K,V> node = table[index];
    while (node != null) {
        if (node.hash == hash && node.key.equals(key)) {
            return node.value;  // Нашли!
        }
        node = node.next;
    }
    
    return null;  // Не нашли
}

Пример

Предположим, HashMap имеет массив размером 4:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);    // hash="apple" % 4 = 0
map.put("banana", 2);   // hash="banana" % 4 = 1
map.put("apricot", 3);  // hash="apricot" % 4 = 0 (КОЛЛИЗИЯ!)
map.put("cherry", 4);   // hash="cherry" % 4 = 2

Массив buckets:
┌─────────┐
│ [0]     │ -> ("apricot", 3) -> ("apple", 1) -> null
├─────────┤
│ [1]     │ -> ("banana", 2) -> null
├─────────┤
│ [2]     │ -> ("cherry", 4) -> null
├─────────┤
│ [3]     │ -> null
└─────────┘

Поиск apple:

  1. hash("apple") % 4 = 0
  2. Идём в bucket[0]
  3. Проходим по цепочке: ("apricot", 3) → ("apple", 1) ✓ найден

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

Коллизия — когда разные ключи имеют одинаковый хеш.

Java использует метод цепочек (chaining):

Без коллизий:
bucket[0] -> (k1, v1) -> null
bucket[1] -> (k2, v2) -> null
bucket[2] -> (k3, v3) -> null

С коллизиями:
bucket[0] -> (k1, v1) -> (k4, v4) -> (k7, v7) -> null  // 3 ключа!
bucket[1] -> (k2, v2) -> null
bucket[2] -> (k3, v3) -> null

Если bucket'ов становится слишком мало, происходит resizing (расширение массива).

Java 8+ оптимизация

В Java 8 добавлена оптимизация: если в одном bucket'е больше 8 элементов, связный список превращается в красно-чёрное дерево.

// В коде HashMap
static final int TREEIFY_THRESHOLD = 8;

if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);  // Превращаем список в дерево
}

Почему? Поиск в красно-чёрном дереве — O(log n), в списке — O(n).

Связный список (8+ элементов):
Поиск: O(n) — медленно

Красно-чёрное дерево:
Поиск: O(log n) — быстро

Load Factor и Resizing

Массив расширяется при превышении load factor (обычно 0.75):

int capacity = 16;  // Начальный размер
float loadFactor = 0.75f;
int threshold = (int)(capacity * loadFactor);  // 12 элементов

// Когда размер >= 12, массив расширяется:
capacity *= 2;  // 16 -> 32
threshold = (int)(32 * 0.75f);  // 24 элементов

Почему это важно?

  • Слишком маленький array → много коллизий → медленно
  • Слишком большой array → пусто расходуется память
  • Оптимальное соотношение: load factor 0.75

Сложность операций

Без коллизий:
get()    → O(1)  (прямой доступ к bucket'у)
put()    → O(1)
remove() → O(1)

С коллизиями:
get()    → O(n)  (поиск по цепочке)
put()    → O(n)
remove() → O(n)

В Java 8+ с деревом:
get()    → O(log n)  (лучше, чем O(n))

Практический пример кода

public class CustomHashMap<K, V> {
    private static final int INITIAL_CAPACITY = 16;
    private Node<K, V>[] table;
    private int size;
    
    @SuppressWarnings("unchecked")
    public CustomHashMap() {
        table = new Node[INITIAL_CAPACITY];
        size = 0;
    }
    
    public void put(K key, V value) {
        int hash = key.hashCode();
        int index = hash & (table.length - 1);
        
        // Проходим по цепочке в bucket'е
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.hash == hash && node.key.equals(key)) {
                node.value = value;  // Обновляем
                return;
            }
            node = node.next;
        }
        
        // Добавляем в начало цепочки
        Node<K, V> newNode = new Node<>(hash, key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;
    }
    
    public V get(K key) {
        int hash = key.hashCode();
        int index = hash & (table.length - 1);
        
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.hash == hash && node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        
        return null;
    }
    
    static class Node<K, V> {
        int hash;
        K key;
        V value;
        Node<K, V> next;
        
        Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
}

Итог

  1. Массив buckets — основа HashMap для быстрого поиска
  2. Хеширование — преобразует ключ в индекс массива за O(1)
  3. Цепочки/деревья — разрешают коллизии
  4. Resizing — расширяет массив при достижении load factor
  5. Java 8+ — оптимизирует длинные цепочки через красно-чёрные деревья

Без массива HashMap был бы обычной связной последовательностью с O(n) поиском. Именно массив даёт O(1) среднюю сложность.

Зачем нужен массив внутри HashMap? | PrepBro