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


 

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

69104. Ініціалізація графічного режиму 52 KB
  Відеоадаптер персонального комп’ютера може працювати в одному із двох режимів - текстовому або графічному. У текстовому режимі на екрані дисплея відображаються лише символи. У графічному режимі мінімальним елементом зображення на екрані дисплея є піксел, або графічна точка.
69105. Графічні процедури й функції 80 KB
  Використання інших кольорових відтінків вимагає доволі складної техніки керування кольоровими палітрами, але її розгляд не належить до кола завдань даного підручника. Синтаксис процедур і функцій, що встановлюють кольори ліній і фону, наведено в табл. 5.1. Зазначимо, що установка кольору впливає...
69106. Побудова графіків функцій. Претворення координат і об’єктів 63 KB
  Для зображення графіка слід перевести логічні координати його точок у їх екранні еквіваленти. 3 урахуванням того що центр логічної системи координат збігається із центром екрана а також того що напрям екранної вісі ординат є зворотним до напряму логічної вісі ординат отримаемо таку формулу...
69107. Анімаційні ефекти 46.5 KB
  Найпростіший спосіб реалізації цього ефекту полягає в тому щоб намалювати зображення певним кольором а потім приховати його шляхом повторного малювання в тих самих графічних координатах кольором фону. Наступного разу зображення відтворюється вже в нових координатах.
69108. Фрактальні зображення 49.5 KB
  Залежно від початкових умов функція що описує таку систему перетворень може наблизитися до нескінченності збігтися до певного скінченного числа числового діапазону або нескінченно варіюватися у певному діапазоні. Множина Мандельброта визначається таким рівнянням...
69109. Теорія і методи структурного програмування 143 KB
  Згодом вона поділяється на підпрограми які декомпонуються на підмодулі наступного рівня. Під час низхідного проектування програми на верхніх рівнях абстракції деталі приховують а на нижніх рівнях вони описуються конкретною мовою програмування.
69110. Використання модулів у Borland Pascal 7.0. Структура модуля 55 KB
  Структура модуля. Структура модуля 3. До складу модуля можна включати оголошення констант типів змінних а також оголошення і реалізацію процедур і функцій. Структура модуля Модуль складається із заголовка інтерфейсної реалізаційної й ініціалізаційної частин.
69111. Основні концепції об’єктно-орієнтованої методології програмування. Базові поняття об’єктна-орієнтованого програмування. Класи і об’єкти в мові Pascal 79.5 KB
  Методологія об’єктно-орієнтованого програмування виникла як результат природної еволюції мов структурного програмування. 3 погляду цієї методології програма є сукупністю об’єктів, кожен об’єкт є екземпляром певного класу, а класи утворюють ієрархію успадкування
69112. Одномірні масиви. Поняття масиву та його властивості. Базові операції обробки одновимірних масивів 214.5 KB
  Характерною ознакою простих типів даних є те, що вони атомарні, тобто не містять як складові елементи дані інших типів. Типи даних, що не эадовольняють зазначеній властивості, називаються структурованими. У мові Раsсаl означено такі структуровані типии: масиви, рядки, множини, записи та файли.