根据 Universal Hashing 的定义，选择一个随机哈希函数以获得良好的最坏情况保证。但我无法理解它是如何工作的。
假设如果我选择一些随机哈希函数 h ，仍然有可能以最差的元素集结束。
请用简单的语言解释。
我看过视频https://www.youtube.com/watch?v=s7QSM_hlS1U .但是很难理解
最佳答案
你是对的:使用随机哈希函数并不能 100% 防止你以最坏情况集结束。但是在您提供的讲座中，主要担心的是敌人可能能够预测总是屈服于最坏情况的输入。
作为一个例子，他使用了一个必须为您的哈希表选择基准的竞争对手。在运行时不使用随机散列函数，他会知道你使用的散列函数，并且可以预测哪些键会产生相同的散列值，从而将散列表转换为链表(因为每个键都分配给同一个桶) .确定性哈希函数具有可预测的最坏情况结果的风险，这在对手环境中尤其糟糕。
通过在运行时使用随机哈希函数，即使敌人选择了基准，你也有一定的概率保证不会发生碰撞。 更具体地说，当你有值 x 和 y(其中 x != y)并且你从 m 个不同的哈希函数 H 中选择一个函数 h，那么(非常直观地)h(x) = h(y) 是 AT 的概率LEAST 小于 1/m，即 1/m 设置概率上限。确定性哈希函数无法为您提供此属性。
另见 here
关于algorithm - 为什么我们在Universal Hashing中选择随机哈希函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28266176/