Хеш-таблицы. Хеш-функции

Содержание

Слайд 2

Введение Задача: Реализовать динамическое множество (key-value storage) со стандартными операциями вставки

Введение

Задача:
Реализовать динамическое множество (key-value storage) со стандартными операциями вставки элемента (Insert),

удаления элемента (Delete), поиск элемента (Search).
Способы реализации :
Массивы – сложность всех операций O(1), т.к. произвольный доступ к элементам.
Связные списки – сложность всех операций O(n) , т.к. последовательный доступ к элементам
хеш-таблицы – сложность всех операций O(1)
вписать элементы в пространство меньшей размерности.
… деревья …

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 3

Таблицы с прямой адресацией Пусть требуется реализовать динамическое множество, где каждый

Таблицы с прямой адресацией

Пусть требуется реализовать динамическое множество, где каждый элемент

имеет ключ из совокупности U = {0, 1, … ,m-1}, при этом m не слишком велико.
Разные элементы имеют разные ключи, т.е. они уникальны.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 4

Таблицы с прямой адресацией Пусть требуется реализовать динамическое множество, где каждый

Таблицы с прямой адресацией

Пусть требуется реализовать динамическое множество, где каждый элемент

имеет ключ из совокупности U = {0, 1, … ,m-1}, при этом m не слишком велико.
Разные элементы имеют разные ключи (идентификаторы), т.е. они уникальны.
Для реализации множества будем использовать таблицу с прямой адресацией:
Таблицу организуем на массиве размера m (m - малое). Обозначим его T[0…m-1].
Никакие два элемента не имеют элементов с двумя одинаковыми ключами.
Каждая ячейка массива соответствует ключу из совокупности, т.е индекс_элемента_массива = ключ_элемента_множества.
Если множество не содержит элемент с ключом k, то T[k]=NULL.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 5

Таблицы с прямой адресацией. Иллюстрация. U – множество всех возможных ключей

Таблицы с прямой адресацией. Иллюстрация.

U – множество всех возможных ключей

Введение
Таблицы с

прямой адресацией
Хеш-таблицы
Коллизии
Слайд 6

Таблицы с прямой адресацией. Иллюстрация. K – множество всех реальных ключей

Таблицы с прямой адресацией. Иллюстрация.

K – множество всех реальных ключей (имеются

объекты с ключами из этого множества)

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 7

Таблицы с прямой адресацией. Иллюстрация. T – таблица с прямой адресацией

Таблицы с прямой адресацией. Иллюстрация.

T – таблица с прямой адресацией (массив)

размера |U|
Таблица может быть заполнена частично.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 8

Таблицы с прямой адресацией. Иллюстрация. Ключи используются для того, чтобы уникально

Таблицы с прямой адресацией. Иллюстрация.

Ключи используются для того,
чтобы уникально определять

каждый объект.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 9

Таблицы с прямой адресацией. Иллюстрация. В i-ой ячейке содержится указатель на

Таблицы с прямой адресацией. Иллюстрация.

В i-ой ячейке содержится указатель на элемент

с ключом i.
Каждый элемент помимо ключа содержит сопутствующую информацию.
Если не существует элемента с ключом j, то T[j] = NULL.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 10

Таблицы с прямой адресацией. Операции. Реализация операций тривиальна. Direct-Address-Search(T,k) // T[]

Таблицы с прямой адресацией. Операции.

Реализация операций тривиальна.
Direct-Address-Search(T,k) // T[] – массив,

k – ключ искомого элемента
return T[k]
Direct-Address-Insert(T,x) // x – вставляемый элемент, x.key – ключ
T[x.key] = x
Direct-Address-Delete(T,x) // x – удаляемый элемент, x.key – ключ
T[x.key] = NIL
Каждая из этих операций выполняется за О(1).

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 11

Таблицы с прямой адресацией. Вариации. Если нет необходимости в дополнительных полях

Таблицы с прямой адресацией. Вариации.

Если нет необходимости в дополнительных полях объектов

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

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Таблица в ячейках содержит
заполненные элементы
пустые элементы
Элемент_массива = объект

Слайд 12

Таблицы с прямой адресацией. Вариации. В объекте можно не хранить информацию

Таблицы с прямой адресацией. Вариации.

В объекте можно не хранить информацию о

значении ключа,
т.к. индекс в таблице = значение ключа.
Но в этом случае нужен специальный механизм для того, чтобы помечать пустые ячейки.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Таблица в ячейках содержит
заполненные элементы
пустые элементы
Элемент_массива = данные_в_объекте

Слайд 13

Таблицы с прямой адресацией. Недостатки. Если совокупность ключей велика, то хранение

Таблицы с прямой адресацией. Недостатки.

Если совокупность ключей велика, то хранение таблицы

T размером |U| непрактично или невозможно.
Кроме того, множество K реально сохраненных ключей может быть мало по сравнению с |U|, то есть |K| << |U|.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 14

Хеш-таблицы Когда используются хеш-таблицы: множество K реально сохраненных ключей мало по

Хеш-таблицы

Когда используются хеш-таблицы:
множество K реально сохраненных ключей мало по сравнению с

|U|.
Требования к памяти - Θ(|K|)
Время поиска элемента – O(1)
Опр. Хеш-функцией называется такая функция h(k), которая отображает совокупность ключей U на ячейки хеш-таблицы T[0…m-1]:
h: U → {0, 1,…, m-1}
где m – размер хеш-таблицы, гораздо меньший значения |U|.
Опр. h(k) называется хеш-значением ключа k.
Цель хеш-функции: уменьшение рабочего диапазона индексов массива.

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 15

Хеш-таблицы. Иллюстрация. Объект с ключом ki сохраняется в таблицу по индексу

Хеш-таблицы. Иллюстрация.

Объект с ключом ki сохраняется в таблицу по индексу h(ki).

Введение
Таблицы

с прямой адресацией
Хеш-таблицы
Коллизии
Слайд 16

Хеш-таблицы. Иллюстрация. Возможна ситуация, когда разным ключам соответствуют одинаковые хеш-значения. Введение

Хеш-таблицы. Иллюстрация.

Возможна ситуация, когда разным ключам соответствуют
одинаковые хеш-значения.

Введение
Таблицы с прямой

адресацией
Хеш-таблицы
Коллизии
Слайд 17

Хеш-таблицы. Коллизии. Опр. Коллизией называется ситуация, когда два ключа имеют одно

Хеш-таблицы. Коллизии.

Опр. Коллизией называется ситуация, когда два ключа имеют одно и

то же хеш-значение, а значит, должны быть сохранены одну ячейку таблицы.
Коллизий нельзя избежать из-за неравенства |U| > m.
|U| - количество всех возможных ключей
m – размер хеш-таблицы
Требования к хорошей хеш-функции:
Минимизировать количество коллизий
Функция обязательно должна быть детерминистической

Введение
Таблицы с прямой адресацией
Хеш-таблицы
Коллизии

Слайд 18

Хеш-таблицы. Коллизии. Методы разрешения коллизий: Метод разрешения с помощью цепочек Метод

Хеш-таблицы. Коллизии.

Методы разрешения коллизий:
Метод разрешения с помощью цепочек
Метод открытой адресации

Введение
Таблицы с

прямой адресацией
Хеш-таблицы
Коллизии
Слайд 19

Особенности использования хэш-функций Найти хэш-функцию, которая минимизирует коллизии Хорошая хэш функция

Особенности использования хэш-функций

Найти хэш-функцию, которая минимизирует коллизии
Хорошая хэш функция должна использовать

всю информацию, которая есть в ключе, чтобы максимизировать количество хэш значений
Хэш значения должны быть равномерно распределены
Распределение независимо от популярности данных
Лучше когда хэш функция создает разные значения для близких значений ключей, это уменьшит коллизии
Хэш-функция должна быть быстрой
Слайд 20

Метод разрешения с помощью цепочек

Метод разрешения с помощью цепочек

Слайд 21

Разрешение коллизий с помощью цепочек Суть метода: все элементы, хешированные в

Разрешение коллизий с помощью цепочек

Суть метода:
все элементы, хешированные в одну и

ту же ячейку, помещаются в связный список.
Ячейка j содержит:
указатель на заголовок списка всех элементов, хеш-значение ключа которых равно j;
ячейка содержит значение NULL, если таких элементов нет.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 22

Разрешение коллизий с помощью цепочек. Иллюстрация Каждая ячейка T[j] хеш-таблицы содержит

Разрешение коллизий с помощью цепочек. Иллюстрация

Каждая ячейка T[j] хеш-таблицы содержит указатель

на связный список всех ключей с хеш-значением j.
Например, h(k1)=h(k4) и h(k5)=h(k7)=h(k2).
Список может быть одно- и двусвязным.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 23

Разрешение коллизий с помощью цепочек. Операции Реализация операций работы с таблицей:

Разрешение коллизий с помощью цепочек. Операции

Реализация операций работы с таблицей:

Суть метода
Операции
Метод

деления
Метод умножения
Универсальное хеширование

Элемент вставляется в начало списка, а не в конец.
Время выполнения – константное.

Слайд 24

Разрешение коллизий с помощью цепочек. Операции Реализация операций работы с таблицей:

Разрешение коллизий с помощью цепочек. Операции

Реализация операций работы с таблицей:

Суть метода
Операции
Метод

деления
Метод умножения
Универсальное хеширование

Определяется нужный список.
Проход по списку
Время выполнения –
зависит от длины списка.

Слайд 25

Разрешение коллизий с помощью цепочек. Операции Реализация операций работы с таблицей:

Разрешение коллизий с помощью цепочек. Операции

Реализация операций работы с таблицей:

Суть метода
Операции
Метод

деления
Метод умножения
Универсальное хеширование

Определяется нужный список.
Проход по списку
Удаляется элемент списка. Переопределяются связи.
Время выполнения –
зависит от длины списка.

Слайд 26

Разрешение коллизий с помощью цепочек Пусть n элементов хранятся в хеш-таблице

Разрешение коллизий с помощью цепочек

Пусть n элементов хранятся в хеш-таблице T

с m ячейками.
Будем вычислять коэффициент заполнения α таблицы T как n/m.
Коэффициент α >0 и может быть:
<1, когда n < m,
=1, когда n = m,
>1, когда n > m.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 27

Разрешение коллизий с помощью цепочек В худшем случае: все n ключей

Разрешение коллизий с помощью цепочек

В худшем случае: все n ключей имеют

одинаковое хеш-значение и попадают в один и тот же список.
Время поиска = Θ(n) (как в связном списке) + время вычисления значения хеш-функции
Вывод: производительность хеширования в среднем случае зависит от того, насколько хорошо хеш-функция распределяет множество ключей по m ячейкам.
Основное предположение:
Пусть все элементы хешируются по ячейкам равномерно и независимо.
Хеширование, удовлетворяющее основному предположению, называется простым равномерным хешированием.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 28

Разрешение коллизий с помощью цепочек Обозначим длины списков T[j] для j=0,1,…,m-1

Разрешение коллизий с помощью цепочек

Обозначим длины списков T[j] для j=0,1,…,m-1 как

nj, так что
n0 + n1 + … + nm-1 = n
А ожидаемое значение nj равно E[nj] = n/m = α.
Утверждение 1:
В хеш-таблице с разрешением коллизий методом цепочек время неудачного поиска (элемент не найден) в среднем случае в предположении простого равномерного хеширования составляет Θ(1+α).
Утверждение 2:
В хеш-таблице с разрешением коллизий методом цепочек время успешного поиска (элемент найден) в среднем случае в предположении простого равномерного хеширования составляет Θ(1+α).

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Доказывается математически

Слайд 29

Разрешение коллизий с помощью цепочек Примечание. Если количество элементов n пропорционально

Разрешение коллизий с помощью цепочек

Примечание.
Если количество элементов n пропорционально количеству ячеек

m в хэш-таблице, то n = O(m) и α = n/m = O(m)/m = O(1).
Операции поиска и удаления элемента выполняются за время O(α ).
Вывод: все операции в среднем случае выполняются за константное время.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 30

Разрешение коллизий с помощью цепочек. Важно Для качественной хеш-функции должно выполняться

Разрешение коллизий с помощью цепочек. Важно

Для качественной хеш-функции должно выполняться предположение

простого равномерного хеширования.
Помещаемые в хеш-таблицу данные могут быть зависимыми (можем этого и не узнать, пока не начнем добавлять объекты в таблицу).
Следовательно, качественная хеш-функция должна минимизировать возможность попадания близких данных в одну ячейку. То есть близкие данные должны быть хорошо «рассеяны».
Прим. Идентификаторы pt и ptr. Хорошая хэш-функция распределит их по «неблизким» ячейкам таблицы.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 31

Разрешение коллизий с помощью цепочек. Строковые ключи Метод преобразования ключей строкового

Разрешение коллизий с помощью цепочек. Строковые ключи

Метод преобразования ключей строкового типа

в числовой:
Пусть есть 2 близких ключа: pt и ptr.
Переведем каждый символ в значение по таблице ASCII
pt = (112,116) и ptr = (112,116,113).
Каждому набору чисел сопоставим единственное число в 128-ричной СС с соответствующими разрядами
pt = (112*128)+116 = 14452
ptr = 112*1282+116*128+113=1849969
Итог: числовые ключи 14452 и 1849969 – не близки.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 32

Разрешение коллизий с помощью цепочек. Методы вычисления хеш-значения по ключу: Метод

Разрешение коллизий с помощью цепочек.

Методы вычисления хеш-значения по ключу:
Метод деления
Метод

умножения
Универсальное хеширование
И т.д.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 33

Хеш-функции. Метод деления. Суть метода: Хеш-значение ключа k определяется как остаток

Хеш-функции. Метод деления.

Суть метода:
Хеш-значение ключа k определяется как остаток от деления

на количество ячеек m в хеш-таблице.
h(k) = k mod m
Пример.
Пусть таблица имеет размер 12, значение ключа = 100, тогда элемента с данным ключом попадет в список с индексом h(100) = 100 mod 12 = 4.
Рекомендации по выбору m:
НЕ должно быть степенью двойки (если m=2p, то h(k) – это младшие p бит числа k). Если только заранее не известно, что все наборы младших р битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа.
Рекомендуют выбирать для m простое число, далекое от степени двойки
Пример. Пусть n=2000, желаемое значение α=3, тогда m=701.
Число 701 выбрано как простое число, близкое к величине 2000/3 и не являющееся степенью 2

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 34

Хеш-функции. Метод умножения. Построение хеш-функции выполняется в 2 этапа: Выбираем константу

Хеш-функции. Метод умножения.

Построение хеш-функции выполняется в 2 этапа:
Выбираем константу 0 <

A < 1. Умножаем ключ k на константу A и выделяем дробную часть результата умножения.
Полученное в п.1 число умножаем на m и к результату применяем функция округление снизу.
Прим. Выражение “kA mod 1” означает получение дробной части произведения kA.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 35

Хеш-функции. Метод умножения. Рекомендация для технической оптимизации: m перестает быть критичным

Хеш-функции. Метод умножения.

Рекомендация для технической оптимизации:
m перестает быть критичным
обычно m

выбирается равной степени 2 (m=2p для некоторого натурального p)
константа A выбирается как дробь вида s/2w, где s – целое число из диапазона 0Пусть размер машинного слова составляет w бит и число k помещается в одно слово.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 36

Хеш-функции. Метод умножения. Вычисление функции h(k): Умножаем k на w–битовое целое

Хеш-функции. Метод умножения.

Вычисление функции h(k):
Умножаем k на w–битовое целое число s=A*2w
Результат

умножения – 2w-битовое число r12w+r0, где r1 – старшее слово произведения, а r0 – младшее.
Старшие p бит числа r0 представляют собой искомое p–битовое хеш-значение.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 37

Хеш-функции. Метод умножения. Вычисление функции h(k): Умножаем k на w–битовое целое

Хеш-функции. Метод умножения.

Вычисление функции h(k):
Умножаем k на w–битовое целое число s=A*2w
Результат

умножения – 2w-битовое число r12w+r0, где r1 – старшее слово произведения, а r0 – младшее.
Старшие p бит числа r0 представляют собой искомое p–битовое хеш-значение.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 38

Хеш-функции. Метод умножения. Вычисление функции h(k): Умножаем k на w–битовое целое

Хеш-функции. Метод умножения.

Вычисление функции h(k):
Умножаем k на w–битовое целое число s=A*2w
Результат

умножения – 2w-битовое число r12w+r0, где r1 – старшее слово произведения, а r0 – младшее.
Старшие p бит числа r0 представляют собой искомое p–битовое хеш-значение.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 39

Хеш-функции. Метод умножения. Вычисление функции h(k): Умножаем k на w–битовое целое

Хеш-функции. Метод умножения.

Вычисление функции h(k):
Умножаем k на w–битовое целое число s=A*2w
Результат

умножения – 2w-битовое число r12w+r0, где r1 – старшее слово произведения, а r0 – младшее.
Старшие p бит числа r0 представляют собой искомое p–битовое хеш-значение.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 40

Метод умножения. Пример. Кнут в своей книге рекомендует в качестве константы

Метод умножения. Пример.

Кнут в своей книге рекомендует в качестве константы
Пример.
Пусть k

= 123456, p = 14, m = 214 = 16384 и w = 32.
Тогда представим A как дробь 2654435769/232, где s = 2654435769. Такая дробь будет очень близка к предлагаемому Кнутом значению A.
Тогда k*s = 327706022297664 = (76300*232) + 17612864, т.е.
r1 = 76300, r0 = 17612864,
а старшие 14 бит числа r0 дают h(k) = 67

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 41

Хеш-функции. Универсальное хеширование. Предположим есть недоброжелатель, знающий, какая именно хеш-функция используется

Хеш-функции. Универсальное хеширование.

Предположим есть недоброжелатель, знающий, какая именно хеш-функция используется и

умышленно выбирающий ключи так, чтобы все n вставляемых значений попали в одну ячейку таблицы.
Тогда время поиска и удаления элемента будет Θ(n).
Вывод: хеш-функция должна выбираться случайно для каждой хеш-таблицы и не должна зависеть от набора ключей, с которыми работает.
Такой подход называется универсальным хешированием и гарантирует в среднем хорошую производительность.
Хеш-функция выбирается из некоторого, заранее определенно класса функций. В силу рандомизации выбора хеш-функции, результаты работы на одних и тех же данных всегда будут разными, что гарантирует отсутствие «всегда плохих» данных.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 42

Пример универсального хеширования. Простой пример класса хеш-функций для универсального хеширования: Выберем

Пример универсального хеширования.

Простой пример класса хеш-функций для универсального хеширования:
Выберем простое число

p достаточно большое, чтобы все возможные ключи находились в диапазоне от 0 до p-1 включительно. Следовательно, p>m.
Обозначим через Zp множество {0,1,2,…,p-1}, а через Zp*– множество {1,2,…,p-1}.
Определим хеш-функцию hab для любых a∈ Zp* и b∈ Zp, используя линейное преобразование с последующими приведениями по модулю.
hab(k) = ((ak+b) mod p) mod m
Пример: пусть p=17 и m=6, тогда h34(8)=5.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 43

Пример универсального хеширования. Получили семейство хеш-функций Hpm={hab: a∈ Zp* и b∈

Пример универсального хеширования.

Получили семейство хеш-функций Hpm={hab: a∈ Zp* и b∈ Zp}.
Причем

размер m выходного диапазона произволен и не обязан быть простым числом.
Поскольку число a можно выбрать p-1 способом, а число b - p способами, то всего в семействе Hpm содержится p(p-1) хеш-функций.

Суть метода
Операции
Метод деления
Метод умножения
Универсальное хеширование

Слайд 44

Метод открытой адресации

Метод открытой адресации

Слайд 45

Хэш-функции. Метод открытой адресации Суть метода: В ячейке хеш-таблицы хранится либо

Хэш-функции. Метод открытой адресации

Суть метода:
В ячейке хеш-таблицы хранится либо элемент динамического

множества, либо NULL
Поиск элемента – проход по хэш-таблице (по определенному алгоритму) пока не найдем, либо пока не убедимся, что элемента нет
Количество вставляемых в таблицу элементов ограничивается её размером
Коэффициент заполнения α ≤ 1
Прим. Отказ от указателей позволяет увеличить объем хэш-таблицы

Суть метода
Методы исследования

Слайд 46

Метод открытой адресации. Исследование таблицы Поиск элемента в таблице – это

Метод открытой адресации. Исследование таблицы

Поиск элемента в таблице – это исследование

ячеек в определенной последовательности.
Если просматривать ячейки в прямой порядке 0,…,m-1, то времени требуется Θ(n).
Вывод: требуется определенный алгоритм просмотра хэш-таблицы. Можно совершить не более, чем m исследований. При этом номер исследования становится вторым аргументом хэш-функции.
Хэш-функция имеет вид

Суть метода
Методы исследования

Ключ Номер исследования Хеш-значение ключа

Слайд 47

Хэш-функции. Метод открытой адресации Последовательность исследований для каждого ключа k есть

Хэш-функции. Метод открытой адресации

Последовательность исследований для каждого ключа k
есть перестановка на

множестве {0,1,…,m-1} .
Реализация функции вставки:

Суть метода
Методы исследования

Вычисляем хеш-значение ключа с учетом номера исследования

Слайд 48

Хэш-функции. Метод открытой адресации Последовательность исследований для каждого ключа k есть

Хэш-функции. Метод открытой адресации

Последовательность исследований для каждого ключа k
есть перестановка на

множестве {0,1,…,m-1} .
Реализация функции вставки:

Суть метода
Методы исследования

- Индекс проверяемой ячейки совпадает с хеш-значением.
- Если найденная ячейка пуста, то в нее помещаем объект с ключом k

Слайд 49

Хэш-функции. Метод открытой адресации Последовательность исследований для каждого ключа k есть

Хэш-функции. Метод открытой адресации

Последовательность исследований для каждого ключа k
есть перестановка на

множестве {0,1,…,m-1} .
Реализация функции вставки:

Суть метода
Методы исследования

Если найденная ячейка не пуста, то увеличиваем счетчик и производим следующее исследование

Слайд 50

Хэш-функции. Метод открытой адресации Последовательность исследований для каждого ключа k есть

Хэш-функции. Метод открытой адресации

Последовательность исследований для каждого ключа k
есть перестановка на

множестве {0,1,…,m-1} .
Реализация функции вставки:

Суть метода
Методы исследования

Если не найдено ни одной пустой ячейки

Слайд 51

Хэш-функции. Метод открытой адресации Реализация функции поиска: Прим. Не забываем предположение

Хэш-функции. Метод открытой адресации

Реализация функции поиска:
Прим. Не забываем предположение о равномерном

хешировании: для каждого ключа должны быть равновероятны все m! перестановок множества {0,1,…,m-1}.

Суть метода
Методы исследования

В ходе i–ой пробы в j–ой ячейке таблицы нашли объект с ключом k

Слайд 52

Хэш-функции. Метод открытой адресации Реализация функции поиска: Прим. Не забываем предположение

Хэш-функции. Метод открытой адресации

Реализация функции поиска:
Прим. Не забываем предположение о равномерном

хешировании: для каждого ключа должны быть равновероятны все m! перестановок множества {0,1,…,m-1}.

Суть метода
Методы исследования

Неблагоприятные исходы:
Дошли до пустой ячейки, но на предыдущих пробах не нашли искомый элемент
Прошли по всей таблице

Слайд 53

Метод открытой адресации. Линейное исследование. Используется вспомогательная хэш-функция h`: U →

Метод открытой адресации. Линейное исследование.

Используется вспомогательная хэш-функция h`: U → {0,1,…,m-1}
Для

вычисления последовательности исследований используется хэш-функция
где i = 0,1,…,m-1
В результате использований хэш-функции исследуются ячейки
T[h`(k)], T[h`(k)+1], …, T[m-1], T[0], T[1], …, T[h`(k)-1]

Суть метода
Методы исследования

Слайд 54

Метод открытой адресации. Линейное исследование. Проблема метода: первичная кластеризация. Пример: добавим

Метод открытой адресации. Линейное исследование.

Проблема метода: первичная кластеризация.
Пример: добавим в хеш-таблицу

размера m=10 с использованием хеш-функции h(k)=k mod m элементы с ключами 5,15,25.

Суть метода
Методы исследования

Добавляем 15:
Проба 1 – ячейка 5
Проба 2 – ячейка 6

Добавляем 5:
Проба 1 – ячейка 5

Добавляем 25:
Проба 1 – ячейка 5
Проба 2 – ячейка 6
Проба 3 – ячейка 7

Слайд 55

Метод открытой адресации. Квадратичное исследование. Используется хэш-функция где h` - вспомогательная

Метод открытой адресации. Квадратичное исследование.

Используется хэш-функция
где h` - вспомогательная хэш-функция, c1

и c2 – положительные вспомогательные константы, i = 0,1,…,m-1.
Прим. Требуется тщательный выбор c1, c2, m.
Проблема метода: вторичная кластеризация (последовательности исследований у ключей совпадают, если совпадают начальные позиции исследований).

Суть метода
Методы исследования

Слайд 56

Метод открытой адресации. Двойное хеширование. Используется хеш-функция где h1, h2 -

Метод открытой адресации. Двойное хеширование.

Используется хеш-функция
где h1, h2 - вспомогательные хеш-функции,

i = 0,1,…,m-1.
Стартовое значение: h1(k)
Шаг поиска: h2(k)

Суть метода
Методы исследования

- Предыдущая
Treasure hunter. Shapes and colors. Slides and pages
Следующая -
Новые формы работы включения родителей в образовательное пространство дошкольного учреждения

Похожие презентации

Компьютерный сленг
Презентация на тему Вставка музыки в презентацию
Основы цифровой электроники
Условная функция и логические выражения в табличном процессоре Excel
Схемы
Представление информации в различных системах счисления
Macromedia Flash 8, первое знакомство
Wi-FIT PROJECT
Управление объектами файловой структуры с помощью операционной оболочки
Основы информатики
Вычислительные системы, сети и телекоммуникации. Эволюция вычислительных систем
Компьютерные сети Телекоммуникационные технологии
Разработка методов цифровой стеганографии, на основе самомодифицирующегося кода, для защиты программного обеспечения
Файловый ввод-вывод данных в Pascalе Средства обработки файлов 11 класс
Презентация "Графы. Поиск путей в графе" - скачать презентации по Информатике
Стандартная библиотека классов. Generics.
Моделирование и формализация. Информация и информационные процессы
Технологии распределенных вычислений. Распределенные базы данных. Технологии и модели "клиент-сервер"
Одномерные массивы
Кодування символів. Особливості двійкового кодування
Технические основы создания и ведения интернет-бизнеса. Сервисы рассылок в Смартреспондере, Ждазклике, Экомтулсе
Системы счисления
Размещение данных 1С:Предприятия 8
Кодирование информации. Язык и алфавит. Дискретность. Алфавитный подход кизмерению количества информации
Работа с текстовой информацией (4 класс)
Презентация "Файл подкачки" - скачать презентации по Информатике
Основные понятия PHP
Разработка и бизнес-администрирования проекта по созданию веб-приложения для оказания образовательных услуг
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть