Хеш-таблицы: множества и словари

Проблема, которую мы решаем:

Представь справочник. В нём 1 миллион имён и телефонов. Если ты хранишь их в массиве и ищешь «Алиса», то скользишь с начала: Алиса? Нет. Боб? Нет. Виктор? Нет. … — O(n) времени.

Но справочник организован по алфавиту. Ты прыгаешь на раздел «А», потом скользишь только по нескольким именам. Всё ещё линейно, но быстрее на практике.

Можем ли мы быстрее? Да, если мы можем прыгнуть прямо к ответу без скольжения вообще. Это то, что делает хеширование.

Идея хеширования:

Хеш-функция — это функция, которая берёт ключ (имя, число, слово) и возвращает индекс — число от 0 до n-1, где n — размер массива. Идея хитра: вместо того чтобы скользить по массиву, использу хеш-функцию, чтобы вычислить, где должны быть данные, потом смотру туда мгновенно.

function hash(key, arraySize) {
  // Превращу ключ в число от 0 до arraySize - 1
  return someFormula(key) % arraySize;
}

const index = hash("Alice", 1000);  // Возвращает, скажем, 342
// Смотру позицию 342 — телефон Алисы лежит там (в идеале)

В хорошей хеш-функции разные ключи преобразуются в разные индексы. «Alice» всегда → 342. «Bob» может → 157. «Charlie» → 899. Массив имеет ящик на каждом индексе, и пара ключ–значение лежит в том ящике.

Почему O(1)? Вычислю индекс (одна формула) и смотру на тот индекс (одна операция). Готово. Нет цикла.

Хеш-множество против хеш-словаря:

Хеш-множество (неупорядоченное множество) хранит только значения — оно отвечает «есть ли X в множестве?». Оно использует хеш-функцию, чтобы преобразовать каждое значение в индекс массива, потом хранит значение (или маркер) на том индексе.

      1
      const mySet = new Set();
    

      2
      mySet.add(10);
    

      3
      mySet.add(20);
    

      4
      mySet.add(30);
    

      5
       
    

      6
      console.log(mySet.has(20));  // true, найдено мгновенно через хеш
    

      7
      console.log(mySet.has(99));  // false, смотрели и нет
    

Хеш-словарь (или словарь) хранит пары ключ–значение. Для каждого ключа вычисляет индекс используя хеш-функцию, потом хранит оба — ключ и значение — на том индексе. Поиски по ключу O(1) в среднем.

      1
      const myMap = new Map();
    

      2
      myMap.set("Alice", "555-1234");
    

      3
      myMap.set("Bob", "555-5678");
    

      4
       
    

      5
      console.log(myMap.get("Alice"));  // "555-1234", найдено за O(1)
    

      6
      console.log(myMap.get("Charlie"));  // undefined, нет, но всё ещё O(1)
    

Основные операции на хеш-множестве или хеш-словаре:

1. Добавить/установить по ключу — Хешировать ключ, прыгнуть на индекс, положить значение. O(1) в среднем.
2. Поиск/содержит — Хешировать ключ, прыгнуть на индекс, проверить, есть ли там. O(1) в среднем.
3. Удалить по ключу — Хешировать ключ, прыгнуть на индекс, убрать. O(1) в среднем.

Слово «в среднем» важно: при плохой хеш-функции или при тяжёлых коллизиях (смотри граничный случай) производительность может упасть. Но при хорошей хеш-функции и разумном факторе загрузки (число элементов / размер массива) O(1) в среднем надёжно.

Трейд-офф:

• Стоимость памяти: Хеш-множество или хеш-словарь использует дополнительную память — массив для хранения ящиков, обычно с запасом, чтобы коллизии были редки. Ты тратишь память, чтобы сэкономить время.
• Нет порядка: Итерация по хеш-множеству или хеш-словарю не следует никакому предсказуемому порядку (кроме того, что JavaScript Maps итерируют в порядке вставки — уступка ожиданиям разработчика).
• Ключи должны быть хешируемы: В некоторых языках только определённые типы могут быть ключами (неизменяемые типы в Python, например). JavaScript более снисходителен: ты можешь хешировать любое значение.