统一哈希函数

哈希表基础知识： - 主要测试即将进行。我们将不胜感激所有帮助。

我基本上对密钥的统一散列有点困惑。

----------------------
| X X X                    <=== Chains; X represents an item in there
----------------------
| X X X                    <=== Multiple X represents collisions
---------------------- 
| 
----------------------
| X X X
----------------------
| X
----------------------

1. 考虑上述哈希表的情况，其中 M = 5（行数）且总长度为 10。我如何知道这个哈希表是否是统一哈希的？

2. 如果对一组键进行统一散列，这是否意味着散列表中的链内的列表（也称为由于冲突而产生的链表）具有相同的长度？或者说是平均数的意思？

3. 如果对键进行统一哈希，这是否意味着该哈希表的查找和删除函数为 O(1)（摊销），纯复杂度为 O(n/M)，其中 M 是链的总数？

4. 负载因子或 (N/#ofChains) 是否确定哈希的均匀性？

我希望你能帮我解答这些问题。我的教授在课堂上提出了很多概念，我基本上只是在这里将它们组合在一起，当我将这些概念放在一起时，我感到很困惑。

我在网上搜索更多信息来研究这个概念，我看到了一组幻灯片，如下所示。如果你的话我将不胜感激可以向我解释第二张幻灯片中的方程式相对于密钥的统一散列意味着什么.

另外，当他们说“映射到每个插槽的键数量相等”时，这是什么意思？是否可以说上面显示的我的哈希表没有统一哈希？

谢谢

幻灯片讨论了键的所有可能值。重要的是要认识到，在哈希图中，在任何给定时间都只有键的子集。无论您的哈希函数有多好，您可能会因为这些键映射到存储桶而感到幸运，也可能不会。

1）考虑上述哈希表的情况，其中M = 5（行数）且总长度为10。我如何知道这个哈希表是否是统一哈希的？

统一哈希是哈希函数的属性，而不是哈希表的属性。因此，仅仅通过查看哈希表的内容，是不行的。您必须查看哈希函数本身才能确定它是否统一。

2）如果对一组键进行统一散列，这是否意味着散列表中链内的列表（也称为由于冲突而产生的链表）具有相同的长度？或者说是平均数的意思。

就是平均的意思。

3) 如果对键进行统一哈希，这是否意味着该哈希表的查找和删除函数为 O(1)（摊销），纯复杂度为 O(n/M)，其中 M 是链的总数。

除了哈希函数的属性之外，复杂性还取决于负载因子。如果桶的数量随着元素的数量线性增长，你会得到O(1)平均查找和删除（只要您适当地摊销重新分桶）。