Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
HashMap внутри - Структура и реализация
HashMap в Java использует массив бакетов (buckets) с цепочками связанных списков (или красно-чёрных деревьев в Java 8+) для разрешения коллизий хеша.
Базовая структура
HashMap внутри:
┌─────────────────────────────────────────────────────┐
│ Массив бакетов (Node<K,V>[]) │
├─────────────────────────────────────────────────────┤
│ [0] → null │
│ [1] → Node(key="Alice", hash=...) ↔ Node(...) │
│ [2] → null │
│ [3] → Node(key="Bob", hash=...) │
│ [4] → Node(...) ↔ Node(...) ↔ Node(...) │
│ ... │
│ [15] → null │
└─────────────────────────────────────────────────────┘
Алгоритм вставки/поиска
public class HashMapDemo {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
// Что происходит при map.put("Alice", 25)?
// 1. Вычисляется hash("Alice")
// 2. Определяется индекс в массиве: hash % bucketLength
// 3. В бакете проверяется цепочка на существование ключа
// 4. Если ключ существует - обновляется значение
// 5. Если нет - добавляется новый Node
map.put("Alice", 25);
map.put("Bob", 30);
map.put("Charlie", 35);
}
}
Вычисление хеша (Java 8+)
// Исходный хеш от объекта
int hashCode = "Alice".hashCode(); // Например: 1970659892
// Комбинирование с upper bits (XOR)
int hash = hashCode ^ (hashCode >>> 16);
// Используется только при вычислении индекса
int index = hash & (capacity - 1); // Быстро заменяет % модуль
Структура Node (Entry)
// Внутренний класс HashMap
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // Кешированный хеш ключа
final K key; // Неизменяемый ключ
V value; // Значение
Node<K, V> next; // Ссылка на следующий node в цепочке
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
Коллизии хеша и цепочки
// Пример коллизии:
// hash("Alice") % 5 = 1
// hash("Charlie") % 5 = 1 // Коллизия!
HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Charlie", 35);
// Что на самом деле в памяти:
// buckets[1] → Node(Alice) → Node(Charlie) → null
Java 8+ Оптимизация: Бинарные деревья
// Когда цепочка в одном бакете становится слишком длинной
// (TREEIFY_THRESHOLD = 8 элементов), она преобразуется в красно-чёрное дерево
// Условия для преобразования:
if (binCount >= TREEIFY_THRESHOLD - 1) {
// Преобразовать цепочку в TreeNode
}
// Результат: вместо O(n) поиск в цепочке → O(log n) в дереве
Load Factor и Resizing
public class HashMapResizingExample {
// Важные параметры:
// - capacity: текущий размер массива (16 по умолчанию)
// - size: количество элементов в HashMap
// - loadFactor: коэффициент заполнения (0.75 по умолчанию)
// - threshold: максимальный size перед resizing (capacity * loadFactor)
public void demonstrateResizing() {
HashMap<String, Integer> map = new HashMap<>();
// Начальные значения:
// capacity = 16
// threshold = 16 * 0.75 = 12
// Добавляем 12 элементов
for (int i = 0; i < 12; i++) {
map.put("key" + i, i); // Пока не увеличение
}
// Добавляем 13-й элемент
map.put("key12", 12); // RESIZE!
// Что происходит при resizing:
// 1. Создаётся новый массив (capacity * 2 = 32)
// 2. Пересчитываются индексы для всех элементов
// 3. Переустанавливается threshold = 32 * 0.75 = 24
// 4. Старый массив затирается
}
}
Процесс Resizing детально
Resizing процесс:
Перед (capacity = 16):
buckets[0-15] → содержат элементы
После (capacity = 32):
buckets[0-31] → переупорядоченные элементы
index = hash & (capacity - 1)
// Старый: hash & 0xF (15 = 1111 в двоичном)
// Новый: hash & 0x1F (31 = 11111 в двоичном)
Полный пример с внутренней логикой
public class HashMapInternals {
static class SimpleHashMap<K, V> {
static final int DEFAULT_CAPACITY = 16;
static final float LOAD_FACTOR = 0.75f;
Node<K, V>[] table;
int size = 0;
int threshold;
@SuppressWarnings("unchecked")
public SimpleHashMap() {
table = new Node[DEFAULT_CAPACITY];
threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
}
public void put(K key, V value) {
// Проверка на resizing
if (size >= threshold) {
resize();
}
// Вычисление хеша
int hash = hash(key);
int index = index(hash);
// Поиск в цепочке
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, table[index]);
table[index] = newNode;
size++;
}
public V get(K key) {
int hash = hash(key);
int index = index(hash);
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;
}
@SuppressWarnings("unchecked")
private void resize() {
Node<K, V>[] oldTable = table;
table = new Node[oldTable.length * 2];
threshold = (int) (table.length * LOAD_FACTOR);
size = 0;
for (Node<K, V> node : oldTable) {
while (node != null) {
put(node.key, node.value);
node = node.next;
}
}
}
private int hash(K key) {
if (key == null) return 0;
return key.hashCode();
}
private int index(int hash) {
return (hash & 0x7FFFFFFF) % table.length;
}
}
}
Производительность
// Средняя временная сложность:
// get/put/remove: O(1) при хорошем распределении хеша
// В худшем случае (все коллизии): O(n) в Java 7, O(log n) в Java 8+
// Пространственная сложность: O(n)
Null ключи и значения
HashMap<String, Integer> map = new HashMap<>();
// HashMap позволяет один null ключ и много null значений
map.put(null, 100); // ✓ Допустимо
map.put("key", null); // ✓ Допустимо
map.put(null, 200); // Обновляет значение для null ключа
System.out.println(map.get(null)); // 200
HashMap — это оптимизированная структура данных, обеспечивающая быстрый поиск в среднем случае через комбинацию хеширования и цепочек/деревьев.