2

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

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

----------------------
| 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) 是否识别散列的一致性？

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

我在网上搜索更多关于这个概念的研究，我看到了一组幻灯片，如下所示。如果您能向我解释第二张幻灯片中与键的统一散列相关的等式的含义，我将不胜感激。

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

在此处输入图像描述

谢谢

4

1 回答 1

4

幻灯片正在讨论键的所有可能值。重要的是要意识到在您的哈希图中，您在任何给定时间都只有一个键子集。不管你的散列函数有多好，你可能很幸运这些键映射到桶，或者你可能不是。

1）考虑上述哈希表的情况，其中 M = 5（行数）且总长度为 10。我怎么知道这是哈希表是否均匀散列？

均匀散列是散列函数的属性，而不是散列表的属性。因此，仅仅通过查看哈希表的内容，是做不到的。您必须查看哈希函数本身以确定它是否是统一的。

2）如果一个人对一组键进行统一散列，这是否意味着哈希表中链内的列表也就是由于冲突而导致的链表具有相同的长度？或者它的意思是平均值。

这意味着平均。

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

除了散列函数的属性外，复杂度还取决于负载因子。如果存储桶的数量在元素数量中线性增长，则O(1)平均会找到并删除（只要您适当地摊销重新存储桶）。

于 2012-12-12T11:14:42.263 回答