Обсуждали тут с коллегой за утренним кофе такую структуру данных как хеш. В процессе родилась задачка. Пусть есть хеш-таблица на 1000 ключей. В нее занесли n значений (n > 1000). В среднем на каждый ключ будет приходиться по n / 1000 коллизий. Значит, среднее время поиска значения будет O(1) + O(n / 1000) = O(n). Однако всем известно, что время поиска в хеш-таблице константа, т.е. O(1). Вопрос: где ошибка в рассуждениях?
А какой же ответ на эту задачу?
Да ответ простой. Если n сравнимо с 1000, то n/1000 сравнимо с единицей и получаем искомое O(1). Если n много больше 1000, то мы имеем переполненный хеш с большим количеством коллизий, и поиск в нем будет действительно линейным. Фактически хеш в этом случае вырождается в список.