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

В чём заключается подход

The only effective way to improve the situation is to choose the hash function randomly in a way that is independent of the keys that are actually going to be stored.

This approach is called random hashing. A special case of this approach, called universal hashing, can yield provably good performance on average when collisions are handled by chaining.

Как реализовать

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

Для каждого universe ключей у нас будет своя семья хэш-функций, которые превращают их в числа от 0 до m-1.

<aside> ℹ️ Every independent uniform random family of hash function is universal, but the converse need not be true: not every universal family of hash function is independent uniform random.

</aside>