В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 13
Текст из файла (страница 13)
Понятно, что такая операция будет линейной относительноразмера хэш-таблицы, но зато есть надежда, что при тактике удвоения размера применятьрехэширование нужно будет достаточно редко.Если задача заключается в том, чтобы заранее скомпилировать хэш-таблицу из некоторого множества известных ключей, а потом только пользоваться ею для поиска ключей(отвечать на вопрос – «есть ключ в контейнере или нет?», либо искать связанное с ключомзначение в ассоциативном контейнере), то можно построить более компактный по памятиалгоритм разрешения коллизий – метод открытой адресации:H(K1)I1H(K2)I1K7K1H(K3)I1K2K3H(K6)I6H(K7)I6K6Рис.
27: Разрешение коллизий методом линейных проб при открытой адресации59Попав в какую-либо ячейку хэш-таблицы сравниваем хранящийся там ключ с искомым,и, если они не совпадают – переходим к следующей по порядку ячейке таблицы. Если онапустая – то сохраним в эту ячейку текущий ключ, если заполнена – опять сравниваемискомый ключ с ранее сохранённым. При необходимости – опять перейдем к следующейячейке, а если мы находимся в конце массива – перепрыгнем в его начало. Рано или поздномы найдём свободную ячейку, на которой поиск завершится, либо вернемся в самую первуюпроверенную ячейку, что будет означать, что наша таблица переполнилась и ничего большев неё сохранить нельзя.Математически этот алгоритм можно выразить как последовательный перебор разныххэш-функций, одна из которых рано или поздно приведёт нас к успеху:0 () = %, 1 () = ( + 1)%, 2 () = ( + 2)%, . .
. , () = ( + )%Обратите внимание, что этот набор функций линеен по , поэтому его и называют методомлинейных проб при открытой адресации. Можно применить и более сложные хэш-функции,например, метод квадратичных проб: () = ( + 2 )%Но обычно и метод линейных проб дает вполне приемлемые результаты.Понятно, что в любом методе открытой адресации некоторые коллизии будут зависеть отпорядка, в котором мы хэшируем ключи: при одном порядке данный ключ будет порождать коллизию, а при другом – не будет.
Но среднее количество коллизий все равно будетзависеть от коэффициента заполнения таблицы образом, подобным приведённому в таблице выше, а поэтому это не будет приносить никаких неприятностей для операций поиска ивставки.Но, в отличие от таблиц с разрешением коллизий методом цепочек, удалять ключи изтакой таблицы будет нельзя: удалив какое-то значение мы можем прервать непрерывнуюпоследовательность ячеек, в которую сохраняли коллизии, поэтому последующие ключипросто не найдутся, если что-то из таблицы удалить.В завершение вернёмся к вопросу выбора хэш-функции для нецелочисленных, и, возможно,вообще для нечисловых ключей.
Рассмотрим эту задачу на примере хэширования строк,так как объекты любой природы можно свести к строкам различной длины, просто преобразовав их к шестнадцатиричному виду байт, хранимых в оперативной памяти для данногообъекта, или перекодировав эти байты в строки другим, более экономным способом.Нам нужно сделать два шага: первым действием надо преобразовать строку в целое число,а вторым шагом – отобразить его в хэш-таблицу уже известным из предыдущей частилекции образом.
Первое, что приходит в голову для преобразования строки в число – этопросто просуммировать все байты этой строки, ведь каждый байт – это просто число отнуля до 255. Однако, такая хэш-функция будет неоптимальной по количеству коллизий:она будет давать совершенно одинаковые значения для строк, различающихся порядкомследования одних и тех же букв.Приведем пример неплохой хэш-функции для строк, которая реализована в одной из известных библиотек языка Си++:unsigned hashkey( const char* str ){unsigned hash = 0;while (*str) hash = (hash << 5) + hash + *str++;return hash;}60Здесь операция << 5 означает «битовый сдвиг левого операнда влево на 5 позиций» (илиже – что то же самое – «целочисленное умножение на 32»).Приведённая хэш-функция будет зависеть не только от букв строки, но и от порядка ихследования.
И не забудьте потом сделать второй шаг – взять остаток от деления возвращённого этой функцией числа на размер хэш-таблицы.Изобретение эффективных по коллизиям хэш-функций – увлекательное занятие, важно лишь вовремя остановиться: если количество коллизий для простой хэш-функции васустраивает, то незачем искать более совершенную хэш-функцию. Сэкономленное время работы программы не будет окупать затраты времени на изобретение новой хэш-функции иеё программирование.61Литература[1] Н.
Н. КалиткинЧисленные методы[2] R. S. Boyer, J. S. Moore762—772.// М., Наука, 1978.A fast string searching algorithm[3] M. Matsumoto, T. NishimuraMersenneuniform pseudorandom number generator.Simulations – 1998 –8 (1), 3-30.twister:A623-dimensionally20,equidistributed// ACM Trans. on Modeling and Computer[4] Г. М. Адельсон-Вельский, Е. М.
Ландис Один алгоритмДоклады АН СССР – 1962 – Т.146, № 2. – С. 263—266.[5] R. Bayer, E. McCreight OrganizationInformatica – 1972 – 1 (3), 173–189.// Comm. ACM – 1977 –организации информацииand Maintenance of Large Ordered Indexes//// ActaСписок иллюстраций123456789101112131415161718192021222324252627Метод дихотомии . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Метод хорд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Метод касательных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .«Плохой» выбор начального приближения . . . . . . . . . . . . . . . . . . . .Метод итераций: разные типы сходимости к корню уравнения . . . . . . . .Mersenne Twister: изменение состояния .
. . . . . . . . . . . . . . . . . . . . .Пример интерполяции многочленом, проходящим через три заданные точкиВставка элемента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Вставка-удаление в конце . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .Хранение элементов в деке . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Хранение элементов в деке . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Хранение элементов в списке . . . . . . . . . . . . . . . . . . . . . . .
. . . . .Вставка в список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Вставка в список перед нужным элементом . . . . . . . . . . . . . . . . . . .Удаление из списка элемента, следующего за указанным . . . .
. . . . . . . .Удаление из списка указанного элемента . . . . . . . . . . . . . . . . . . . . .Двусвязный список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Двоичное дерево поиска . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .Удаление внутреннего узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . .АВЛ-балансировка первого типа . . . . . . . . . . . . . . . . . . . . . . . . . .АВЛ-балансировка второго типа . . . . . . . . . . . . . . . . . .
. . . . . . . .Страничная организация двоичного дерева . . . . . . . . . . . . . . . . . . .Страничная организация двоичного дерева . . . . . . . . . . . . . . . . . . .Вставка в B-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . + -дерево . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Коллизии в хэш-таблице и их разрешение методом цепочек . . . . . . . . . .Разрешение коллизий методом линейных проб при открытой адресации . . .63101112121329364344444546464647474748495051535455565859.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
