Метод умножения (мультипликативный метод)
Согласно методу, индекс элемента в хэш-таблице определяется по формуле:
,
где 
– взятие дробной части числа; 
– взятие целой части числа; 
– рациональное положительное число, меньшее единицы ( 
); 
– преобразуемый ключ; 
– количество строк в хэш-таблице.
В общем случае значение может быть любым, принадлежащим указанному диапазону. Принято считать неплохим значением 
, соответствующее так называемому золотому сечению. Считается, что при данном значении элементы в хэш-таблице распределяются достаточно равномерно.
В качестве принято выбирать одну из степеней двойки, так как умножение на 
равносильно сдвигу на разрядов и производится быстрее.
Например, при 
, , хэш-функция будет давать следующие значения индексов:
для 
, 
для 
, 
для 
, 
При осуществлении поиска в хэш-таблице значение должно быть таким же, как и при заполнении хэш-таблицы.
Аддитивный метод
Ключами в данном методе являются символьные строки.
На первом этапе реализации метода каждая строка преобразутся в целое число путем суммирования кодов всех символов. Хэш-функция определяется как остаток от деления рассчитанного числа 
на число элементов алфавита (как правило, 
):
Здесь 
– целое число, полученное в результате суммирования кодов всех символов ключа.
Так, строке abc будет соответствовать индекс i хэш-таблицы:
Коллизии в аддитивном методе возникают достаточно часто, например, для ключей, состоящих из одинакового набора символов (abc и cba).
|
|
|
Методы обработки коллизий
Существует две группы методов обработки коллизий:
· С закрытой адресацией (сlose-addressing). В данной группе методов для хранения элементов с одинаковыми хэш-адресами используются отдельная область памяти. Алгоритмы данной группы используют дополнительные ячейки в хэш-таблице.
· С открытой адресацией (open-addressing). В методах данной группы для хранения элементов с одинаковыми хэш-адресами используются ячейки самой таблицы. В алгоритмах из данной группы реализуется перебор элементов хэш-таблицы в поисках свободного места для записи.
К первой группе относятся метод цепочек (связывания), а ко второй – методы с линейным, квадратичным опробованием и метод двойного хэширования.
Метод цепочек (закрытое хэширование)
Суть метода заключается в создании для каждого индекса хэш-таблицы отдельного односвязного списка, в который будут помещаться все ключи, преобразованные в этот индекс. В самой таблице по адресу i хранится не ключ, а адрес списка ключей (рисунок 5.14). Ключи заносятся в списки согласно рассчитанным индексам (в конец списка, в начало списка или в найденное место отсортированного списка).
|
|
|
Рис. 5.14. Схема метода разрешения коллизий методом связных списков
Для поиска или удаления элемента из хэш-таблицы по значению ключа определяется его адрес в таблице и в списке, связанном с данным адресом, выполняется поиск.
При реализации открытого хэширования важно найти компромисс между числом строк в списке (количеством список) и их длинной. При малом количестве ячеек в таблице, списки будут иметь большую длину и поиск в них будет занимать значительное время.
Достоинством метода цепочек является то, что таблица никогда не переполняется так при добавлении нового элемента происходит только увеличение длины вписка. К недостаткам метода можно отнести то, что организация списков и работа с ними требует дополнительную память и время.
Дата добавления: 2020-01-07; просмотров: 244; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!