AF>Может быть я действительно не до конца понял волшебство хэш-таблиц, но я вообще то всегда рассматривал конкретные, заранее просчитанные случаи использования хэш-таблиц. Широко известный факт, то что сложность доступа к таблице в общем случае варьируется от O(1) до O(N). И я приводил пример что если вычисление хэша это каждый раз коллизия, то будет O(N), думаю при желании и "правильной" реализации таблицы можно и больше. Вопрос в том что когда осознанно выбирают хэш-таблицы, стремятся сделать именно O(1) под конкретный случай, иначе зачем вообще хэш-таблица. Насколько я понял вы вели речь про какую то идеальную, безразмерную хэш-таблицу на все случаи жизни, правильно?

Я вел речь об обычной хэш-таблице, размер которой в несколько раз превышает количество объектов которые в ней хранят.
И я вел речь о хэш-функциях, которые на имеющихся данных ведут себя как случайные.
Эта случайность хэш-функции гарантирует, что матожидание (т.е. среднее ожидаемое) количество объектов попавших в одно значение хэш-функции будет O(1).

AF>Согласен, вы правы, мы ограничиваем сверху N и доступ O(1), но остается открытым вопрос как у дерева получилось O(1) даже если N ограничить сверху. Просто интересно, здесь действительно не понимаю

Все эти O(1), O(N), O(N^2) это характеристики поведения функции на бесконечности, а не на ограниченном интервале.
С точки зрения чистых теоретиков любое ограниченное число является O(1). Таким образом для теоретика если N ограничено, то и log(N) и даже N^3 и exp(N) являются O(1)