АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Хеширование данных

Читайте также:
  1. Access. Базы данных. Определение ключей и составление запросов.
  2. Decide which answer А, В, С or D best fits each space. Подумайте, какие из предложенных ответов лучше подходят для данных выражений.
  3. Decide which answer А, В, С or D best fits each space. Подумайте, какие из предложенных ответов лучше подходят для данных выражений.
  4. I. Разработка структуры базы данных.
  5. III. Векторное произведение векторов, заданных координатами
  6. Абстрактные структуры данных
  7. Автоматизированная система обработки данных правовой статистики
  8. Авторское право - правовое положение авторов и созданных их творческим трудом произведений литературы, науки и искусства.
  9. Алгоритм шифрования данных IDEA
  10. Американский стандарт шифрования данных DES
  11. Анализ данных при исследовании систем управления
  12. Анализ матричных данных (матрица приоритетов)

Для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей.

При этом могут быть использованы методы поиска в упорядоченных структурах данных, например, метод половинного деления, что существенно сокращает время поиска данных по значению ключа. Однако при добавлении новой записи требуется переупорядочить таблицу. Потери времени на повторное упорядочивание таблицы могут значительно превышать выигрыш от сокращения времени поиска. Поэтому для сокращения времени доступа к данным в таблицах используется так называемое случайное упорядочивание или хеширование. При этом данные организуются в виде таблицы при помощи хеш-функции h, используемой для ⌠вычисления■ адреса по значению ключа.

Рис.3.1. Хеш-таблица

Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса.

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

Рассмотрим пример реализации несовершенной хеш-функции на языке TurboPascal. Предположим, что ключ состоит из четырех символов. При этом таблица имеет диапазон адресов от 0 до 10000.

function hash (key : string[4]): integer;

var

f: longint;

begin

f:=ord (key[1]) - ord (key[2]) + ord (key[3]) -ord (key[4]);

{вычисление функции по значению ключа}

f:=f+255*2;

{совмещение начала области значений функции с начальным

адресом хеш-таблицы (a=1)}

f:=(f*10000) div (255*4);

{совмещение конца области значений функции с конечным адресом

хеш-таблицы (a=10 000)}

hash:=f

end;

При заполнении таблицы возникают ситуации, когда для двух неодинаковых ключей функция вычисляет один и тот же адрес. Данный случай носит название ⌠коллизия■, а такие ключи называются ⌠ключи-синонимы■.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |


При использовании материала, поставите ссылку на Студалл.Орг (0.005 сек.)