Изменения

Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент Элементы вставляются в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>, учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно <tex>O(n)</tex>. Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем <tex>n</tex> ключей по <tex>m</tex> ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка <tex>n/m</tex> ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время <tex>O(1)</tex>. При использовании двусвязных списков удаление также может быть выполено за <tex>O(1)</tex>. (доказательство см. Т.Корман, второе издание, стр. 288)[[Файл:Hash_open.jpg|600px|thumb|center|описание]]