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

Hash Table — структура данных, которая хранит пары ключ-значение, используя хэш-функцию для вычисления индекса (бакета), обеспечивая в среднем O(1) для вставки, удаления и поиска.

Зачем нужно

Хэш-таблица — одна из самых важных структур данных. Она превращает операцию поиска из O(n) в O(1). JavaScript Object, Map, Set — все построены на хэш-таблицах. Понимание хэширования и коллизий помогает писать эффективный код и проходить собеседования.

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

  • JavaScript Object (свойства хранятся в хэш-таблице)
  • Map и Set (реализованы как хэш-таблицы)
  • Базы данных (индексы)
  • Кэширование (Redis, Memcached)
  • Дедупликация данных
  • Маршрутизация (URL → handler)
  • Компиляторы (таблица символов)

Предпосылки

Принцип работы

1. Ключ подаётся в хэш-функцию
2. Хэш-функция возвращает числовой хэш
3. Хэш преобразуется в индекс массива (hash % size)
4. Значение сохраняется в этом индексе (бакете)

Пример:
hash("name") = 7432581 → 7432581 % 16 = 5 → buckets[5] = "Alice"
hash("age")  = 2938474 → 2938474 % 16 = 10 → buckets[10] = 30

Бакеты (массив):
Index: [0] [1] [2] [3] [4] [5]      [6] ... [10]     [15]
Data:   -   -   -   -   -  "Alice"   -  ...  30        -
Key:                       "name"             "age"

Хэш-функция

Хэш-функция превращает ключ любого типа в число.

// Простая хэш-функция для строк
function simpleHash(key, tableSize) {
  let hash = 0;

  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) % tableSize;
  }

  return hash;
}

console.log(simpleHash('name', 16)); // какой-то индекс 0-15
console.log(simpleHash('age', 16));  // другой индекс 0-15

Требования к хэш-функции:

  • Детерминированная: одинаковый вход → одинаковый выход
  • Равномерное распределение: минимум коллизий
  • Быстрая: O(1) или O(k), где k — длина ключа

Коллизии

Коллизия — когда два разных ключа получают одинаковый индекс.

Метод 1: Chaining (цепочки)

Каждый бакет хранит связный список.

Бакет 5: [("name","Alice")] → [("eman","Bob")] → null

hash("name") = 5
hash("eman") = 5  ← коллизия! Добавляем в цепочку

class HashTableChaining {
  #buckets;
  #size;

  constructor(size = 16) {
    this.#buckets = new Array(size).fill(null).map( => );
    this.#size = size;
  }

  #hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.#size;
    }
    return hash;
  }

  set(key, value) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];

    // Обновить если ключ уже существует
    for (const pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }

    bucket.push([key, value]);
  }

  get(key) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];

    for (const pair of bucket) {
      if (pair[0] === key) return pair[1];
    }

    return undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  delete(key) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        return true;
      }
    }

    return false;
  }

  keys {
    const result = ;
    for (const bucket of this.#buckets) {
      for (const [key] of bucket) {
        result.push(key);
      }
    }
    return result;
  }
}

// Использование
const ht = new HashTableChaining();
ht.set('name', 'Alice');
ht.set('age', 30);
ht.set('city', 'Moscow');

console.log(ht.get('name')); // 'Alice'
console.log(ht.has('age'));   // true
ht.delete('city');
console.log(ht.keys());      // ['name', 'age']

Метод 2: Open Addressing (открытая адресация)

При коллизии ищем следующее свободное место.

class HashTableOpen {
  #keys;
  #values;
  #size;
  #count = 0;

  constructor(size = 16) {
    this.#size = size;
    this.#keys = new Array(size).fill(undefined);
    this.#values = new Array(size).fill(undefined);
  }

  #hash(key, attempt = 0) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.#size;
    }
    // Линейное пробирование: hash + attempt
    return (hash + attempt) % this.#size;
  }

  set(key, value) {
    if (this.#count / this.#size > 0.7) {
      this.#resize;
    }

    for (let attempt = 0; attempt < this.#size; attempt++) {
      const index = this.#hash(key, attempt);

      if (this.#keys[index] === undefined || this.#keys[index] === key) {
        if (this.#keys[index] === undefined) this.#count++;
        this.#keys[index] = key;
        this.#values[index] = value;
        return;
      }
    }
  }

  get(key) {
    for (let attempt = 0; attempt < this.#size; attempt++) {
      const index = this.#hash(key, attempt);

      if (this.#keys[index] === undefined) return undefined;
      if (this.#keys[index] === key) return this.#values[index];
    }

    return undefined;
  }

  #resize {
    const oldKeys = this.#keys;
    const oldValues = this.#values;
    this.#size *= 2;
    this.#keys = new Array(this.#size).fill(undefined);
    this.#values = new Array(this.#size).fill(undefined);
    this.#count = 0;

    for (let i = 0; i < oldKeys.length; i++) {
      if (oldKeys[i] !== undefined) {
        this.set(oldKeys[i], oldValues[i]);
      }
    }
  }
}

Load Factor и ресайзинг

Load factor = количество элементов / размер таблицы.

  • Load factor > 0.7 → слишком много коллизий → ресайз (удвоение)
  • Load factor < 0.25 → слишком мало элементов → можно уменьшить
Load 0.3: мало коллизий, быстрый доступ
Load 0.7: начинаются коллизии, нужен ресайз
Load 1.0: каждая вставка — коллизия (для open addressing)

JavaScript Object как хэш-таблица

// Object внутренне использует хэш-таблицу для свойств
const user = {};
user['name'] = 'Alice';    // hash("name") → бакет
user['age'] = 30;           // hash("age") → бакет

// V8 оптимизирует объекты:
// - "Быстрые" объекты: фиксированная структура (hidden classes)
// - "Медленные" объекты: настоящая хэш-таблица (при delete, динамических ключах)

// Поэтому Map часто быстрее для частых добавлений/удалений

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

Операция Средний Худший (все коллизии)
set O(1) O(n)
get O(1) O(n)
delete O(1) O(n)
has O(1) O(n)

Худший случай (O(n)) возникает крайне редко при хорошей хэш-функции.

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

  1. Плохая хэш-функция. Если все ключи попадают в один бакет — O(n) вместо O(1)
  2. Не учитывать load factor. Без ресайзинга производительность деградирует
  3. Путать хэширование и шифрование. Хэш — не обратимый, для индексации; шифрование — обратимое, для секретности
  4. Ожидать порядок. Классическая хэш-таблица не гарантирует порядок (JS Map — гарантирует)

Практика

  1. Реализуйте HashTable с chaining
  2. Добавьте метод resize, который удваивает размер при load factor > 0.75
  3. Реализуйте countFrequency(text) — подсчёт частоты слов через вашу HashTable
  4. Сравните производительность вашей HashTable и встроенного Map

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

Ресурсы

  • visualgo.net/en/hashtable — визуализация
  • V8 Blog — Fast properties in V8
  • Introduction to Algorithms (CLRS), глава 11
  • Grokking Algorithms, глава 5 (Aditya Bhargava)