В чем заключается худший случай для хеш-таблиц?

Question

[albertalexandrov]

Привет!

Пишут, что для хеш-таблиц худший случай для поиска, вставки и удаления - это О(n). В чем кроется этот худший случай? Перестройка индекса таблицы?

Answer 1

[GavriKos]

Вам пример? Это когда у всех элементов хеш совпадает - невозможно найти нужный элемент только по хешу и приходится искать вручную. Т.е. таблица грубо говоря становится обычным массивом.

Answer 2

[Teslaman]

При коллизиях (совпадении хэша) элементы обычно складывают в связный список. В поиске по этому связному списку и кроется O(n).