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