Hash Table (Хэш-таблица)

Хэш-таблица хранит пары ключ→значение и обеспечивает вставку, поиск и удаление за O(1) в среднем. Ключ прогоняется через хэш-функцию, которая даёт индекс в массиве бакетов.

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

Операция	Средний случай	Худший случай
Вставка	O(1)	O(n)
Поиск	O(1)	O(n)
Удаление	O(1)	O(n)

Худший случай O(n) возникает при массовых коллизиях (все ключи в один бакет). На практике хорошая хэш-функция + рехэширование держат операции близко к O(1).

Коллизии

Когда два ключа дают одинаковый индекс:

• Цепочки (chaining) — в каждом бакете связный список/дерево элементов.
• Открытая адресация (open addressing) — ищем следующий свободный слот (linear/quadratic probing).

При заполнении выше порога (load factor) таблица рехэшируется — размер увеличивается, элементы перераспределяются.

Map и Set в JS

// Map — пары ключ→значение, ключ любого типа
const map = new Map();
map.set('a', 1);      // O(1)
map.get('a');         // O(1)
map.has('a');         // O(1)
map.delete('a');      // O(1)
 
// Object — тоже хэш-таблица, но ключи только строки/символы
const freq = {};
for (const ch of 'anagram') freq[ch] = (freq[ch] || 0) + 1;
 
// Set — множество уникальных значений
const seen = new Set();
seen.add(1); seen.has(1); // O(1)

Хэш-таблицы — основа паттерна «подсчёт частот» и поиска дубликатов за O(1).

См. также

• two-pointers — альтернатива для отсортированных данных
• LeetCode: задачи (раздел «Хэш-таблицы и множества»)