Похожие презентации:
Хеширование (hashing). Лекция 3
1. Хеширование (hashing)
Лекция 32.
• До сих пор речь шла о поиске необходимойинформации по заданному ключу путем
прямого сравнения значения аргумента с
искомым ключом. Лучший из рассмотренных
методов (бинарный поиск) имеет сложность
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. Заключение
• В случае неудачного поиска нет никакойинформации. Например, методы поиска
могут дать меньшее значение и большее
значение, находящиеся в таблице, которые
могут быть использованы для
интерполирования функции
• Проблема выбора размера памяти (таблицы)
• Методы хеширования эффективны в
среднем, в наихудшем случае они очень
плохи ( нельзя использовать в жизненноважных ситуациях)