Здравствуйте, dilmah, Вы писали:

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

D>>>я понимаю, но в этом и состояло мое замечание, что часто приводимая псевдотеоретическая аргументация что доступ к хэштаблице O(1), а к дереву O(log N) -- эта аргументация лукава и имеет мало смысла. Фактически для хэштаблицы мы ограничиваем N сверху и говорим что доступ O(1), но если дереву ограничить N сверху то доступ к нему тоже O(1)
Здесь мне кажется я вас понял. Да, аргументация была псевдотеоретическая, а именно практическая, особенно случай автора со 100к ключами. Согласен, вы правы, мы ограничиваем сверху N и доступ O(1), но остается открытым вопрос как у дерева получилось O(1) даже если N ограничить сверху. Просто интересно, здесь действительно не понимаю

AF>>Мне кажется я вас не понимаю. Можете объяснить что такое N?
D>N -- это количество различных объектов, которое планируется хранить в дереве, либо хэш-таблице
все таки понял вас правильно