Метод хеширования

Линейный поиск прост и позволяет легко выполнять добавление новых элементов к существующей таблице, но работает он довольно медленно. Двоичный поиск и его модификации, будучи быстрыми, могут оперировать только с упорядоченными таблицами. Основной недостаток этого метода, делающий его менее полезным для ассемблеров и компиляторов, заключается в том, что добавление новых элементов представляет собой непростой процесс, часто требующий расхода времени на переупорядочение таблицы. По этой причине для построения и доступа к таблицам символов обычно используется метод хеширования [7].

Для построения хеш-таблицы (часто называемой перемешанной,-или рандомизированной, таблицей) с N входами выбирается функция отображения, преобразующая ключ К в число h из диапазона от 0 до N—\. Идеальная функция отображения преобразовывала бы все встречающиеся ключи в различные числа. Элемент с ключом К помещается в k-ю позицию таблицы. Для поиска элемента применяется та же самая функция отображения и ищется fe-й элемент таблицы.

Проблема заключается в том, что в большинстве случаев для таблицы конечного размера невозможно получить такую функцию отображения, все значения которой для различных встречающихся ключей различны. Поэтому на практике используется следующая процедура.

Если предполагается, что таблица содержит М элементов, ее размер выбирается равным N « 3/2 М. Такое решение дает разумный компромисс между размером таблицы и средней длиной поиска. Функция отображения М(К) выбирается таким образом, чтобы любое число из диапазона от 0 до N — 1 вырабатывалось с приблизительно равной вероятностью для заданного или же возможного набора ключей. Простой способ достижения этой цели заключается в том, что в качестве значения хеш-функции берется остаток от деления на N значения ключа, рассматриваемого как двоичное число. Другие алгоритмы будут приведены в разд. 9.3.2, в котором будут обсуждаться приемы рандомизации. При наличии определенной функции отображения выполняются следующие шаги:
(a) Вычислить k=M(K).
(b) Если позиция k в таблице пуста или содержит элемент с ключом К, разместить в ней новый элемент или выдать информацию.
(с). Если не выполнено ни одно из условий (Ь), установить k= =fe+p(mod N), где р и N взаимно-простые числа, и вернуться к шагу (Ь).

Этот метод называется методом открытого хеширования. Из-за своей простоты и эффективности он очень часто используется в ассемблерах. Цикл (Ь) — (с) гарантирует, что если число элементов не больше, чем размер таблицы (максимально допустимое число входов), то для каждого элемента рано или поздно место будет найдено; или же, если ищется заданный ключ, ни один элемент не будет пропущен.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Метод хеширования Линейный поиск прост и позволяет легко выполнять добавление новых элементов к существующей таблице, но работает он довольно медленно. Двоичный поиск и его модификации, будучи быстрыми, могут оперировать только с упорядоченными таблицами. Основной недостаток этого метода, делающий его менее полезным для ассемблеров и компиляторов, заключается в том, что добавление новых элементов представляет собой непростой процесс, часто требующий расхода времени на переупорядочение таблицы. По этой причине для построения и доступа к таблицам символов обычно используется метод хеширования [7]. Для построения хеш-таблицы (часто называемой перемешанной,-или рандомизированной, таблицей) с N входами выбирается функция отображения, преобразующая ключ К в число h из диапазона от 0 до N—\. Идеальная функция отображения преобразовывала бы все встречающиеся ключи в различные числа. Элемент с ключом К помещается в k-ю позицию таблицы. Для поиска элемента применяется та же самая функция отображения и ищется fe-й элемент таблицы. Проблема заключается в том, что в большинстве случаев для таблицы конечного размера невозможно получить такую функцию отображения, все значения которой для различных встречающихся ключей различны. Поэтому на практике используется следующая процедура. Если предполагается, что таблица содержит М элементов, ее размер выбирается равным N « 3/2 М. Такое решение дает разумный компромисс между размером таблицы и средней длиной поиска. Функция отображения М(К) выбирается таким образом, чтобы любое число из диапазона от 0 до N — 1 вырабатывалось с приблизительно равной вероятностью для заданного или же возможного набора ключей. Простой способ достижения этой цели заключается в том, что в качестве значения хеш-функции берется остаток от деления на N значения ключа, рассматриваемого как двоичное число. Другие алгоритмы будут приведены в разд. 9.3.2, в котором будут обсуждаться приемы рандомизации. При наличии определенной функции отображения выполняются следующие шаги: (a) Вычислить k=M(K). (b) Если позиция k в таблице пуста или содержит элемент с ключом К, разместить в ней новый элемент или выдать информацию. (с). Если не выполнено ни одно из условий (Ь), установить k= =fe+p(mod N), где р и N взаимно-простые числа, и вернуться к шагу (Ь). Этот метод называется методом открытого хеширования. Из-за своей простоты и эффективности он очень часто используется в ассемблерах. Цикл (Ь) — (с) гарантирует, что если число элементов не больше, чем размер таблицы (максимально допустимое число входов), то для каждого элемента рано или поздно место будет найдено; или же, если ищется заданный ключ, ни один элемент не будет пропущен.