 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Хеш–функция
|
Читайте также: |
Как уже отмечалось, выбор хеш–функции очень сильно влияет на эффективность рассматриваемых методов организации таблиц. Обычно, если слово S, являющееся аргументом хеширования, занимает более одного машинного слова, то на первом шаге хеширования по S формируется одно машинное слово S /. Как правило, S / вычисляется суммированием всех слов из S при помощи поразрядного сложения по модулю 2 (то есть при помощи операция XOR – исключающее или).
На втором шаге из S / вычисляется окончательный индекс, причем это можно сделать несколькими способами:
1. Умножить S / само на себя и использовать n средних битов в качестве значения функции хеширования (если таблица имеет 2n элементов). Поскольку n средних битов зависит от каждого бита S /, этот метод дает очень хорошие результаты.
2. Использовать какую–либо логическую операцию, например тот же XOR, над некоторыми частями S /.
3. Если в таблице имеется 2n элементов, расщепить S / на n частей и просуммировать их. Использовать n правых крайних битов результата.
4. Разделить S / на длину таблицы и остаток использовать в качестве хеш–индекса.
Все эти методы применялись и давали удовлетворительные результаты. Можно предложить и другие методы. Нужно только быть уверенным, что на множестве аргументов, к которому будет применяться функция хеширования, она даст достаточно случайные адреса. Это легко проверить, формируя таким образом таблицу терминалов (ключевых, зарезервированных слов языка). В принципе, выделение ключевых слов в отдельную таблицу вовсе необязательно. Их можно поместить в общую таблицу идентификаторов при начальной загрузке компилятора, снабдив соответствующим признаком. Стоит проверить эту первоначальную таблицу на число возникших коллизий. Хеш–функция может быть достаточно хорошей с точки зрения статистики, но может как раз случиться, что 20 зарезервированных слов ссылается на один и тот же адрес.
Например, в компилятора PL/1 F фирмы IBM, реализованного в начале 70–х годов, использовалось следующая хеш–функция:
1. Суммировались последовательные части идентификатора, содержащие по 4 символа, в один 4–байтовый регистр.
2. Результат делился на 211 и определялся остаток R.
3. Значение 2*R использовалось в качестве индекса для ссылки на таблицу из 211 указателей (каждый указателей имеет длину 2 байта).
В этом компиляторе для разрешения коллизии использовался не метод рехеширования, а метод цепочек (гроздей), который, конечно же, предпочтительнее в системах с динамическим распределением памяти.
Поиск по сайту: