使用通用哈希
Use of universal hashing
我正在阅读 Cormen 的书，试图了解通用哈希相对于普通哈希的有用性，除了函数每次都是随机生成的。
根据我对通用哈希的理解，我们选择的函数是
H(x)=[(ax+b)mod p]mod m
p是一个比所有key都大的质数，m是数据的大小table，a,b是随机数。
因此，例如，如果我想读取 80 个人的 ID，并且每个 ID 的值都在 [0,200] 之间，那么 m 将是 80，p 将是 211（下一个质数）。正确的？
我可以使用函数让我们说
H(x)=[(100x+50)mod 211]mod 80
但这为什么会有帮助？很有可能我最终会无缘无故地占用 table 的很多空槽。降低数字 m 以获得更小的 table 以便 space 没有理由不被使用不是更有用吗？
感谢任何帮助
我认为回答您问题的最佳方法是从您用于计算哈希码的公式的细节中抽象出来，并更多地考虑，一般来说，改变大小的影响是什么哈希值 table.
您正在考虑调整的参数 m 会调整散列中的槽数 table。假设您计划将 n 项放入哈希 table。比率 n / m 称为散列 table 的 负载因子 ，通常用字母 α 表示。
如果您的 table 具有高负载系数（大 α，小 m），那么您在 table 中的浪费会减少 space。但是，您也会增加执行查找的成本，因为将大量对象分布到一个小的 space 中，您可能会遇到一堆需要时间才能解决的冲突。
另一方面，如果您的 table 具有低负载系数（较小的 α，较大的 m），那么您会降低发生冲突的可能性，因此会降低执行查找的成本。然而，如果 α 变得太小——比如说，你实际存储了每个元素 1,000 个槽——那么你就会有很多浪费 space.
制作良好哈希的工程方面的一部分 table 是弄清楚如何在这两个选项之间取得平衡。查看哪些有效，哪些无效的最佳方法是提取分析器并测量 α 的变化如何改变您的运行时间。
我正在阅读 Cormen 的书，试图了解通用哈希相对于普通哈希的有用性，除了函数每次都是随机生成的。
根据我对通用哈希的理解，我们选择的函数是
H(x)=[(ax+b)mod p]mod m
p是一个比所有key都大的质数，m是数据的大小table，a,b是随机数。
因此，例如，如果我想读取 80 个人的 ID，并且每个 ID 的值都在 [0,200] 之间，那么 m 将是 80，p 将是 211（下一个质数）。正确的？ 我可以使用函数让我们说
H(x)=[(100x+50)mod 211]mod 80
但这为什么会有帮助？很有可能我最终会无缘无故地占用 table 的很多空槽。降低数字 m 以获得更小的 table 以便 space 没有理由不被使用不是更有用吗？
感谢任何帮助
我认为回答您问题的最佳方法是从您用于计算哈希码的公式的细节中抽象出来，并更多地考虑，一般来说，改变大小的影响是什么哈希值 table.
您正在考虑调整的参数 m 会调整散列中的槽数 table。假设您计划将 n 项放入哈希 table。比率 n / m 称为散列 table 的 负载因子 ，通常用字母 α 表示。
如果您的 table 具有高负载系数（大 α，小 m），那么您在 table 中的浪费会减少 space。但是，您也会增加执行查找的成本，因为将大量对象分布到一个小的 space 中，您可能会遇到一堆需要时间才能解决的冲突。
另一方面，如果您的 table 具有低负载系数（较小的 α，较大的 m），那么您会降低发生冲突的可能性，因此会降低执行查找的成本。然而，如果 α 变得太小——比如说，你实际存储了每个元素 1,000 个槽——那么你就会有很多浪费 space.
制作良好哈希的工程方面的一部分 table 是弄清楚如何在这两个选项之间取得平衡。查看哪些有效，哪些无效的最佳方法是提取分析器并测量 α 的变化如何改变您的运行时间。