с учетом идеальной хеш-функции, вычислять включение

Question

Учитывая отличную хеш-функцию по набору целых чисел S, можно вычислить включение целого числа в S, т. Е. Если целое число не находится в S, вы можете сказать, не прочитав из хеш-таблицу, и если целое число находится в S, вы можете сказать, не прочитав хеш-таблицу? Предположим, что мы имеем минимальную совершенную хеш-функцию. Таким образом, размер хеш-таблицы равен n, а размер S равен m, а n = m. Прошу прощения, если это очевидно.

Answer 1

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

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