Изменения

Каждая ячейка <tex>i</tex> массива <tex>H</tex> является указателем содержим указать на связный список(цепочку) пар ключ-значениеначало списка всех элементов, соответствующих одному и тому же хеш-значению значение ключакоторых равно <tex>i</tex>, иначе ячейка содержит значение <tex>NIL</tex>. Коллизии просто приводят к тому, что появляются списки длиной более размером больше одного элемента.

Операции поиска или удаления элемента требуют просмотра всех элементов соответствующему ему спискаВремя, чтобы найти необходимое для вставки в нем элемент с заданным ключомнаихудшем случае равно <tex>O(1)</tex>. Для добавления элемента нужно добавить Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в конец или начало соответствующего спискатаблице, ино если потребуется, то перед вставкой мы может выполнить поиск этого элемента.Время работы поиска в наихудшем случаепропорционально длине списка, а если коэффициент заполнения станет слишком великвсе <tex>n</tex> ключей хешированы в одну и ту же ячейку (создавая список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, увеличить размер массива что ничуть не лучше, чем использование связного списко для хранения всех <tex>n</tex> элементов.Удаления элемента может быть выполнено за <tex>HO(1)</tex> , как и перестроить таблицувставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>