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


 

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

12157. ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ 61.5 KB
  ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ Типы полей реляционной базы данных Проектирование приложения работающего с базами данных предполагает наличие самих баз данных. Вместе с BDE в Delphi поставляется программа Database Desktop которая позволяет создавать таблицы ба...
12158. ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ 182.07 KB
  ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ База данных Всегда когда возникает потребность манипулирования большими массивами данных используются базы данных. В общем случае под данными понимается информация наход...
12159. ПОСТРОЕНИЕ ЗАПРОСОВ В DELPHI 36 KB
  ПОСТРОЕНИЕ ЗАПРОСОВ В DELPHI Запрос это вопрос к базе данных возвращающий запись или множество записей удовлетворяющих вопросу. Любой запрос по базе данных выполняется на языке SQL Structured Query Language язык структурированных запросов который был создан Microsoft в конце 70х год...
12160. Режимы design-time и run-time. Объектные процедурные типы. Работа с ini файлами 148.5 KB
  Лабораторная работа №1 Тема: Режимы designtime и runtime. Объектные процедурные типы. Работа с iniфайлами Цель работы: показать простоту создания приложений в режиме designtime и удобство использования компонентов; показать возможность создания приложений с настраиваемым интер...
12161. Классы для представления потока данных 43 KB
  Классы для представления потока данных В среде Delphi существует иерархия классов для хранения и последовательного вводавывода данных. Классы этой иерархии называются потоками. Потоки лучше всего представлять как файлы. Классы потоков обеспечивают различное физическое ...
12162. КОМПОНЕНТЫ TCHART, TPAINTBOX. РАБОТА С ГРАФИКОЙ 25.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №4 Компоненты TChart TPaintBox. работа с Графикой Цель: овладеть навыками анимации построение графиков функций. Замечание: Графики функций необходимо вывести в отдельных окнах в двух вариантах а именно: используя компонент для отображения г
12163. ПОТОКИ. СЕРИАЛИЗАЦИЯ. КОМПОНЕНТ TREEVIEW 21 KB
  ЛАБОРАТОРНАЯ РАБОТА №5 Потоки. Сериализация. Компонент TreeView Цель: научиться эффективно использовать потоки; освоить сериализацию; использование контейнеров; компонент TreeView. Вариант 1. Дерево просмотра каталогов и файлов Вариант 2. Дерево манипуляции с каталог
12164. ДИНАМИЧЕСКИЕ БИБЛИОТЕКИ 58.5 KB
  ДИНАМИЧЕСКИЕ БИБЛИОТЕКИ Динамические библиотеки DLL Dynamic Link Library играют важную роль в функционировании ОС Windows и прикладных программ. Они представляют собой файлы с откомпилированным исполняемым кодом который используется приложениями и другими DLL. Реализация многи
12165. КЛАССЫ ОБЩЕГО НАЗНАЧЕНИЯ 51 KB
  Классы общего назначения Как показывает практика в большинстве задач приходится использовать однотипные структуры данных: списки массивы множества и т.д. От задачи к задаче изменяются только их элементы а методы работы сохраняются. Например для любого списка нужны п...