AF>зачастую на практике да — самообман, но не всегда, а при определенных условиях. Вообще сложность О(1) относится к случаю так называемого perfect hash, когда отсутствуют коллизии, если коллизии встречаются, но очень редко, сложность все еще можно считать O(1)

ну, тут мне кажется что ты сам еще не осознал до конца всего волшебства хэшей Оставим в стороне perfect hash.
Если хэш просто достаточно хорош, чтобы быть похожим на случайный, то в этом случае если сделать размер хэш-таблицы в КОНСТАНТУ (скажем, 3) (не в логарифм, а именно всего лишь в константу) раз больше чем количество элементов которых нужно захэшировать, то из легкого упражнения по теории вероятностей будет следовать что коллизий будет O(1), а это и означает, что доступ будет O(1).

Вообще, если человек сам не проделал это упражнение по теории вероятностей, я не поверю что он до конца понял волшебство хэш-таблиц


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

AF>Мне кажется я вас не понимаю. Можете объяснить что такое N?

N -- это количество различных объектов, которое планируется хранить в дереве, либо хэш-таблице