Хеш-таблица

Хеш-таблица (hash table / hash map) — структура данных, обеспечивающая хранение пар ключ-значение с O(1) амортизированным временем поиска, вставки и удаления за счёт хеш-функции, преобразующей ключ в индекс массива.

Зачем нужно

Хеш-таблица — одна из самых используемых структур данных: именно она лежит в основе словарей Python, объектов JavaScript, HashMap в Java. Замена линейного поиска O(n) на хеш-таблицу O(1) — стандартная оптимизация, известная как «пожертвовать памятью ради скорости» (time-space tradeoff).

Где используется

  • Кэширование и мемоизация
  • Подсчёт частот символов/слов
  • Поиск дубликатов за O(n) вместо O(n^2)
  • Реализация множеств (Set)
  • Индексы баз данных (hash index)
  • Symbol tables в компиляторах

Основной контент

Как работает

key "name" → hash("name") → 42 % buckets → bucket[42] → "Alice"

Хеш-функция: string → number → index
Bucket (корзина): список пар [key, value]
Load factor: n / capacity (обычно ≤ 0.75)

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

// Два ключа дают одинаковый хеш → коллизия

// Метод 1: Chaining (цепочки) — каждый bucket — связный список
class HashTable {
  constructor(size = 53) {
    this.table = new Array(size).fill(null).map( => );
  }

  #hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * (i + 1)) % this.table.length;
    }
    return hash;
  }

  set(key, value) {
    const idx = this.#hash(key);
    const bucket = this.table[idx];
    const existing = bucket.find(([k]) => k === key);
    if (existing) existing[1] = value; // обновить
    else bucket.push([key, value]);    // добавить
  }

  get(key) {
    const bucket = this.table[this.#hash(key)];
    return bucket.find(([k]) => k === key)?.[1];
  }

  delete(key) {
    const idx = this.#hash(key);
    const bucket = this.table[idx];
    const pos = bucket.findIndex(([k]) => k === key);
    if (pos !== -1) bucket.splice(pos, 1);
  }
}

const ht = new HashTable();
ht.set('name', 'Alice');
ht.set('age', 30);
console.log(ht.get('name')); // 'Alice'

Встроенные структуры в JavaScript

// Object — простейшая хеш-таблица (строковые/символьные ключи)
const obj = {};
obj['key'] = 'value'; // O(1)
'key' in obj;         // O(1)
delete obj['key'];    // O(1)

// Map — правильная хеш-таблица (любые ключи, порядок вставки)
const map = new Map();
map.set('key', 42);   // O(1)
map.get('key');       // O(1)
map.has('key');       // O(1)
map.delete('key');    // O(1)
map.size;             // O(1)

// Set — хеш-множество
const set = new Set([1, 2, 3]);
set.has(2);           // O(1)
set.add(4);           // O(1)
set.delete(2);        // O(1)

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

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

Худший случай возникает при плохой хеш-функции и многих коллизиях. Рехеширование — O(n) амортизированно при превышении load factor.

Типичный паттерн: подсчёт частот

function twoSum(nums, target) {
  const seen = new Map(); // значение → индекс
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return null;
}
// twoSum([2, 7, 11, 15], 9) → [0, 1] — O(n) вместо O(n²)

Частые ошибки

  • Использовать обычный объект {} как хеш-таблицу — ключи приводятся к строке, порядок не гарантирован до ES2015.
  • Забывать о коллизиях: хеш-функция не может гарантировать уникальность индексов.
  • Сравнивать объекты как ключи Map по ссылке: new Map(); map.set({}, 1); map.get({}) → undefined (разные объекты).
  • Итерировать Object через for...in — захватывает унаследованные свойства; используй Object.entries() или Map.

Связанные темы

Ресурсы