TwiddleLab / Код / Структуры данных, которые видно
Хеш-таблицы: как словари находят вещи
Что ты узнаешь
- Хеш-функция превращает ключ в число. Это число % размер таблицы выбирает шкафчик.
- Хеш-таблица хранит каждый ключ в его шкафчике, поэтому найти его это прыжок, а не поиск.
- Два ключа в одном шкафчике это коллизия; шкафчик держит короткую цепочку и проверяет её.
- Хороший хеш распределяет ключи равномерно; достаточно большая таблица держит цепочки короткими. Так словарь Python остаётся быстрым.
Как идёт урок
Instagram находит твой аккаунт среди миллиардов за мгновение.
Он не проверяет их по одному. Сначала попробуй так: найди Mia.
А если само имя говорит, какой шкафчик?
Запусти хеш-машину на Mia. Потом набери своё имя латиницей.
% 8 даёт остаток от 0 до 7, ровно по одному на шкафчик. Сумма зависит только от букв, поэтому машина каждый раз даёт один и тот же шкафчик.
Побудь машиной. Положи каждое имя в его шкафчик.
Суммы букв написаны на карточках. % 8 делаешь ты.
Шкафчики плюс хеш: хеш-таблица.
Хеш-функция превращает ключ в число. Это число % размер выбирает шкафчик, его ещё называют корзиной.
Хеш-таблица это шкафчики с ключами (и их значениями) внутри. Найти ключ значит: посчитать хеш, прыгнуть к шкафчику, проверить, что там.
Два ключа в одном шкафчике это коллизия. Здесь шкафчик держит короткую цепочку, как стрелки из прошлого урока. dict в Python тоже хеш-таблица; при коллизии он пробует другой свободный шкафчик вместо цепочки.
Какая хеш-функция лучше?
Попробуй все три на одних и тех же 10 именах. Оставь ту, что распределяет их ровнее всего, потом «Проверить».
Длина кладёт каждое имя из 3 букв в один шкафчик, а первая буква сводит вместе Mia, Max и Milo. Сумма меняется при изменении любой буквы, поэтому распределяет имена ровнее. Настоящие хеш-функции перемешивают биты ещё сильнее.
Сколько шкафчиков нужно 12 именам?
Двигай число шкафчиков. Найди наименьшее, при котором ни одна цепочка не длиннее 2, потом «Проверить».
Когда шкафчиков мало, многим именам приходится делить их. Каждый лишний шкафчик даёт суммам больше места. Словарь Python тихо увеличивает свою таблицу, когда она заполнена примерно на две трети, поэтому цепочки остаются короткими.
Найди Zoe: хеш-таблица против простого списка.
Пройди поиск по шагам. Поиск по списку запустится, когда закончишь.
Чат-бот превращает каждое слово в номер токена.
Он ищет слова в такой таблице миллионы раз в секунду. В каком шкафчике лежит «cat»? Нажми на него, потом «Проверить».
cat: 3 + 1 + 20 = 24, а 24 = 3 x 8 + 0. Настоящие языковые модели используют словарь из текста токена в номер токена; внутри это хеш-таблица.
Спринт по шкафчикам.
Пять имён, одно из них твоё. Нажимай на каждый шкафчик как можно быстрее.
Предыдущий урок: Связные списки: цепочки стрелок · Следующий урок: Множества: оно там есть? · Часть курса: Структуры данных, которые видно
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
