Хеширование методом цепочек

Согласно статье на вики:

Метод цепочек

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

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

При предположении, что каждый элемент может попасть в любую позицию таблицы H с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее время работы операции поиска элемента составляет Θ(1 + α), где α — коэффициент заполнения таблицы.