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

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

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

3 Хеширование данных Function H (x: string[10]): 0..n-1; var I, sum: integer; begin sum:= 0; for I:=1 to 10 do sum := sum + ord ( x[I] ); h :=sum mod n end;

4 Хеширование данных Пример реализации несовершенной хеш-функции: Предположим ключ состоит из четырех символов; таблица имеет диапазон адресов от 0 до

5 Хеширование данных 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)}

6 Хеширование данных {совмещение начала области значений функции с начальным адресом хеш-таблицы (a=1)} f:=(f*10000) div (255*4); {совмещение конца области значений функции с конечным адресом хеш-таблицы (a=10 000)} hash:=f end;

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

8 Разрешение коллизий: метод цепочек

9 Разрешение коллизий: линейное опробование

10 Разрешение коллизий: квадратичное опробование

11 Разрешение коллизий: двойное хеширование

12 Линейное опробование: вставка 1. i = 0 2. a = h(key) + i*c 3. Если t(a) = свободно, то t(a) = key, записать элемент, стоп элемент добавлен 4. i = i + 1, перейти к шагу 2

13 Линейное опробование: поиск 1. i = 0 2. a = h(key) + i*c 3. Если t(a) = key, то стоп элемент найден 4. Если t(a) = свободно, то стоп элемент не найден 5. i = i + 1, перейти к шагу 2

14 Оценка качества хеш-функции

15 Инвертированные индексы

16

17 Битовые карты