MasterZiv
mayton wrote:

> Не забывайте, что hashtable теряет свои свойства при резком приросте
> количества элементов. Его рекомендуют перестраивать с новой формулой
> хеширования. А это - накладные расходы.

Не обязательно при резком приросте.

Дело в том, что существуют разные стратегии т.н. " обработки
переполнений ", это когда несколько элементов таблицы имеет
один и тот же хэш-код. Так вот, они бывают разные, их порядка
нескольких десятков понапридумывали в своё время. Ну, и, соответсвенно,
не для всех критичен резкий прирост (статистически равномерно размазанный
по всей таблице).

Но вот для всех хэш-функций по определению критичны такие последовательности
ключей, в которых все элементы обладают одним и тем же значением
хэш-функции. И, соответственно, искусство пользования хэш-таблицей
заключается в том, чтобы подобрать хорошую для обрабатываемых ключей
хэш-функцию.



вопрос по хешам, можно ли при моих данных (10000000 элементов типа unsigned long) построить хешь который будет потреблять столько же памяти как и массив из 10000000 элементов unsigned long (ну или чуточку больше)?