«Хорошая» хеш-функция распределяет вычисляемые индексы элементов в таблице равномерно по всей таблице, чтобы уменьшить количество возникающих коллизий.
Код 1-го символа имени не дает хороших результатов т.к. все имена, начинающиеся на одну букву, ссылаются на 1 и тот же элемент таблицы. Лучший результат дает использование в качестве хеш-функции кода последнего символа имени.
В трансляторах хеш-функция является более сложной и зависит как от кодов внутреннего представления символов имени, так и от его длины.
Обобщенный алгоритм вычисления хеш-функции включает 2 шага:
Выполняется, если исходное имя s имеет длину более 1 машинного слова. 1 шаг: из исходного имени s формируется код s’ длиной в одно машинное слово. Этот код получается суммированием всех слов исходного имени сложением или сложением по модулю 2. (В случае сложения, вместо s’ выбираются младшие разряды результата). 2 шаг: s’ используется для вычисления хеш-функции. Возможны варианты:
- N=2^K Если размер таблицы определяется степенью двойки, то s’* s’ и к средних битов результата выбирается в качестве значений хеш-функции.
- N=2^K , s’ делится на группы разрядов длиной к, эти разряды «+» или складываются по модулю 2 и результат используется в качестве хеш-функции.
Опубликовал Kest
February 19 2010 10:23:58 ·
0 Комментариев ·
9467 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
