Пример хеширования

Для иллюстрации на простом примере работы метода открытого хеширования рассмотрим некий гипотетический ассемблер. Идентификаторы состоят из двух знаков, первый из которых — буква,
Такая начальная ситуация называется прямым попаданием (hit).— Прим.

Ред второй — десятичная цифра. Пусть максимальное число идентификаторов не превышает 7. Поэтому строится хеш-таблица, имеющая 3/2x7^10 входов. Позицию ключа в таблице дает функция отображения k=K<i=M(K), где Kd—десятичная цифра идентификатора. Если символы A3, В5, ХЗ, CI, С4, D9, D4 заносятся в таблицу в указанном порядке, происходит следующее (рис. 5.10).

Для первых двух элементов A3 и В5 получаются хеш-значения 3 и 5. Так как и третий, и пятый входы пусты, оба элемента помещаются в соответствующие позиции таблицы. Для ХЗ вход-3 уже занят элементом A3. Пусть для простоты р=\ (см. шаг (с)). Тогда следующий вход для ХЗ, вход-4, пуст, так что ХЗ помещается в эту позицию. Никаких проблем не возникает с О. Трудности снова появляются для С4, поскольку вход-4 занят ХЗ. Следующий вход также не пуст, так что первое возможное место для С4 находится в позиции 6. Та же самая процедура может быть прослежена и для D9, и D4.

Если в таблице ищется некоторый элемент, выполняется аналогичная процедура. Если ищется элемент D9, для него вычисляется хеш-значение1}, которое равно 9. Элемент D9 находится в позиции 9, поэтому мы достигаем его за один шаг. Для того чтобы получить D4, вычисляется хеш-значение 4, В этой позиции размещен-ХЗ, поэтому выполняется шаг вперед к позиции 5, где хранится В5. Следующая позиция — 6, которая занята элементом С4, и, наконец, на четвертом шаге D4 обнаруживается в позиции 7. Если бы выполнялся поиск Е2 или Е9, проверялись бы соответственно позиции 2 и 9. Первая из них пуста, поэтому сразу обнаруживается, что Е2 в таблице отсутствует. В позиции 9 обнаруживается элемент D9. Выполняется шаг вперед к позиции 9+1 = 0 (mod 10),. которая также пуста. Это означает, что Е9 также отсутствует в таблице.

Последний столбец на рис. 5.10 содержит число шагов, необходимое для поиска элемента после того, как заполнение таблицы закончено. Средняя длина поиска для данного конкретного распределения составляет (1 + 1+2+1+3+4+1)/7 = 13/7 = 1,86. Отсюда видно, что если таблица заполнена на 70%, то, для того чтобы найти произвольный элемент, нам необходимо в среднем менее чем две пробы. При линейном поиске необходимы были бы в среднем 4 пробы, а при двоичном — около 2,9 пробы.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Пример хеширования Для иллюстрации на простом примере работы метода открытого хеширования рассмотрим некий гипотетический ассемблер. Идентификаторы состоят из двух знаков, первый из которых — буква, Такая начальная ситуация называется прямым попаданием (hit).— Прим. Ред второй — десятичная цифра. Пусть максимальное число идентификаторов не превышает 7. Поэтому строится хеш-таблица, имеющая 3/2x7^10 входов. Позицию ключа в таблице дает функция отображения k=K<i=M(K), где Kd—десятичная цифра идентификатора. Если символы A3, В5, ХЗ, CI, С4, D9, D4 заносятся в таблицу в указанном порядке, происходит следующее (рис. 5.10). Для первых двух элементов A3 и В5 получаются хеш-значения 3 и 5. Так как и третий, и пятый входы пусты, оба элемента помещаются в соответствующие позиции таблицы. Для ХЗ вход-3 уже занят элементом A3. Пусть для простоты р=\ (см. шаг (с)). Тогда следующий вход для ХЗ, вход-4, пуст, так что ХЗ помещается в эту позицию. Никаких проблем не возникает с О. Трудности снова появляются для С4, поскольку вход-4 занят ХЗ. Следующий вход также не пуст, так что первое возможное место для С4 находится в позиции 6. Та же самая процедура может быть прослежена и для D9, и D4. Если в таблице ищется некоторый элемент, выполняется аналогичная процедура. Если ищется элемент D9, для него вычисляется хеш-значение1}, которое равно 9. Элемент D9 находится в позиции 9, поэтому мы достигаем его за один шаг. Для того чтобы получить D4, вычисляется хеш-значение 4, В этой позиции размещен-ХЗ, поэтому выполняется шаг вперед к позиции 5, где хранится В5. Следующая позиция — 6, которая занята элементом С4, и, наконец, на четвертом шаге D4 обнаруживается в позиции 7. Если бы выполнялся поиск Е2 или Е9, проверялись бы соответственно позиции 2 и 9. Первая из них пуста, поэтому сразу обнаруживается, что Е2 в таблице отсутствует. В позиции 9 обнаруживается элемент D9. Выполняется шаг вперед к позиции 9+1 = 0 (mod 10),. которая также пуста. Это означает, что Е9 также отсутствует в таблице. Последний столбец на рис. 5.10 содержит число шагов, необходимое для поиска элемента после того, как заполнение таблицы закончено. Средняя длина поиска для данного конкретного распределения составляет (1 + 1+2+1+3+4+1)/7 = 13/7 = 1,86. Отсюда видно, что если таблица заполнена на 70%, то, для того чтобы найти произвольный элемент, нам необходимо в среднем менее чем две пробы. При линейном поиске необходимы были бы в среднем 4 пробы, а при двоичном — около 2,9 пробы.