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