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 и результат используется в качестве 
хеш-функции.


 

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

14720. Визначення втрат тепла через систему охолодження автомобільного двигуна 405.5 KB
  Лабораторна робота № 4 Визначення втрат тепла через систему охолодження автомобільного двигуна Мета роботи: Вивчення теплового балансу двигуна і практичне визначення втрат тепла через систему охолодження автомобільного двигуна. Обладнання: Двигун ЗІЛ 130 ...
14721. Алгоритм анализа качества системы при детерминированных и случайных воздействиях 80.51 KB
  Алгоритм анализа качества системы при детерминированных и случайных воздействиях Задача анализу известной динамической системы в конкретных условиях ее эксплуатации состоит в определении выходных реакций и сигналов управления систем при определенных входных сигнал...
14722. Таблицы решений 128 KB
  Лабораторная работа № 3. Таблицы решений Цель работы Целью работы является изучение таблиц решений и спецификация с помощью данного механизма логики вычислительных процессов. Содержание отчета Итоговым документом выполнения лабораторной работы является отчет с
14723. Flow-формы и диаграммы Насси-Шнейдермана 44 KB
  Лабораторная работа № 2. Flowформы и диаграммы НассиШнейдермана Цель работы Изучение и практическое применение принципов разработки спецификаций вычислительных процессов с помощью визуальных языков Flowформ и диаграмм НассиШнейдермана. Содержание отчета Итоговы
14724. Схемы алгоритмов 76 KB
  Контрольная работа. Схемы алгоритмов Цель работы Целью работы является практическое изучение процесса спецификации алгоритмов с помощью схем. Содержание отчета Итоговым документом выполнения контрольной работы является отчет состоящий из следующих пунктов. ...
14725. Определение ускорения свободного падения с помощью оборотного маятника 48 KB
  отчёт по лабораторной работе № 20 Определение ускорения свободного падения с помощью оборотного маятника Расчетная формула. 4πL₀ T где L₀ приведенная длина оборотного маятника; T период колебаний маятника. Эскиз установки. ...
14726. Анализ дискретной математической модели непрерывного динамического объекта 463.34 KB
  Лабораторная работа №4 Анализ дискретной математической модели непрерывного динамического объекта Цели работы: выполнить анализ заданного непрерывного объекта; выбрать несколько периодов квантования объекта; получить дискретные ММ непрерывного объект
14727. Синтез и исследование динамических наблюдателей состояния линейных объектов управления 224.99 KB
  4 Лабораторная работа №3 Синтез и исследование динамических наблюдателей состояния линейных объектов управления Цель работы: ознакомление с современными методами наблюдения состояния технических объектов в системах управления синтеза соответству...
14728. Исследование эквивалентных преобразований математических моделей динамических систем в пространстве состояний 36.36 KB
  4 Лабораторная работа №2 Исследование эквивалентных преобразований математических моделей динамических систем в пространстве состояний Цели работы: исследовать управляемость и наблюдаемость системы; привести ММ управляемой ДС к основной норм