Как устроена и организована структура данных HashMap в Java?

HashMap в Java основан на принципах хеширования. Он хранит пары "ключ-значение".

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

• Массив бакетов (емкостей). Каждый бакет — это связный список (или дерево, начиная с Java 8, при большом количестве коллизий).
• При добавлении элемента (put):
  1. Вычисляется хеш-код ключа (key.hashCode()).
  2. Хеш-код модифицируется для лучшего распределения (hash).
  3. Используя модифицированный хеш и размер массива бакетов, вычисляется индекс бакета, куда будет помещен элемент (хеш & (размер_массива - 1)).
  4. Элемент (пара "ключ-значение" в виде объекта Node) помещается в этот бакет. Если бакет уже содержит элементы, новый элемент добавляется в начало связного списка или дерева.
  5. При добавлении проверяется наличие ключа: используется метод equals() для сравнения ключей внутри бакета. Если ключ найден, значение обновляется.
• При получении элемента (get):
  1. Так же вычисляется индекс бакета по ключу.
  2. Внутри бакета происходит поиск элемента по ключу, используя методы hashCode() и equals().
  3. Возвращается связанное значение.

Организация:

• Коллизии: Если несколько ключей имеют одинаковый хеш-код и попадают в один бакет, элементы хранятся в виде связного списка. С Java 8 при количестве элементов в бакете, превышающем порог (обычно 8), связный список преобразуется в дерево для более быстрого поиска (O(log n) вместо O(n)).
• Ресайзинг: Когда количество элементов превышает "порог загрузки" (load factor * capacity), HashMap увеличивает размер внутреннего массива бакетов (обычно вдвое) и перехеширует все элементы. Это дорогая операция (O(n)).
• Параметры:
  • capacity: Начальный размер массива бакетов (по умолчанию 16).
  • load factor: Порог загрузки (по умолчанию 0.75). Определяет, когда произойдет ресайзинг.

Почему важны hashCode() и equals():

• Корректная работа HashMap зависит от правильной реализации этих методов.
• Если equals() возвращает true для двух объектов, то и hashCode() должен возвращать одинаковое значение.
• Неправильная реализация может привести к тому, что элементы не будут найдены (get вернет null), даже если они были добавлены.

Пример структуры Node:

// Internal only
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap обеспечивает быстрое (в среднем O(1)) добавление, получение и удаление элементов при равномерном распределении хешей. В худшем случае (сильные коллизии) операция может стать O(n) или O(log n) с деревьями.

Не потокобезопасен. Для потокобезопасного использования следует использовать ConcurrentHashMap или Collections.synchronizedMap(new HashMap<...>(...)).