Разрешение коллизий с помощью списков

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

Время, необходимое для вставки в наихудшем случае равно . Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.

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

Удаления элемента может быть выполнено за , как и вставка, при использовании двухсвязного списка.

Двойное хеширование — метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.

Дата добавления: 2015-07-26; просмотров: 155; Нарушение авторских прав

Мы поможем в написании ваших работ!