Когда выбирается хэш-функция при универсальном хэшировании?
Я понял принципы универсального хэширования: как работает, для чего нужно, доказательства и т.д. Меня интересует вопрос реализации - когда эта функция хэширования выбирается?
Пример: я создаю хэш-таблицу (в ЯП) и начинаю вставлять в нее элементы. Эта хэш-функция выбирается каждый раз заново (при каждом вызове вставки) или единственный раз при создании этой хэш-таблицы?
Я предполагаю, что при создании этой хэш-таблицы, иначе на один и тот же ключ будут разные хэши. Но я нигде не могу найти примеры реализаций, а в текстах только доказательства корректности.
Существует несколько стратегий выбора хеш-функции. Наиболее простая стратегия состоит в том, чтобы в начале работы случайно выбрать хеш-функцию и не менять её вплоть до конца работы. Однако в этом случае производительность хеш-функции оказывается значительно ниже ожидаемой. Другая стратегия состоит в том, чтобы время от времени подсчитывать число коллизий и менять хеш-функцию, если это число значительно превышает ожидаемое. Такой подход обеспечивает хорошую производительность, при условии, что хеш-функция выбирается случайно
