Где применяется
1. Задача
Встроенные Map и Set из уроков про коллекции находят значение по ключу примерно за один шаг, сколько бы ключей в них ни лежало. В этом уроке ты увидишь, как они это делают. Как структура сразу попадает в нужное место и не просматривает каждую запись?
Секрет в хеш-функции. Это небольшое правило, которое превращает любой ключ в число, а число указывает на ячейку. Если число посчитано правильно, искать ничего не нужно: ты сразу идёшь в нужную ячейку.
2. Простыми словами
Возьми ключ "dog" и таблицу из 3 ячеек с номерами 0, 1 и 2. Постоянное правило превращает "dog" в номер ячейки. Правило этого урока даёт 2 (арифметика будет в следующем разделе). Значит, "dog" хранится в ячейке 2.
Потом ты ищешь "dog". Применяешь то же правило к тому же ключу и снова получаешь 2. Идёшь прямо в ячейку 2, и ключ там. Ячейки 0 и 1 ты не проверяешь. На этом правиле всё и держится: на входе ключ, на выходе номер ячейки, и одинаковые ключи всегда ведут в одну и ту же ячейку.
3. Идея
Хеш-функция это правило, которое берёт ключ и возвращает число. Нам нужно правило, которое дёшево считать и которое для одного и того же ключа всегда даёт одно и то же число.
Простое правило для текста: сложить коды символов всех букв. Код символа это число, которым компьютер обозначает букву: "a" это 97, "b" это 98 и так далее. Слово "cat" превращается в 99 + 97 + 116 = 312. Эта сумма и есть «сырой» хеш, ещё не превращённый в номер ячейки.
Сумма может быть большой, а ячеек в таблице ограниченное число. Пусть их numBuckets, с номерами от 0 до numBuckets - 1. Чтобы получить из большой суммы допустимый номер, бери остаток от деления суммы на numBuckets. Остаток пишется знаком %, а саму операцию называют взятием по модулю. Например, 312 % 3 равно 0, потому что 312 делится на 3 без остатка. Остаток всегда лежит от 0 до numBuckets - 1, то есть ровно в диапазоне номеров ячеек. Поэтому bucketIndex = sum % numBuckets всегда указывает на настоящую ячейку.
Ячейку в хеш-таблице называют корзиной (bucket). Вот как "cat", "dog" и "bird" попадают в таблицу из 3 корзин:
Теперь поиск. Чтобы найти "dog", снова применяем правило: 100 + 111 + 103 = 314, и 314 % 3 = 2. Идём прямо в корзину 2. Корзины 0 и 1 не просматриваем. Поэтому хеш-структура и отвечает примерно за один шаг.
Посмотри на корзину 0: в ней два ключа. "cat" дал сумму 312, "bird" дал 98 + 105 + 114 + 100 = 417. Обе суммы делятся на 3 без остатка, поэтому оба ключа попали в корзину 0. Два разных ключа в одной корзине называют коллизией. Это не ошибка. Когда ключей больше, чем корзин, коллизий не избежать. В этом уроке мы ищем один ключ и на этом останавливаемся. Что делать с переполненной корзиной, разберём в следующем уроке.
4. Во что это обходится
Хеш-функция проходит по символам ключа один раз. Для короткого ключа это практически O(1). Выбор корзины это одно взятие по модулю, тоже O(1). Значит, найти корзину для ключа стоит постоянное время, сколько бы ключей уже ни лежало в таблице. Перебор всех записей стоил бы O(n).
Память: O(numBuckets) на пустую таблицу и O(n) на n хранимых ключей. distribute проходит по ключам один раз, но каждый ключ стоит своего прохода по буквам, а таблица начинается с numBuckets пустых списков. Поэтому время O(numBuckets + суммарная длина ключей), то есть O(numBuckets + n) для коротких ключей.
Одна честная оговорка: «примерно один шаг» верно, только если ключи ложатся по корзинам равномерно. Если плохой хеш сложит все ключи в одну корзину, поиск снова превратится в перебор. Как раскладывать ключи ровно и как разбирать переполненную корзину, ты узнаешь в следующих уроках.
6. Где это встречается
Шардирование (разбиение данных на части, которые хранятся на разных серверах) делает то же самое. Кэш или база данных разбиты на N частей. Чтобы решить, в какой части лежит ключ, система хеширует ключ и берёт остаток от деления на N. Это ровно bucketIndex. Поэтому один и тот же ключ всегда попадает в одну и ту же часть, и чтение находит то, что записали. Партиции в Kafka и распределение нагрузки по серверам используют ту же идею с более надёжной хеш-функцией. Консистентное хеширование в распределённых кэшах устроено сложнее: оно подбирает части так, чтобы при добавлении сервера переезжало мало ключей. Каждый Map, Set, словарь в Python и хеш-индекс в базе данных начинается с того же: ключ превращается в число, число в ячейку.
На LeetCode
Задачи, где каждый элемент превращается в ключ и попадает в свою корзину, чтобы элементы с одинаковым ключом встретились. Например, группы анаграмм, пары по остатку от деления или хеш-множество, которое ты строишь сам.
Отсортированные буквы слова дают всем анаграммам один ключ, так же как «ab» и «ba» попали в одну корзину.
Разложи песни по корзинам по остатку длины от деления на 60 и считай пары между корзиной r и корзиной 60 минус r.
Построй таблицу сам и выбирай корзину ключа через key % numBuckets, как это делает bucketIndex.
Твоя задача (Tier 1)
Напиши две функции: bucketIndex(key, numBuckets) и distribute(keys, numBuckets).
bucketIndex превращает текстовый ключ в номер корзины. distribute с её помощью раскладывает список ключей по корзинам.
bucketIndex(key, numBuckets):keyэто текст,numBucketsэто целое число больше нуля. Возвращает номер корзины для ключа, всегда от0доnumBuckets - 1.distribute(keys, numBuckets):keysэто список текстовых ключей. Возвращает список изnumBucketsсписков, где каждый ключ лежит в своей корзине.
Шаги:
- Для
bucketIndex: сложи коды символов всех букв вkey. Верни остаток от деления этой суммы наnumBuckets. У одинаковых ключей одинаковые суммы, поэтому они всегда попадают в одну корзину. - Для
distribute: создайnumBucketsпустых списков. Для каждого ключа найди его корзину черезbucketIndexи добавь ключ в этот список. Внутри каждой корзины ключи идут в том же порядке, что и на входе. Верни список корзин.
Готово, когда проходят все тесты:
bucketIndex:
("cat", 3)->0("dog", 3)->2("anything", 1)->0(одна корзина, всё попадает в0)("", 5)->0(у пустого ключа сумма0)("ab", 4)->3и("ba", 4)->3(те же буквы, та же корзина)
distribute:
(["cat","dog","bird"], 3)->[["cat","bird"], [], ["dog"]](["ab","ba"], 4)->[[], [], [], ["ab","ba"]](коллизия: два ключа в одной корзине)(["a","b","c"], 1)->[["a","b","c"]]([], 3)->[[], [], []](пустой список, не должно падать)
Практика
bucketIndex / distribute
export function bucketIndex(key, numBuckets) {
// Your code here. The task is described in the box above the editor.
}
export function distribute(keys, numBuckets) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.