这是一个家庭作业问题,但我认为它缺少一些东西。它要求:
提供一个m键序列来填充用线性探测实现的哈希表,这样填充它的时间是最小的。
然后
提供另一个m键序列,但使填充时间是最大的。如果哈希表实现二次探测,则重复这两个问题。
我只能假设哈希表的大小为m,这既是因为它是给定的唯一数字,也是因为在描述负载因子之前,我们一直使用该字母来寻址哈希表大小。但是,如果不知道散列函数将序列散列到表中,我就想不出要执行第一个序列了。
如果它是一个糟糕的散列函数,例如,它将每个条目散列到相同的索引中,那么填充它的最小和最大时间都将花费O(n)时间,而不管序列是什么样子。在一般情况下,假设哈希函数没有问题,我怎么知道这个哈希函数填充表需要多长时间?
这些问题不是比散列函数更强的哈希函数吗?
至于第二个问题,我可以假设,不管哈希函数是什么,大小为m的序列具有相同的密钥重复m次将提供最大的时间,因为它将导致从第二项开始的线性探测。我想那需要时间。对吗?
发布于 2012-07-02 17:50:15
嗯,这些问题背后的想法是测试你对探索风格的理解。对于线性探测,如果发生碰撞,只需测试下一个单元格。直到你找到一个可用的细胞来存储你的数据。您的哈希表不需要大小为m,但它需要是at least size m。
第一个问题是,如果您有一个完美的散列函数,那么填充表的复杂性是什么?完美的散列功能可以在不发生冲突的情况下处理每个元素。因此,对于m中的每个元素,您需要O(1)时间。总复杂度为O(m)。
第二个问题是询问散列(X)=cell(0)的情况,所有元素都将搜索到第一个空单元格(仅是当前填充表的尾部)。
对于第一个元素,只需探测一次-> O(1)
对于第二个元素,您可以探测两次-> O(2)
对于第n个元素,你探测n乘以-> O(n)
总的来说,您有m个元素,所以-> O(n*(n+1)/2)
对于二次探测,您有相同的策略。最小的情况是相同的,但最大的情况将有O(nlogn)。(我没有解决这个问题,只是我有根据的猜测。)
发布于 2012-07-02 17:14:53
这个问题听起来并不是非常关心哈希函数,但最好有这样的问题。不过,你似乎差不多明白了。在我看来,这个问题更关心的是“你知道最坏的钥匙清单会是什么吗?”而不是“你知道如何利用坏的哈希函数吗?”
显然,如果您想出了一个序列,其中所有条目都散列到不同的位置,那么O(1)插入的时间总共是O(m)。
对于您所说的对同一位置的所有键进行散列,如果这是您所建议的,则每个插入都应该使用O(n)。但是,这并不是插入所有元素的总时间。另外,您可能需要考虑的不是一遍又一遍地使用相同的键,而是使用会在表中产生相同位置的键。我认为,按照惯例,插入相同的键会导致替换,尽管我不能百分之百肯定。
如果我提供太多的信息或留下任何不清楚的信息,我会提前道歉的。这个问题看上去相当枯燥,除了关于不真正知道哈希函数的部分,如果不回答整个问题,就很难说出很多话来。
https://stackoverflow.com/questions/11277694
复制相似问题