Как работает put() в hashCode?

Как работает put() в HashMap: роль hashCode()

Это один из ключевых вопросов на собеседованиях. Правильнее: "Как работает put() в HashMap и какую роль играет hashCode()".

---

Общий процесс: put(key, value)

Загадка: как HashMap за O(1) находит нужное место для элемента?

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 30);  // где это сохранится?
map.put("Bob", 25);

Ответ: используя два уровня хеширования:

1. hashCode() — преобразует ключ в число
2. equals() — проверяет полное совпадение

---

Шаг за шагом: что происходит при put()

Шаг 1: Вычисляем хеш-функцию

public V put(K key, V value) {
  int hash = hash(key);  // вызывает key.hashCode()
  // ...
}

private static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Пример:

String key = "Alice";
int hashCode = key.hashCode();  // например: 2015827293
int hash = 2015827293 ^ (2015827293 >>> 16);  // ~61954

Шаг 2: Находим индекс бакета

int bucketIndex = hash & (buckets.length - 1);

int hash = 61954;
int bucketIndex = 61954 & 15;  // 15 = 16 - 1
// Результат: 2

Итак: элемент будет храниться в buckets[2].

Шаг 3: Работаем с бакетом

Каждый bucket — это linked list или red-black tree:

Node<K,V> node = buckets[bucketIndex];

while (node != null) {
  if (node.hash == hash && 
      (node.key == key || key.equals(node.key))) {
    V oldValue = node.value;
    node.value = value;
    return oldValue;
  }
  node = node.next;
}

addNode(hash, key, value, bucketIndex);

Критично: используется оба hashCode() И equals()!

---

Полный пример: визуализация

HashMap<String, Integer> map = new HashMap<>();

map.put("Alice", 30);
// hashCode("Alice") = 2015827293
// bucketIndex = 2
// buckets[2] = [Node("Alice", 30)]

map.put("Bob", 25);
// hashCode("Bob") = 2058757838
// bucketIndex = 2  (КОЛЛИЗИЯ!)
// buckets[2] = [Node("Alice", 30)] -> [Node("Bob", 25)]

map.put("Alice", 31);
// Ищем в buckets[2]
// Найдено! Меняем значение на 31

---

Коллизии хеш-функции

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

class Person {
  String name;
  
  @Override
  public int hashCode() {
    return 42;  // ❌ УЖАСНАЯ реализация!
  }
  
  @Override
  public boolean equals(Object o) {
    if (!(o instanceof Person)) return false;
    return name.equals(((Person) o).name);
  }
}

Хорошая реализация hashCode():

@Override
public int hashCode() {
  return Objects.hash(name, age, email);
}

---

❌ КРИТИЧНО: Изменение ключа после добавления

class Person {
  String name;
  
  @Override
  public int hashCode() {
    return name.hashCode();
  }
}

Person p = new Person("Alice");
HashMap<Person, String> map = new HashMap<>();
map.put(p, "Engineer");
// Элемент в buckets[5]

p.name = "Bob";  // ❌ Изменили ключ после добавления!
// Теперь hashCode(p) указывает на buckets[10]

map.get(p);  // ищет в buckets[10] — НЕ НАЙДЁТ!

Правило: ключи должны быть immutable (неизменяемыми)!

map.put("Alice", value);  // String immutable - OK
map.put(42, value);       // Integer immutable - OK
map.put(new StringBuilder("Bob"), value);  // mutable - BAD!

---

Resize: когда растёт HashMap

Когда количество элементов превышает load factor (0.75):

HashMap<String, Integer> map = new HashMap<>();
// capacity = 16, load_factor = 0.75
// resize происходит при 12-м элементе (0.75 * 16)

// При resize:
// 1. Создаётся новый массив размером 32
// 2. ВСЕ элементы перехешируются!
// 3. bucketIndex пересчитывается (зависит от length)

---

Полная схема put()

put(key, value)
    |
  hash = hash(key.hashCode())
    |
  bucketIndex = hash & (length - 1)
    |
  Поиск элемента в buckets[bucketIndex]
    |
  equals() совпадает?
    |-- ДА: обновить значение
    |-- НЕТ: добавить новый Node
    |
  size >= capacity * load_factor?
    |-- ДА: resize() - увеличить массив, перехешировать всё
    |-- НЕТ: готово

Ключевые моменты

✅ hashCode() быстро определяет примерное место (bucket)
✅ equals() проверяет точное совпадение в bucket
✅ Плохой hashCode() заставляет все элементы в один bucket (O(n) вместо O(1))
✅ Ключи должны быть immutable
✅ При resize все элементы пересчитываются
✅ Коллизии обрабатываются через linked list (Java 8+ использует red-black tree при 8+ элементов)