Хеширование (hashing)
Общая идея подхода
Хеш-функция
Метод деления
Как выбрать М
Метод середины квадратов
Метод свертывания
Пример метода свертывания
Метод преобразования систем счисления
Пример метода преобразования систем счисления
Хорошая хеш-функция
Методы разрешения коллизий
Метод открытой адресации (закрытое хэширование)
Пример метода открытой адресации
Пример
Пример
Удаление ключа
Удаление ключа
Недостатки метода
Эффект скучивания
Повторное хеширование
Метод цепочек (открытое хэширование)
Недостатки метода цепочек
Заключение
181.00K
Категория: ИнформатикаИнформатика

Хеширование (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. Заключение

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