Хэш-таблица без разрешения коллизий?

Question

[Имя]

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

Comments

[Akina]

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

Конечно нет.

Допустим, такая функция существует. Рассмотрим предельный вариант - количество хэшируемых значений превысило количество уникальных значений хэша. Очевидно, что на таком массиве гарантированно имеется коллизия. Противоречие. То есть предположение о существовании такой функции - ложно.

Иными словами, требование "количество значений хэша больше количества существующих хэшируемых значений", является обязательным.

[Имя]

Akina, ну этот случай само собой очевиден, я же написал, что таблица будет своевременно увеличиваться, и я так-же не собираюсь иметь uint32_max значений.

Если таблицу расширять заранее, например когда кол-во имеющихся элементов занимает 75%, то можно ли тогда подобрать такую функцию, которая позволит избежать коллизий вовсе?

[Akina]

можно ли тогда подобрать такую функцию, которая позволит избежать коллизий вовсе?

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

[Vitsliputsli]

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

Answer 1

[Wataru]

Нет. Ну, только если вы не будете заводить таблицу на 4 миллиарда с копейками элементов (2^32) и использовать тривиальную хеш-функцию.

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

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