Какая сложность алгоритма у метода цепочек и метода открытой адресации?

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

В цепочках стоимость зависит от средней длины списка в бакете: порядка O(1 + α), где α — отношение элементов к бакетам. В открытой адресации при приближении загрузки к единице резко растёт число проб; важны стратегия пробирования и tombstones после удаления. Перехеширование стоит O(n), но распределяется по последовательности вставок амортизированно. Эти оценки предполагают разумное хеширование; дорогие сравнения ключей и злонамеренные коллизии добавляют собственную цену.