Хеширование (hashing). Лекция 3

1. Хеширование (hashing)

Лекция 3

2.

• До сих пор речь шла о поиске необходимой
информации по заданному ключу путем
прямого сравнения значения аргумента с
искомым ключом. Лучший из рассмотренных
методов (бинарный поиск) имеет сложность
O(log2n).
• Эффективными методами поиска являются
те методы, которые минимизируют число
ненужных сравнений. В идеале хотелось бы
иметь такую организацию данных, при
которой вообще не было бы ненужных
сравнений.

3. Общая идея подхода

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

4. Хеш-функция

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

5.

• Любая хорошая функция хеширования
должна как можно равномернее
распределять ключи по всему диапазону
значений адресов.
• Однако всегда существует вероятность того,
что найдутся ключи Кey1 ≠ Кey2, такие, что
их хеш – адреса равны: Н(Кey1)=Н(Кey2).
Такая ситуация называется коллизией при
хешировании.

6.

• При использовании метода
хеширования необходимо решить две
задачи:
• выбрать функцию хеширования
• выбрать метод разрешения коллизий.

7.

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

8. Метод деления

• Наиболее распространенная функция
хеширования основывается на методе
деления и определяется в виде:
Н(Key)=(Key mod m)+1,
где Key - ключ,
mod –операция, вычисляющая остаток
от деления,
m – делитель.

9.

• Равномерность распределения
получаемых адресов во многом зависит
от выбранного делителя m. Следует
избегать четных делителей, т.к. при
этом четные и нечетные ключи
отображаются соответственно в четные
и нечетные адреса. Если множество
ключей в основном состоит из четных
или в основном нечетных ключей, будут
возникать многочисленные коллизии.

10. Как выбрать М

• Как показывают исследования, если m
является большим простым числом, то
количество коллизий невелико.
• Также неплохие результаты дает выбор
в качестве делителя m нечетного числа,
имеющего 20 и более делителей.

11. Метод середины квадратов

• При хешировании по методу середины
квадратов сначала ключ умножается сам на
себя. В качестве адреса выбирается столько
цифр из середины результата, какова
требуемая длина адреса.
• Рассмотрим это на примере. Пусть дан ключ
234583. при возведении его в квадрат
получаем 75395823889. Если требуется 100
адресов, то адрес будет равен 58, если
необходимо 1000 адресов – 582, если 10000
– 9582.

12.

• Иногда требуется получить некратное 10
количество адресов, например 736. в этом
случае необходимо взять три средние цифры
и умножить на коэффициент 0,736.
Например, 582*0,736=428.
• Эксперименты с реальными данными
показали, что метод середины квадратов
дает неплохой результат при условии, что
ключи не содержат много левых или правых
нулей подряд.

13. Метод свертывания

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

14. Пример метода свертывания

• Пусть дан ключ 3415768898. Для двух-,
трех-, и четырех цифрового адреса
получим следующие значения:
• 34+15+76+88+98=11;
• 341+576+889+8=814;
• 3415+7688+98=1201
• Методом свертывания используется,
как правило, для больших ключей.

15. Метод преобразования систем счисления

• Этот метод получения хеш-адреса
заключается в том, что ключ,
представленный в системе счисления q,
рассматривается как число в системе
счисления s, где s>q, причем s и q –взаимно
простые.
• Число из системы счисления с основанием s
переводиться в систему счисления с
основанием q, а адрес формируется путем
выбора правых цифр нового числа.

16. Пример метода преобразования систем счисления

• Пусть задан ключ (530476)10. рассматривая
его как (530476)11, переведем в десятичную
систему счисления с помощью следующих
вычислений:
• (530476)11 = 5*115+3*114+4*112+7*11+6 =
(849745)10
• Для двух-, трех-, четырех цифрового адреса
получим 45, 745 и 9745 соответственно.

17. Хорошая хеш-функция

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

18. Методы разрешения коллизий

• Существует два основных метода
разрешения коллизий:
• метод открытой адресации
• метод цепочек

19. Метод открытой адресации (закрытое хэширование)

• Пусть задан ключ Key и массив M, состоящий из
m элементов. Пусть d=Н(Key) – индекс массива
M, получаемый при использовании некоторой
хеш-функции Н, причем 1<=d<=m. Необходимо
расположить ключ Key в массиве M.
• Если элемент массива M[d] свободен, то ключ
Key помещается в эту позицию и включение
элемента завершается. Если же элемент M[d]
уже занят, в массиве просматриваются другие
элементы. Эти действия выполняются до тех
пор, пока не будет найдено свободное место
для размещения ключа Key.

20.

• Простейший способ поиска свободной
позиции состоит в последовательном
просмотре элементов массива с индексами:
d+1, …, m-1, m, 1, 2, …, d-1.
• Если в массиве есть хотя бы один свободный
элемент, он будет найден. В противном
случае, после просмотра всех позиций
массива можно сделать заключение о том,
что массив переполнен и добавление нового
ключа невозможно.

21.

• Алгоритм поиска ключа состоит в
вычислении его хеш – адреса тем же
алгоритмом, что и при первоначальной
расстановке ключей, и просмотре той
же последовательности элементов.
• Либо, при удачном поиске, будет
найден искомый ключ, либо, при поиске
неудачном, будет найдена незанятая
ячейка или будут просмотрены все
элементы массива.

22. Пример метода открытой адресации

• Пусть задан массив M из 10 элементов
(88, 30, 35, 33, 96, 28, 45, 52, 18, 16).
• Хеш-функцию будем вычислять
методом деления
Н(Key)=(Key mod 11)+1.

23. Пример

24. Пример

• Коллизия возникает при занесении ключей
33, 96, 52 и 45.
• У ключа 33 один хеш-адрес с ключом 88, у 96
и 52 – с ключом 30, а место ключа 45
оказалось занятым ранее размещенным
ключом 33.

25. Удаление ключа

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

26. Удаление ключа

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

27. Недостатки метода

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

28. Эффект скучивания

• Для рассмотренного выше примера при
пустом массиве вероятность того, что новый
элемент попадет в первую позицию, равна
1/10.
• Пусть теперь первая позиция занята. При
втором добавлении вероятность того, что
будет занята позиция два, в два раза
больше, чем вероятность попадания в
остальные позиции и т.д.
• Следовательно, имеет место тенденция
возникновения все более длинных
последовательностей занятых подряд
позиций, что увеличивает и время поиска, и
время добавления элементов.

29. Повторное хеширование

Существует несколько методов
повторного хеширования
• линейное опробование адрес=h(x)+ci ;
• квадратичное опробование
адрес=h(x)+ci+di2 ;
• двойное хеширование адрес=h(x)+ih2(x)
.

30.

• Среднее количество проб при линейном
опробовании ~ (1 + 1 / (1 - N/L) ) /2
~ (1 + 1 / (1 - N/L)2)/2
• Если размер таблицы L слишком большой,
то тратится слишком много памяти
• Если L мало, то будет переполнение
таблицы и снижение производительности при
заполненной таблице
• На практике коэффициент заполнения N/L
~ 1/2

31. Метод цепочек (открытое хэширование)

• Другой способ разрешения коллизий
состоит в том, чтобы поддерживать Т
связанных списков, по одному на
каждый возможный хеш - адрес.
• Таким образом, каждый список будет
содержать все ключи с одинаковым хеш
- адресом. Кроме того, необходимо
иметь массив из Т указателей на голову
каждого из Т списков.

32.

33.

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

34. Недостатки метода цепочек

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

35.

• Число проб для поиска
пропорционально N/L
• Если размер таблицы L слишком велик
то много пустых ячеек
• Если размер таблицы L мал, то
слишком длинные цепочки
• На практике L~ N/5

36.

• Идея хеширования впервые была высказана
Г.П. Ланом при создании внутреннего
меморандума IBM в январе 1953 г. с
предложением использовать для разрешения
коллизий метод цепочек. Примерно в это же
время другой сотрудник IBM, Жини Амдал,
высказала идею использования открытой
линейной адресации.
• В открытой печати хеширование впервые
было описано Арнольдом Думи (1956 год),
указавшим, что в качестве хеш-адреса
удобно использовать остаток от деления на
простое число. А. Думи описывал метод
цепочек для разрешения коллизий, но не
говорил об открытой адресации.

37.

• Подход к хешированию, отличный от
метода цепочек, был предложен А.П.
Ершовым (1957 год), который
разработал и описал метод линейной
открытой адресации
• Эмпирические результаты: Среднее
количество проб для успешного поиска
< 2 при N/L < 2/3
где N - число ключей, L - размер
таблицы

38. Заключение

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