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

Презентация:



Advertisements
Похожие презентации
Цикл со счетчиком. Ц ИКЛ СО СЧЕТЧИКОМ FOR управляющая переменная:= a TO n DO операторы;(если an) Здесь a – начальное значение управляющей переменной;
Advertisements

Функции. Функция- это подпрограмма, которая вычисляет и возвращает некоторое значение. Функции описываются в разделе описаний следующим образом: Function.
1 Циклические алгоритмы Цикл for. Циклический алгоритм-это многократное повторение одних и тех же действий при различных параметрах Примеры циклических.
Двумерные массивы Решение задач из сборника «Задачи по программированию» под редакцией С. Окулова.
Работа с массивами Программирование в ЕГЭ. Что надо знать о массивах? Матрица – двумерный массив. Элементы массива могут иметь любой тип. Массив определяют.
Перестановка элементов массива Перестановка для одного и двух массивов.
3. Дана прямоугольная матрица, элементами которой являются целые числа. Поменять местами ее строки следующим образом: первую строку с последней, вторую.
FOR Когда известно число повторений удобно использовать инструкцию FOR. Например, таблица умножения или вычисление значений функции в нескольких различных.
Учитель информатики "СОШ 6" г. Кирова Захарова Е.В. ЦИКЛЫ В ПАСКАЛЕ.
Организация повторений в Паскале. i,1,n Действие 1 Действие 2 i,1,n Действие 1 Действие 2 FOR i:=1 TO N DO BEGIN действие 1; действие 2; END; FOR i:=1.
Массивы Вариант 1 Program upr1; Var s,a:real; I: integer; Begin S:=0; For I:=1 to 10 do Begin Writeln (введите очередное число'); Readln(a); S: =s+a; End;
1 Массивы Массив – это упорядоченная последовательность, состоящая из фиксированного количества величин одного типа. Особенности: все элементы имеют один.
Массивы Материалы к урокам по программированию. МАССИВ это УПОРЯДОЧЕННАЯ последовательность данных ОДНОГО ТИПА. Массивы относятся к структурированным.
Множества. Множество- ограниченный, неупорядоченный набор различных элементов одного типа. Примеры множеств: Множество арабских цифр. Множество знаков.
Шутилина Л.А., A[1,1]A[1,2]A[1,3]A[1,4]A[1,5] A[2,1]A[2,2]A[2,3]A[2,4]A[2,5] A[3,1]A[3,2]A[3,3]A[3,4]A[3,5] A[4,1]A[4,2]A[4,3]A[4,4]A[4,5]
Организация повторений в Паскале. Найди ошибки: Program new Uses crt; Var a, b, c integer Begin clrscr Readln(a,b); C:=a*a+b*b Wreteln(c); End.
Массивы – структурированный тип данных, состоящий из фиксированного числа элементов одинакового типа, имеющих общее имя. Массив.
Pascal Алгоритмы циклической структуры, программирование на языке Pascal 9 класс.
Обработка массивов ГБОУ СОШ При назначении размера массива необходимо проанализировать возможный объем данных и ввести возможное количество.
Программирование Задания В2, В5. Оператор присваивания в языке программирования Задание В2 – базовый уровень, время – 2 мин.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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