Хеш-таблицы

Если 47 хранится в таблице из 7 корзин, компьютер сразу идёт в корзину 47 mod 7 = 5, а не перебирает всю таблицу.

Превращаем ключ в позицию

До сих пор найти значение значило искать: до n шагов в неотсортированном массиве или связном списке. Но массив может дойти до любой позиции за один шаг. А что, если позицию подскажет сам ключ? Если бы ключи были маленькими целыми числами, скажем номерами учеников от 0 до 99, можно было бы держать массив из 100 ячеек и хранить ученика k в ячейке k. В конспектах MIT это называется массивом прямого доступа. Способ не работает, когда возможных ключей огромное число, например номера телефонов или слова, потому что ячейку для каждого возможного ключа себе не позволишь.

Хеш-функция решает это, сжимая любой ключ в небольшой диапазон позиций от 0 до m − 1. Простая функция для целых чисел: h(k) = k mod m, остаток от деления на m. Массив из m ячеек называется хеш-таблицей, а его ячейки часто называют корзинами. Чтобы сохранить 47 при m = 7, вычисли 47 mod 7 = 5 и положи число в корзину 5. Чтобы потом найти 47, вычисли то же самое и смотри только в корзину 5.

Коллизии и цепочки

Есть проблема. Если корзин 7, а возможных ключей больше 7, некоторым ключам придётся делить корзину: 12, 33 и 47 все дают остаток 5. Это называется коллизией, и конспекты MIT отмечают, что её не избежать по принципу Дирихле. Обычное средство называется методом цепочек: каждая корзина хранит маленький список, цепочку, из всех ключей, которые туда попали. Тогда поиск 47 стоит 1 шаг на хеш плюс одно сравнение на каждый проверенный ключ в цепочке 5. Если перед ним стоят 12 и 33, это 1 + 3 = 4 шага.

Какой длины цепочки? Если ключи распределяются равномерно, в каждой цепочке около n/m ключей, это число называется заполненностью (коэффициентом заполнения). Держи m примерно равным n, и цепочки останутся короткими, так что поиск, вставка и удаление в среднем занимают постоянное число шагов. Опасность в плохом распределении. Если каждый ключ попадает в одну и ту же корзину, одна цепочка хранит все n ключей, и таблица ничем не лучше связного списка. В лаборатории задай 7 корзин и вставь 14, 21 и 28: все они попадут в корзину 0.

Хеш-таблицы в JavaScript

Самому писать хеш-таблицу приходится редко, потому что в JavaScript есть Map и Set. Спецификация ECMAScript говорит, что они «должны быть реализованы с помощью хеш-таблиц или других механизмов, которые в среднем дают время доступа, сублинейное по числу элементов». Иначе говоря, map.get(key) и set.has(x) должны работать быстрее, чем перебор всей коллекции. MDN добавляет, что Map хранит ключи в порядке вставки и, в отличие от обычного объекта, не содержит ключей по умолчанию, которые могли бы совпасть с твоими.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, без перебора списка
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true