Основы универсального хеширования, как обеспечить доступность

Question

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

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

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

Answer 1

Универсальная хеш-функция - это семейство различных хеш-функций, обладающих свойством, что с высокой вероятностью два случайно выбранных элемента из вселенной не будут сталкиваться независимо от того, какая хеш-функция выбрана. Как правило, это достигается тем, что реализация выбирает случайную хеш-функцию из семейства хеш-функций для использования внутри реализации. Как только эта хеш-функция выбрана, хеш-таблица работает как обычно - вы используете эту хеш-функцию для вычисления хеш-кода для объекта, а затем помещаете объект в соответствующее место. Хеш-таблица должна помнить выбор сделанной ею хеш-функции и должна использовать ее последовательно во всей программе, так как в противном случае (как вы заметили) она забудет, где она отображала каждый элемент.

Надеюсь, это поможет!