29365

Методы вычисления хеш-функции

Доклад

Информатика, кибернетика и программирование

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

Английский

2013-08-21

24 KB

3 чел.

33) Методы вычисления хеш-функции.

«Хорошая» хеш-функция распределяет вычисляемые индексы элементов в таблице равномерно по всей таблице, чтобы уменьшить количество возникающих коллизий. 
Код 1-го символа имени не дает хороших результатов т.к. все имена, начинающиеся на одну букву, ссылаются на 1 и тот же элемент таблицы. Лучший результат дает использование в качестве 
хеш-функции кода последнего символа имени.
В трансляторах 
хеш-функция является более сложной и зависит как от кодов внутреннего представления символов имени, так и от его длины.
Обобщенный алгоритм вычисления 
хеш-функции включает 2 шага:
Выполняется, если исходное имя s имеет длину более 1 машинного слова.
1 шаг: из исходного имени s формируется код s’ длиной в одно машинное слово. Этот код получается суммированием всех слов исходного имени сложением или сложением по модулю 2. (В случае сложения, вместо s’ выбираются младшие разряды результата).
2 шаг: s’ используется для вычисления хеш-функции. Возможны варианты:
- N=2^K Если размер таблицы определяется степенью двойки, то s’* s’ и к средних битов результата выбирается в качестве значений хеш-функции.
- N=2^K , s’ делится на группы разрядов длиной к, эти разряды «+» или складываются по модулю 2 и результат используется в качестве 
хеш-функции.


 

А также другие работы, которые могут Вас заинтересовать

62973. Вплив шкідливих звичок на організм людини 19.72 KB
  Мета: Навчальна: запобігати шкідливим звичкам які негативно впливають на здоровя підлітків; Виховна: формувати вміння і навички учнів щодо власної безпеки розуміння відповідальності за власні вчинки та їх наслідки...
62976. Решение биквадратного уравнения в EXCEL 76 KB
  Здесь предусмотрены все пять случаев, которые могут встретиться при решении биквадратного уравнения, изложенных подробно в разделе: Алгоритм решения биквадратного уравнения. На рисунке выше коэффициенты указанных уравнений введены в таблицу Excel.
62979. Будова та різноманітність квіток 779.99 KB
  Мета: поглибити знання учнів про генеративні органи рослини; сформувати поняття про квітку як основний генеративний орган вивчити будову квітки їх різноманітність біологічне значення; формувати вміння розпізнавані квітки одностатеві й двостатеві...
62980. Використання інформаційно-комунікаційних технологій у викладанні географії 23.5 KB
  Одним із напрямів модернізації системи географічної освіти у школі є впровадження компютерних технологій у навчальний процес. Сучасне життя вимагає від учителів освоєння компютерної техніки тому що багатьом учням які вже достатньою...