Хеширование
| English | Русский |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | хэш-функция |
| key/kiː/ | ключ |
| address/əˈdres/ | адрес |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | детерминистическое |
| collision/kəˈlɪʒn/ | коллизия |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | линейная пробирка |
| chaining/ˈtʃeɪnɪŋ/ | цепочка |
| load factor/ləʊd ˈfæktə/ | коэффициент загрузки |
Найти одну строку в пятидесяти миллионах без просмотра
- Кассир супермаркета сканирует штрихкод, и цена появляется до того, как вы уберете товар. Файл продуктов содержит пятьдесят миллионов строк.
- Ничего не искали. Номер штрихкода прошел через короткое вычисление, которое дало позицию, и компьютер прочтал эту позицию: одно чтение, без сравнений, одинаковое время, whether the file holds fifty rows or fifty million.
- Вычисление — это функция хеширования, и вся идея основана на ней: не храните данные там, где они поместятся, храните их там, куда указывает их собственный ключ.
- Этот урок посвящен алгоритмам хеширования, тому, что происходит, когда два ключа хотят занять один слот, и как выполнять поиск и вставку.
Функция хеширования
- Функция хеширования (или алгоритм хеширования) принимает ключ записи и выдает адрес, по которому запись хранится.
- Хорошая функция быстрая, детерминированная (один и тот же ключ всегда дает один и тот же адрес) и равномерно распределяет ключи по доступным слотам.
- Для $N$ слотов три метода, которые ожидает программа: модуль,
address ← key MOD N; фолдинг (сложение фрагментов): разбить ключ на части, сложить их, затем взятие остатка от деления на $N$; хэш-функция для строк: сложить коды символов, затем взятие остатка от деления на $N$.
Хеш-функция:
Хеш-функция отображает ключ на адрес, обеспечивая почти мгновенный прямой поиск.
Что делает хеш-функцию хорошей? Выберите все подходящие варианты.
Быстрый, детерминированный и равномерно распределённый. Никакий реалистичный хэш-функция полностью избегает коллизий, поэтому каждый дизайн включает стратегию разрешения.
Разбор примера: применение каждого алгоритма
- В файле 10 слотов, пронумерованных от 0 до 9. Куда поместится ключ 4517?
- Модуль: $4517 \bmod 10 = 7$, поэтому слот 7.
- Фолдинг парами: $45 + 17 = 62$, затем $62 \bmod 10 = 2$, поэтому слот 2.
- А ключ "CAB" с помощью хэша строки? $67 + 65 + 66 = 198$, затем $198 \bmod 10 = 8$, значит, в слот 8.
- Покажите арифметику. Балл начисляется за вычисления, а не только за номер слота.
Используя модульное хэширование address ← key MOD N с ключом = 27 и N = 10, какой адрес будет получен?
27 MOD 10 = 7 (остаток от деления 27 на 10).
Таблица имеет 10 ячеек. Используя метод сворачивания парами для ключа 4517 (сложить 45 и 17, затем взятие по модулю 10), в какую ячейку он попадёт?
45 + 17 = 62, а 62 MOD 10 = 2. При использовании обычного модульного хэширования тот же ключ попал бы в ячейку 7.
Коллизии
- Коллизия возникает, когда два различных ключа хешируются в один и тот же адрес. При любом хэше и любом реалистичном файле коллизии неизбежны, поэтому стратегия их разрешения должна быть частью проектирования, а не добавлена позже.
- Линейный пробинг помещает запись в следующий свободный слот, переходя к началу таблицы после её конца. Это просто, но записи образуют кластеры: заполненный участок растет, и каждый новый ключ, попадающий в него, обрабатывается дольше.
- Цепочка делает каждый слот головой связного списка всех записей, которые туда хешировались. Нет кластеризации, но требуется дополнительная память для указателей и короткий проход по списку.
- Рехеширование применяет вторую хэш-функцию для поиска другого слота, лучше распределяя ключи ценой больших вычислений.
Коллизия возникает, когда:
Два ключа, отображающиеся на одну ячейку — это коллизия; она должна быть разрешена методом зондирования, цепочек или повторного хэширования.
Сопоставьте каждую идею разрешения коллизий с тем, что она делает.
Коллизии разрешаются цепочками или зондированием; поддержание низкого коэффициента загрузки обеспечивает поиск близким к O(1).
Поиск и вставка
- Для вставки: хешируйте ключ. Если слот свободен, запишите запись туда. Если нет, следуйте стратегии разрешения: следующий свободный слот для линейного пробинга или начало списка этого слота для цепочки.
- Для поиска: хешируйте ключ и прочитайте этот слот. Если сохраненный ключ совпадает, запись найдена. Если нет, следуйте той же стратегии, пока либо ключи не совпадут, либо пустой слот не докажет отсутствие записи в файле.
- Обе операции используют одну и ту же стратегию. Поиск, останавливающийся при первом несовпадении, пропустил бы все записи, когда-либо перемещенные из-за коллизий.
Разбор примера: отслеживание коллизии
- Таблица из 10 слотов использует
key MOD 10с линейным пробингом. Вставьте 23, 33, 43 в указанном порядке, затем найдите 43. - 23 хешируется в 3; слот 3 свободен, поэтому запись попадает туда. 33 хешируется в 3; слот 3 занят записью 23, поэтому линейный пробинг помещает её в слот 4. 43 хешируется в 3; слоты 3 и 4 заняты, поэтому она попадает в слот 5.
- Поиск 43: хеш 3, чтение слота 3, ключ 23, не совпадает, продолжаем пробинг; слот 4 содержит 33, не совпадает; слот 5 содержит 43, найдено после трех чтений.
- Растущая последовательность из трех элементов — это кластеризация, вызванная линейным пробингом.
Хешируйте каждый ключ непосредственно в корзину
Хеш-функция преобразует ключ в номер корзины, позволяя перейти прямо к записи вместо поиска. Когда два ключа попадают в одну корзину, это коллизия — они образуют цепочку в этой корзине.
При поиске в хэш-таблице запись отсутствует в файле, как только первая прочитанная ячейка содержит другой ключ.
Запись могла быть вытеснена коллизией. Поиск следует той же стратегии разрешения до совпадения или пустой ячейки.
Коэффициент загрузки
- Коэффициент загрузки — это количество записей, деленное на количество слотов. Это единственное число, предсказывающее производительность таблицы.
- Ниже примерно 70% среднее время поиска близко к одному чтению. Выше этого значения последовательности пробинга резко удлиняются, а производительность падает до уровня линейного поиска.
- Решение — увеличить таблицу и рехешировать каждую запись в неё, поэтому размер хэш-таблицы определяется данными, которые она будет хранить, а не теми, что есть сегодня.
Таблица из 10 ячеек использует ключ MOD 10 с линейным зондированием. После последовательной вставки 23, 33 и 43, какая ячейка содержит 43?
Все три ключа хэшируются в 3. 23 занимает ячейку 3, 33 перемещается (зондируется) в 4, а 43 — в 5. Три последовательных ключа — это именно то скопление (кластеризация), которое вызывает линейное зондирование.
Потерянные баллы
- Коллизия — это два ключа, один адрес. Это не ошибка и не потерянная запись; это нормальный случай, который обрабатывается стратегией.
- Поиск должен следовать той же стратегии разрешения, что и вставка, и прекращаться только при совпадении или遇到 пустого слота.
- Линейный пробинг вызывает кластеризацию; цепочка требует дополнительной памяти. Укажите компромисс, а не просто механизм.
- Коэффициент загрузки — количество записей, деленное на количество слотов, а порог составляет около 70%, а не 100%.
Для поддержания быстрого поиска в хэш-таблице коэффициент загрузки (записи ÷ ячейки) следует держать:
Более низкий коэффициент загрузки означает меньше коллизий, поэтому поиск остаётся близким к O(1).
Вы поняли
- хэш-функция преобразует ключ в адрес: быстро, детерминированно, равномерно распределяет; modulo, folding и string hashes — три метода, которые нужно знать
- коллизия — два ключа хешируются в один адрес, разрешается линейным пробингом (следующий свободный слот, кластеры), цепочкой (связный список для каждого слота, больше памяти) или рехешированием
- вставка и поиск следуют одной стратегии; поиск завершается при совпадении или遇到 пустого слота
- держите коэффициент загрузки, количество записей, деленное на количество слотов, ниже примерно 70% для поиска за одно чтение