Изменения

Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Процедура вставки выполняется очень быстро, потому что предполагается, что вставляемый элемент отсутствует в таблице. При необходимости это предположение использовании двусвязных списков удаление также может быть проверено путем проведения поиска перед вставкойвыполено за <tex>O(1)</tex>. (доказательство см. Т. Время работы поиска в наихудшем случае пропорционально длине спискаКорман, второе издание, стр.288)