Организация поиска. Хеширование

Содержание

Слайд 2

Словарные операции поиск элемента х; добавление нового элемента х; удаление элемента

Словарные операции
поиск элемента х;
добавление нового элемента х;
удаление элемента х.

Структуры данных
для

выполнения словарных операций

массив;
поисковые деревья;
хеш-таблицы.

Существуют интересные гибриды, находящиеся посередине между деревьями поиска и хеш-таблицами, которые реализуют концепцию упорядоченного множества. Это всевозможные деревья Ван Эмде Боасса (Van Emde Boas tree), X-fast-, Y-fast- и Fusion-деревья, у которых в оценках временной сложности появляется двойной логарифм.

Слайд 3

Абстрактный тип данных: множество (set) Абстрактный тип данных: ассоциативный массив (map)

Абстрактный тип данных: множество (set)

Абстрактный тип данных: ассоциативный массив (map)

Структуры данных

на основе хеш-таблиц реализованы в стандартных библиотеках всех широко используемых языков программирования.
Слайд 4

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

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

[0, N).

Обозначим через K множество возможных ключей: K = {0, 1, 2, . . . , N − 1}.

На практике множество K обычно довольно большое.
Часто в качестве ключей в промышленном программировании применяются 32-битные или 64-битные целые числа, т. е.
N = 232 ≈ 4,2 · 109
или
N = 264 ≈ 1,8 · 1019 .

Устройство хеш-таблицы

Слайд 5

1. Прямая адресация Если достаточно памяти для массива, число элементов которого

1. Прямая адресация

Если достаточно памяти для массива, число элементов которого равно

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

Имеем булев массив T размера N, называемый таблицей с прямой адресацией, в котором элемент ti содержит истинное значение, если ключ i входит в множество, и ложное значение, если ключ i в множестве отсутствует.

- добавление ключа;
- проверка наличия ключа;
- удаление ключа.

базовые операции:

O(1)

K = {0, 1, 2, . . . , N − 1}

T:

Слайд 6

размер таблицы с прямой адресацией не зависит от того, сколько элементов

размер таблицы с прямой адресацией не зависит от того, сколько элементов

реально содержится в множестве;

если множество K всевозможных ключей велико, то хранить в памяти массив T размера N непрактично, а то и невозможно:

если число реально присутствующих в таблице записей мало по сравнению с N, то много памяти тратится зря;

Недостатки прямой адресации

Тем не менее при сравнительно небольших N метод прямой адресации успешно используется на практике.

T:

K = {0, 1, 2, . . . , N − 1}

Слайд 7

2. Хеш-функция (англ. hash function) Введём некоторую функцию, называемую хеш-функцией, которая

2. Хеш-функция (англ. hash function)

Введём некоторую функцию, называемую хеш-функцией, которая отображает

множество ключей в некоторое гораздо более узкое множество:
h : {0, 1, 2, . . . , N − 1} → {0, 1, . . . , M − 1},
x→ h(x).

K = {0, 1, 2, . . . , N − 1}.

Величина h(x) называется хеш-значением (англ. hash value) ключа x.

Далее вместо того, чтобы работать с ключами, мы работаем с хеш-значениями.

Если разные ключи получают одинаковые хеш-значения: x ≠ y, h(x) = h(y), то говорят, что произошла коллизия (англ. collisions).

Хотелось бы выбрать хеш-функцию так, чтобы коллизии были невозможны. Но в общем случае при M < N это неосуществимо: согласно принципу Дирихле (1834 г.), нельзя построить инъективное отображение из большего множества в меньшее.

Слайд 8

является вполне годной для практики хеш-функцией и часто применяется; любая пара

является вполне годной для практики хеш-функцией и часто применяется;

любая пара различных

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

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

всякий раз возвращает случайное число от 0 до M − 1 включительно, выбранное равновероятно независимо от x

возвращает остаток от деления ключа x на M

в качестве М предпочтителен выбор простого числа, далеко отстоящего от степени 2;

если ключи возникают, как десятичные числа, то нежелательно выбирать в качестве M степень 10 (т.к. в этом случае окажется, что часть цифр числа уже полностью определяют хеш-значение);

деление с остатком

умножение

 

 

 

 

в качестве М выбирают степень 2;

утверждают, что наиболее удачное значение константы A = 0,6180339887 (золотое сечение).

Слайд 9

Велика ли вероятность коллизий? Пусть осуществляется хеширование для n различных ключей,

Велика ли вероятность коллизий?

Пусть осуществляется хеширование для n различных ключей, т.е.

мы строим вектор длины n, где назначаем каждому элементу одно из M значений (предположим, что хеш-значения независимы и распределены идеально равномерно от 0 до M − 1).

Число векторов длины n, которые могут быть при этом сгенерированы:

Число векторов длины n, которые могут быть при этом сгенерированы и в которых элементы не повторяются:

 

Вероятность того, что все элементы сгенерированного вектора различны,
т.е. нет коллизий:

Вероятность того, что будут коллизии:

 

 

 

каждый элемент может принять
одно из M значений

Слайд 10

 

 

 

 

 

 

 

Слайд 11

или

 

 

 

или

 

Слайд 12

Разработано несколько стратегий разрешения коллизий Разрешение коллизий методом цепочек (англ. separate

Разработано несколько стратегий разрешения коллизий

Разрешение коллизий методом цепочек
(англ. separate chaining)


Разрешение коллизий методом открытой адресации
(англ. open addressing)

Слайд 13

Разрешение коллизий методом цепочек (англ. separate chaining)

Разрешение коллизий методом цепочек
(англ. separate chaining)

Слайд 14

Хеш-функция h раскладывает исходные ключи x по корзинам (англ. bins, buckets)

Хеш-функция h раскладывает исходные ключи x по корзинам (англ. bins, buckets)

или слотам (англ. slots).

ключ x попадает в корзину с номером, равным хеш-значению h(x);

для хранения элементов с одинаковыми хеш-значениями внутри одной корзины можно использовать связные списки;

На верхнем уровне организуется массив размера M — по числу различных значений хеш-функции, каждый элемент которого — это односвязный список, состоящий из ключей, имеющих конкретное хеш-значение. Возникают цепочки ключей, из-за чего метод и получил название метода цепочек.

Слайд 15

Операция вставки элемента

Операция вставки элемента

Слайд 16

Сначала вычисляется хеш-значение h(x) для ключа x, а затем происходит обращение

Сначала вычисляется хеш-значение h(x) для ключа x, а затем происходит обращение

к соответствующему связному списку.

Если НЕ СТОИТ ЗАДАЧА ПРОВЕРЯТЬ, ПРИСУТСТВУЕТ ЭЛЕМЕНТ X В ТАБЛИЦЕ ИЛИ НЕТ, то операция вставки может быть реализована за константное время: всегда можно добавить элемент в начало списка, и не нужно идти по всему связному списку.

Если требуется поддерживать УНИКАЛЬНОСТЬ ЭЛЕМЕНТОВ, то сначала надо проверить, есть элемент x в таблице или нет, и добавлять только уникальные элементы. Поэтому операция вставки вначале выполняет проход по списку, и на это расходуется время, пропорциональное длине соответствующей цепочки.

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

Слайд 17

Операция удаления элемента

Операция удаления элемента

Слайд 18

Вычисляем сначала хеш-значение для ключа x: h(45)=5. В общем случае из

Вычисляем сначала хеш-значение для ключа x: h(45)=5.

В общем случае из

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

Затем выполняем прохождение соответствующего списка в поиске элемента x.

Слайд 19

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

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

цепочки.

 

 

ВНИМАНИЕ
Даже если цепочка имеет нулевую длину, то требуется выделить время на то, чтобы вычислить хеш-значение (мы полагаем, что хеш-функция от ключа вычисляется за константу) и обратиться к соответствующей цепочке.

Слайд 20

Разрешение коллизий методом открытой адресации (англ. open addressing)

Разрешение коллизий методом открытой адресации
(англ. open addressing)

Слайд 21

В линейном массиве хранятся непосредственно ключи, а не заголовки связных списков.

В линейном массиве хранятся непосредственно ключи, а не заголовки связных списков.

В

каждой ячейке массива разрешено хранить только один элемент.

Что делать, если произошла коллизия?

Слайд 22

Последовательность проб (англ. probe sequence) Обозначим через h(x,i) номер ячейки в

Последовательность проб
(англ. probe sequence)

Обозначим через h(x,i) номер ячейки в массиве,

к которой следует обращаться на i-й попытке при выполнении операций с ключом x.

Последовательность проб для ключа x получается такой:
h(x,0),
h(x,1),
h(x,2),
...

Будем нумеровать попытки с 0 для каждого вновь поступающего элемента.

Слайд 23

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

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

в результате M проб все ячейки хеш-таблицы оказались просмотренными ровно по одному разу в каком-либо порядке:
∀x ∈ K {h(x,i) | i = 0,1,...,M − 1} = {0,1,...,M − 1}.

Широко используются три вида последовательностей проб:

линейная;

квадратичная;

двойное хеширование.

Слайд 24

Линейное пробирование Ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом c

Линейное пробирование

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

ячейками:
h(x, i) = (h′(x) + c·i) mod M,
где h′(x) — некоторая хеш-функция.
Слайд 25

h(x,i)=(x+2·i) mod 10 Например, при x = 5, подставляя i от

h(x,i)=(x+2·i) mod 10

Например, при x = 5, подставляя i от

0 до 9, будем получать индексы:
5,7,9,1,3,5,7,9,1,3
в результате чётные позиции оказываются не посещены.

Функция

Например, при x = 5, подставляя i от 0 до 9, будем получать индексы (каждый индекс возвращается один раз):
5,8,1,4,7,0,3,6,9,2

h(x,i)=(x+3·i) mod 10

НЕ ПОДХОДИТ в качестве последовательности проб.

Функция

ПОДХОДИТ в качестве последовательности проб

Слайд 26

Теорема Для того чтобы в ходе M проб все ячейки таблицы

Теорема

Для того чтобы в ходе M проб все ячейки таблицы оказались

просмотренными по одному разу, необходимо и достаточно, чтобы число c было взаимно простым с размером хеш-таблицы M.

В простейшем случае можно взять единицу в качестве константы c
h(x,i) =(h′(x)+i) mod M

h(x, i) = (h′(x) + c·i) mod M

Слайд 27

Доказательство. Воспользуемся сведениями из элементарной теории чисел. Докажем необходимость Пусть h(x,

Доказательство.
Воспользуемся сведениями из элементарной теории чисел.
Докажем необходимость
Пусть h(x, i)

пробегает все значения от 0 до M − 1. Значит, для любого t найдётся такой индекс i, что c · i ≡ t (mod M). В частности, это верно для t = 1. Следовательно, есть такое i, что c · i ≡ 1 (mod M), или, другими словами, c · i − 1 делится на M. Пусть d — общий делитель чисел c и M. Тогда число 1 также вынуждено делиться на d. Значит, d = ±1, т.е. числа c и M взаимно просты и не могут иметь других общих делителей.
Докажем достаточность
Пусть числа c и M взаимно просты. Предположим от противного, что при i-й и j-й пробах получаются одинаковые индексы: h(x, i) = h(x, j). Но это значит, что c · i ≡ c · j (mod M), или
c ·(i − j) ≡ 0 (mod M). Отсюда следует, что разность i − j делится на M без остатка. Но раз номера попыток i и j оба лежат на отрезке от 0 до M − 1, то это возможно лишь в случае, когда i = j. Противоречие. Значит, при всех попытках пробы получаются разными. Поскольку попыток всего M, каждая ячейка будет учтена по одному разу.

Теорема

Для того чтобы в ходе M проб все ячейки таблицы оказались просмотренными по одному разу, необходимо и достаточно, чтобы число c было взаимно простым с размером хеш-таблицы M.

Слайд 28

Недостаток линейного пробирования проявляется в том, что на реальных данных часто

Недостаток линейного пробирования проявляется в том, что на реальных данных часто

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

Линейное пробирование:

h(x,i) = (h′(x) + c·i) mod M

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

с=2

с=3

с=1

Слайд 29

Номер ячейки квадратично зависит от номера попытки, расстояние между ячейками с

Номер ячейки квадратично зависит от номера попытки, расстояние между ячейками с

каждой итерацией увеличивается на константу (=2·c2).

Квадратичное пробирование:

h(x,i) = (h′(x) + c1·i + c2·i2) mod M,

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

c1=1
c2=3

i=0

i=1

i=2

i=3

где числа c1 и c2 фиксированы (эти значения должны быть тщательно подобраны, чтобы в результате M попыток все ячейки были посещены, например, если M=11, то можно взять c1=1, c2=3 ).

Слайд 30

Двойное хеширование: h(x,i) = (h'(x) + h"(x) ·i) mod M Последовательность

Двойное хеширование:

h(x,i) = (h'(x) + h"(x) ·i) mod M

Последовательность проб

при работе с ключом x представляет собой арифметическую прогрессию (по модулю M) с первым членом h'(x) и шагом h"(x).

Для этого можно поступить следующим образом:
• выбрать в качестве M степень двойки, а функцию h"(x) взять такую, чтобы она принимала только нечётные значения;
• выбрать в качестве M простое число и потребовать, чтобы вспомогательная хеш-функция h"(x) принимала значения от 1 до M − 1.

Для того, чтобы последовательность проб покрыла всю таблицу, значение h'(x) должно быть ненулевым и взаимно простым с M.

Слайд 31

Операция вставки элемента

Операция вставки элемента

Слайд 32

Перед вставкой ключа x выполняется поиск этого ключа. Если такой элемент

Перед вставкой ключа x выполняется поиск этого ключа.
Если такой элемент x

уже есть в таблице, то вставка не требуется.
Затем проверяется принципиальное наличие ячеек, не занятых ключами
(счётчик занятых ячеек).
Если есть свободные ячейки, то осуществляется пробирование, начиная с того места, в которое указывает хеш-функция, в соответствии с некоторой последовательностью проб, пока не будет найдено свободное место в хеш-таблице.
В свободную ячейку заносится x, а счётчик занятых ячеек увеличивается на 1.
Слайд 33

Например, при линейном пробировании: h(x,i) = (x+i) mod M, М=10 7,

Например, при линейном пробировании:
h(x,i) = (x+i) mod M, М=10

7, 29, 67,

38, 25, 27, 18

7

29

67

25

38

27

67

38

38

27

27

27

27

18

18

18

18

18

h(7, 0)=7 - свободна – заносим 7

h(29, 0)=9 - свободна – заносим 29

h(67, 0)=7 - занята

h(67, 1)=8 - свободна – заносим 67

h(38, 0)=8 - занята

h(38, 1)=9 - занята

h(38, 2)=0 - свободна – заносим 38

h(25, 0)=5 – свободна – заносим 25

и так далее …

Название «открытая адресация» связано с тем фактом, что положение (адрес) элемента не определяется полностью его хеш-значением.

Хеш-таблица будет иметь следующий вид:

для последовательности элементов:

Слайд 34

Операция поиска элемента Случай 1. Предположим, сначала что в таблице операция удаления элемента НЕ поддерживается.

Операция поиска элемента

Случай 1.
Предположим, сначала что в таблице операция

удаления элемента НЕ поддерживается.
Слайд 35

Ячейки массива проверяются, в соответствии с той же функцией последовательности проб,

Ячейки массива проверяются, в соответствии с той же функцией последовательности проб,

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

7

29

25

67

38

27

18

Поиск останавливается как только будет выполнено одно из условий:
найден элемент x;
достигнута пустая ячейка (элемента x в таблице нет);
выполнены M попыток (таблица полностью заполнена, а элемента - нет).

=19

=19

=19

=19

=19

СТОП, элемента x=19 НЕТ

Для ячейки вводится два состояния:
empty — ячейка пуста;
key(x) — ячейка содержит ключ x.

Слайд 36

Операция поиска элемента Случай 2. Предположим, что в хеш-таблице поддерживается операция удаления элемента.

Операция поиска элемента

Случай 2.
Предположим, что в хеш-таблице поддерживается операция

удаления элемента.
Слайд 37

h(x,i)=(x+i) mod M, 7 29 25 67 38 27 18 M=10

h(x,i)=(x+i) mod M,

7

29

25

67

38

27

18

M=10

Затем выполнили поиск
элемента x=18.

=18

=18

=18

=18

СТОП, элемента x=18 НЕТ

- НЕ ВЕРНО

Предположим, что из таблицы сначала
удалили элемент x=27.

empty

Для удаления элемента x=27 вначале выполняем его поиск и, если ячейка с элементом найдена, то:
переводим её в состояние свободной;
счётчик занятых ячеек уменьшаем на единицу.

Поиск останавливается как только будет выполнено одно из условий:
найден элемент x;
достигнута пустая ячейка (элемента x в таблице нет);
выполнены M попыток (таблица полностью заполнена, а элемента - нет).

Слайд 38

h(x, i) = (x + i) mod M, 7 29 25

h(x, i) = (x + i) mod M,

7

29

25

67

38

27

18

M=10

=18

=18

=18

=18

Теперь при удалении

x=27, ячейка c номером 1 перейдет в состояние deleted.

Для ячейки вводятся три состояния:
empty — ячейка пуста;
key(x) — ячейка содержит ключ x;
deleted — ячейка ранее содержала ключ, но он был удалён.

deleted

Поиск останавливается как только будет выполнено одно из условий:
найден элемент x;
достигнута пустая ячейка empty (элемента x в таблице нет);
выполнены M попыток (таблица полностью заполнена, но элемента x в таблице нет).

=18

Добавление нового элемента можно осуществлять как в ячейку empty,
так и в ячейку deleted.

Слайд 39

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

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

Слайд 40

1. Нетрудно видеть, что при разрешении коллизий методом открытой адресации наличие

1. Нетрудно видеть, что при разрешении коллизий методом открытой адресации наличие

большого числа deleted-ячеек отрицательно сказывается на времени выполнения операции поиска, а значит и других операций.

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

7

9

67

deleted

7

67

9

deleted

deleted

deleted

deleted

deleted

h(x, i) = (x + i) mod M,

M=10,

K={9,7,67}

Слайд 41

2. Число хранимых ключей не может превышать размер хеш-массива (при заполнении

2. Число хранимых ключей не может превышать размер хеш-массива (при заполнении

на 70% производительность падает и нужно расширять таблицу);

3. Более строгие требования к выбору хеш-функции: чтобы распределять значения максимально равномерно по корзинам, функция должна минимизировать кластеризацию хеш-значений, которые стоят рядом в последовательности проб; при образовании больших кластеров, время выполнения всех операций может стать неприемлемым даже при том, что заполненность таблицы в среднем невысокая и коллизии редки.

Слайд 42

Преимущества открытой адресации

Преимущества
открытой адресации

Слайд 43

экономия памяти, если размер ключа невелик по сравнению с размером указателя

экономия памяти, если размер ключа невелик по сравнению с размером указателя
в

методе цепочек приходится хранить в массиве указатели на начала списков, а каждый элемент списка хранит, кроме ключа, указатель на следующий элемент, поэтому на все эти указатели расходуется память;
не требуется затрат времени на выделение памяти на каждую новую запись и подход может быть реализован даже на миниатюрных встраиваемых системах, где полноценный аллокатор недоступен;
нет лишней операции обращения по указателю (indirection) при доступе к элементу;
лучшая локальность хранения, особенно с линейной функцией проб
когда размеры ключей небольшие, это даёт лучшую производительность за счёт хорошей работы кеша процессора, который ускоряет обращения к оперативной памяти;
однако, когда ключи «тяжёлые» (не целые числа, а составные объекты), то они забивают все кеш-линии процессора, к тому же много места в кеше тратится на хранение незанятых ячеек - можно в массиве с открытой адресацией хранить не сами ключи, а указатели на них, но при этом часть преимуществ при этом будет утрачена.
Слайд 44

Хеш-таблицы на практике Любой подход к реализации хеш-таблицы может работать достаточно

Хеш-таблицы на практике

Любой подход к реализации хеш-таблицы может работать достаточно быстро

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

Критически важным показателем для хеш-таблицы является коэффициент заполнения— отношение числа ключей,

Критически важным показателем для хеш-таблицы является коэффициент заполнения— отношение числа ключей,

которые хранятся в хеш-таблице, к размеру хеш-таблицы:

 

Коэффициент заполнения (англ. load factor )

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

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

Для оптимального использования хеш-таблицы желательно, чтобы её размер был примерно пропорционален числу ключей, которые нужно хранить.
На практике редко случается, что число ключей фиксировано и можно заранее выставить хорошее значение параметра M. Если ставить его заведомо больше, то много памяти будет потрачено зря (особенно если нужно организовать много хеш-таблиц с небольшим числом ключей в каждой).

Слайд 46

Реализация хеш-таблицы общего назначения обязана поддерживать операцию изменения размера. На практике

Реализация хеш-таблицы общего назначения обязана поддерживать операцию изменения размера.

На практике часто

используемым приёмом является автоматическое изменение размера.
Когда коэффициент заполнения превышает некоторый порог αmax, выделяется память под новую, большую таблицу, все элементы из старой таблицы перемещаются в новую, затем память из-под старой хеш-таблицы освобождается.
Аналогично, если коэффициент заполненности опускается ниже другого порога αmin, элементы перемещаются в хеш-таблицу меньшего размера.
Слайд 47

Объединение хеш-значений Предположим, что координаты точек на плоскости хранятся в виде

Объединение хеш-значений

Предположим, что координаты точек на плоскости хранятся в виде пар

целых чисел (x,y), и нужно создать множество точек с использованием хеш-таблицы.
Пусть получены хеш-значения двух координат h(x) и h(y).
Как их объединить, чтобы получить хеш от пары?
Слайд 48

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

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

дальше в реализации хеш будет взят по нужному модулю M). Часто на практике программисты для соединения хешей пишут тривиальные функции, например через операцию побитового исключающего или (xor):
def combine(hx, hy):
return hx ^ hy
Такой вариант часто работает на практике приемлемо, но не лишён очевидных недостатков. Например, для всех точек с равными координатами x и y хеш-функция будет принимать нулевое значение, и если точек на прямой y = x во входных данных окажется много, производительность будет низкой из-за коллизий.
Также очевидно, что разные точки (x, y) и (y, x), симметричные относительно той же прямой, получат одинаковые хеш-значения. Чтобы подобрать пары, дающие коллизию, было труднее, для объединения хешей используют более сложные функции с обилием «магических» констант и странных операций.
Например, в C++-библиотеке boost используется примерно такая формула:
def combine(hx, hy):
return hx ^ (hy + 0x9e3779b9 + (hx << 6) + (hx >> 2))
Часто берут линейную комбинацию двух хеш-значений с, например, большими взаимно простыми коэффициентами.
def combine(hx, hy):
return hx + 1000000007 * hy
Основной смысл таких манипуляций — сделать так, чтобы на реально встречающихся в жизни данных коллизии были более редкими. Но контрпример при желании можно подобрать. Лучшего универсального решения в этом деле нет.
Слайд 49

Хеширование строк. Полиномиальное хеширование

Хеширование строк.
Полиномиальное хеширование

Слайд 50

Предположим, что на вход поступает строка: S= ‘аbcdb’ → 1,2,3,4,2. Прямой

Предположим, что на вход поступает строка:

 

 

S= ‘аbcdb’ → 1,2,3,4,2.

 

Прямой полиномиальный хеш


(хеширование слева направо)

Обратный полиномиальный хеш
(хеширование справа налево)

 

 

 

 

 

 

это число

это число

Слайд 51

 

Слайд 52

 

Слайд 53

0 …

0

 

 

 

 


Слайд 54

Так как хеш - это значение многочлена, то для многих строковых

Так как хеш - это значение многочлена, то для многих строковых

операций можно быстро пересчитывать хеш результата.

 

 

 

 

 

 

Слайд 55

 

 

 

Слайд 56

 

 

Слайд 57

Применение хеширования строк Т S Т Т

 

Применение хеширования строк

Т

S

Т

Т

Слайд 58

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

Проход по содержимому хеш-таблицы

В процессе программирования может возникнуть необходимость выполнить обход

всех элементов структуры данных и, например, распечатать их.

Функция для итерации по содержимому структуры является полезной, поэтому обычно поддерживается в реализациях хеш-контейнеров, с которыми ведётся работа на практике.

Слайд 59

В большинстве реализаций проход по хеш-множествам выполняется в произвольном порядке, не

В большинстве реализаций проход по хеш-множествам выполняется в произвольном порядке, не

гарантируется какой-либо отсортированности ключей.
В случае, если внутренняя реализация хеш-таблицы использует метод цепочек, обычно функция обхода выдаёт сначала все элементы первой корзины (с хеш-значением 0) в порядке их следования в цепочке, затем все элементы второй корзины (с хеш-значением 1), и т. д.

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

Наоборот, средства итерации по ключам множества, которое построено на базе бинарного поискового дерева, обычно возвращают ключи в порядке возрастания (выполняется внутренний обход дерева). Порядок фиксирован и каждый раз одинаковый.

Часто предсказуемость результата удобна, например, для написания модульных тестов к частям программы. Таким образом, если порядок итерации важен, возможно, стоит использовать «древесные» структуры данных.

Слайд 60

Хеш-таблицы в C++

Хеш-таблицы в C++

Слайд 61

Долгое время в языке C++ не было стандартных реализаций структур данных

Долгое время в языке C++ не было стандартных реализаций структур данных

на основе хеш-таблиц.
Контейнеры std::set и std::map из STL строятся на основе сбалансированных бинарных поисковых деревьев (во всех популярных реализациях применяются красно-чёрные деревья).
Хеш-таблицы существовали в виде нестандартных расширений (например stdext::hash_set в Visual Studio) или внешних библиотек (например boost).
Слайд 62

Наконец, в стандарте C++11 в STL официально были добавлены хеш-таблицы. Стандарт

Наконец, в стандарте C++11 в STL официально были добавлены хеш-таблицы.
Стандарт

предусматривает четыре контейнера на основе хеш-таблиц, которые отличаются от своих аналогов на основе деревьев наличием префикса unordered_ в названии.
std::unordered_set представляет собой динамическое множество;
std::unordered_map — ассоциативный массив.
Cуществует также два multi-контейнера, которые допускают хранение одинаковых ключей.

Стандарт требует, чтобы в построении этих структур данных авторы компиляторов использовали разрешение коллизий методом цепочек.

Метод открытой адресации не был стандартизирован из-за внутренних трудностей при удалении элементов. Однако детали реализации хеш-таблиц стандартом не регламентируются.

Слайд 63

В качестве хеш-значения в C++ используется число типа size_t. Все хеш-контейнеры

В качестве хеш-значения в C++ используется число типа size_t.
Все хеш-контейнеры предоставляют

метод rehash(), который позволяет установить размер хеш-таблицы (число корзин M).
Метод под названием load_factor() возвращает текущий коэффициент заполнения.
Слайд 64

Рассмотрим более подробно реализацию в компиляторе GCC (GNU Compiler Collection) Пусть

Рассмотрим более подробно реализацию в компиляторе GCC (GNU Compiler Collection)

Пусть

ключи добавляются в std::unordered_set по одному.
Когда коэффициент заполнения достигает значения 1, происходит перестроение хеш-таблицы:
в качестве нового числа корзин берётся первое простое число из заранее составленного списка, не меньшее удвоенного старого числа корзин (таким образом, размер таблицы как минимум удваивается и является простым числом).
Длины отдельных цепочек никак не анализируются (появление одной длинной цепочки не повлечёт за собой операцию перестроения).
Слайд 65

Хеш-таблицы в JAVA

Хеш-таблицы в JAVA

Слайд 66

Коллекции HashSet и HashMap реализуются как хеш-таблицы, для разрешения коллизий используется

Коллекции HashSet и HashMap реализуются как хеш-таблицы, для разрешения коллизий используется

метод цепочек.
Для хеширования целых чисел применяется функция следующего вида:
int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
операция >>> — беззнаковый сдвиг вправо: биты смещаются вправо, число слева
дополняется нулями;
операция ^ — поразрядное сложение по модулю 2, исключающее «или»;
Затем в классе коллекции результат функции hash берётся по модулю числа корзин, по которым раскладываются элементы.
Число корзин, оно же число различных значений хеш-функции M, в Java всегда выбирается как некоторая степень числа 2:
чтобы деление на M можно было заменить операцией битового сдвига вправо, так как современные процессоры выполняют инструкцию деления целых чисел существенно медленнее, чем битовые операции;
Слайд 67

В версии Java 8 разработчики озаботились вопросом устойчивости коллекций, использующих хеширование,

В версии Java 8
разработчики озаботились вопросом устойчивости коллекций, использующих хеширование,

к коллизиям.
В исходном коде библиотеки Java можно найти константу:
istatic final int TREEIFY_THRESHOLD = 8;
В случае, если новый ключ попадает в корзину, в которой уже лежат как минимум восемь других ключей, библиотека преобразует связный список для данной корзины в бинарное сбалансированное поисковое дерево.
Получается гибридная структура:
корзины для тех хеш-значений, где ключей мало, хранятся списками;
корзины, где ключей накопилось много, хранятся в виде деревьев.
Слайд 68

Хеш-таблицы в PYTHON

Хеш-таблицы в PYTHON

Слайд 69

Встроенный тип dict — ассоциативный массив, словарь —широко используется в языке.

Встроенный тип dict — ассоциативный массив, словарь —широко используется в языке.
Он

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

Интерпреттором CPython поддерживается опция командной строки -R, которая активирует на старте случайный выбор начального значения (англ. seed), которое затем используется для вычисления хеш-значений от строк и массивов байт.

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

Слайд 70

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

Криптографические хеш-функции

В криптографии множество K возможных ключей бесконечно, и любой

блок данных является ключом (в принципе, произвольный массив байт можно рассматривать как двоичную запись некоторого числа).
Хеш-функция h(x) называется криптографической, если она удовлетворяет следующим требованиям:
необратимость: для заданного значения хеш-функции c должно быть сложно определить такой ключ x, для которого h(x) = c;
стойкость к коллизиям первого рода: для заданного ключа x должно быть вычислительно невозможно подобрать другой ключ y, для которого h(x) = h(y);
стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару ключей x и y, имеющих одинаковый хеш.
Криптографические хеш-функции обычно не используются в хеш-таблицах, потому что они сравнительно медленно вычисляются и имеют большое множество значений. Зато такие хеш-функции широко применяются в системах контроля версий, системах электронной подписи, во многих системах передачи данных для контроля целостности.

Примерами криптографических хеш-функций являются алгоритмы MD5, SHA-1, SHA-256.
Так, метод SHA-1 ставит в соответствие произвольному входному сообщению некоторую 20-байтную величину, т. е. результат вычисления SHA-1 принимает одно из 2160 различных значений.
Пример вычисления SHA-1 от ASCII-строки, где результат записан в шестнадцатеричной системе счисления:
SHA-1("The quick brown fox jumps over the lazy dog") = 0x2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
В настоящий момент коллизии для MD5 и SHA-1 обнаружены, поэтому методы постепенно выходят из широкого использования.
Более новые алгоритмы семейства SHA-2 считаются существенно более стойкими к коллизиям. Тем не менее следует понимать, что коллизии есть обязательно, потому что нельзя биективно отобразить бесконечное множество в конечное. Вопрос только в том, насколько трудно эти коллизии отыскать.

Слайд 71

За годы развития вычислительной техники сформировалась наука о том, как практически

За годы развития вычислительной техники сформировалась наука о том, как практически

строить хеш-функции.
Разработаны всевозможные правила на тему того, какие биты ключа x стоит взять, на сколько позиций выполнить поразрядный сдвиг, как применить операцию исключающего «или», на что умножить, чтобы получить хеш, который бы выглядел как случайный.
Чтобы найти примеры практических хеш-функций, можно взять какую-нибудь стандартную библиотеку. Эти функции часто ничего не гарантируют: коллизии, конечно, есть.
Любую фиксированную хеш-функцию можно всегда «сломать» — придумать ситуацию, когда там будут одни сплошные коллизии.
Попробуем тогда внести элемент случайности при выборе хеш-функции?
Слайд 72

Универсальное хеширование (англ. universal hashing)

Универсальное хеширование
(англ. universal hashing)

Слайд 73

Добавить рандомизацию: внести элемент случайности, чтобы не было фиксированного «плохого» случая.

Добавить рандомизацию:
внести элемент случайности, чтобы не было фиксированного «плохого» случая.


Идея не брать какую-либо одну конкретную хеш-функцию, а, например, организовать программу так, чтобы при каждом запуске хеш-функция выбиралась заново.
Тогда одним и тем же входом «сломать» программу не получится, и можно будет рассуждать о длине цепочки с точки зрения теории вероятностей: говорить о том, какая длина цепочки в среднем, какая у неё дисперсия и т.п.
Такой подход называют универсальным хешированием.
Слайд 74

 

Слайд 75

p·(p-1) способ выбрать хеш-функцию из семейства добавление элемента – усреднённо O(1);

 

 

p·(p-1) способ выбрать хеш-функцию из семейства

добавление элемента – усреднённо O(1);

поиск

элемента – математичекое ожидание O(1).

Оценки

В 1977 году Дж.Л. Картером (J.L. Carter) и М.Н. Вегманом (M.N. Wegman) предложен один из способ построения универсального семейства хеш-функций для целочисленных ключей.

постулат Бертрана гласит, что существует достаточно близкое к N простое число: N≤ p < 2N

Слайд 76

Совершенное хеширование (англ. perfect hashing)

Совершенное хеширование
(англ. perfect hashing)

Слайд 77

Пусть S — фактическое множество ключей в хеш-таблице, и у этого

Пусть S — фактическое множество ключей в хеш-таблице, и у этого

множества размер n, где nТогда существует хеш-функция, которая не даёт коллизий: если элементов меньше, чем слотов, то их всегда можно отобразить без коллизий. Это хорошая хеш-функция, её называют совершенной.
Эта функция всегда есть и зависит от набора ключей.
Даже если предположить, что набор ключей статический и известен заранее (т.е. все ключи сразу поступили, размещены в таблице и новые ключи туда более не будут более добавлены), есть трудность в том, как эффективно задать эту хеш-функцию.
Слайд 78

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

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

константного объёма памяти, чтобы её хранить;
быстрой, т.е. требуется константное время на вычисление;
совершенной, т.е. коллизии отсутствуют.
Слайд 79

Совершенное двухуровневое хеширование

Совершенное двухуровневое хеширование

Слайд 80

Уровень 2 для каждой цепочки строится небольшая вторичная хеш-таблица, чтобы гарантировать

Уровень 2
для каждой цепочки строится небольшая вторичная хеш-таблица, чтобы гарантировать

отсутствие коллизий на этом уровне
выполнять
выбрать хеш-функцию для таблицы порядка (Li )2
(из универсального множества хеш-функций);
пока (есть коллизии)

 

В худшем случае поиск элемента выполняется за O(1)

К={10,22,37,40,60, 70,75}

x – ключ;
М – размер таблицы (произвольное число, не обязательно простое);
p - достаточно большое простое число, такое, что все ключи лежат в диапазоне от 0 до p-1 (p>M);
a - выбирается из множества {1,2,…,p-1}
b - выбирается из множества {0,1,…,p-1}

 

S=12+22+ 12 +32=15
15<3·9,
переход ко 2-у уровню

 

Уровень 1.

Уровень 2.

Математическое ожидание построения таблицы O(n)

Слайд 81

Общие задачи в iRunner для закрепления навыков 0.5. Хеш-таблица (разрешение коллизий метом открытой адресации)

Общие задачи в iRunner для закрепления навыков

0.5. Хеш-таблица (разрешение коллизий

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