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

D>>то что хэши O(1) это самообман.

D>а почему мне смайлики ставят? Поясните, что я написал смещного?
D>Один человек я еще понимаю -- пыхнуть мог, завидую. А у товарища Зудина зазудел стадный инстинкт?

Я, например, тоже смайлик поставил, не из-за стадного инстинкта, а потому что мне показалось что вы запутались. Рассуждаете правильно, но, по-моему, не совсем о том, о чем остальные участники. Если обидел — извините, по логике можно было ставить минус, потому что не согласен, но это тоже может оказаться еще обиднее.

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

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

> Если хэш и лучше, то он лучше именно на практике, а не теоретически.
Так в том и дело что его нужно правильно применять

> для N элементов необходима хэш-таблица размером K*N где K -- некая константа. Как ты понимаешь с ростом N настанет момент когда 32-битного хэша начнет не хватать. То есть с ростом N растет битность хэша, а значит и меняется операция хэширования.
Не надо все в одну кучу, в общем случае на ходу ни размер хэш таблицы, ни битность хэша не меняется. Когда не хватает битности, делаем хэш таблицу меньшего размера (уменьшаем К) и опять всего хватает, либо увеличиваем битность хэша, но это ведь не делается в рамках одной операции. Сложность оценивается для операций вставки, чтения, когда хэш таблица сконфигурирована: битность, размер таблицы константны.