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