这是一个家庭作业问题，但我认为其中遗漏了一些东西。它询问:
Provide a sequence of m keys to fill a hash table implemented with linear probing, such that the time to fill it is minimum.
然后
Provide another sequence of m keys, but such that the time fill it is maximum. Repeat these two questions if the hash table implements quadratic probing
我只能假设哈希表的大小为m，既因为它是唯一给出的数字，又因为我们在描述负载因子之前一直使用该字母来解决哈希表的大小。但如果不知道将序列哈希到表中的哈希函数，我就无法想到任何序列来执行第一个操作。
如果它是一个糟糕的哈希函数，例如，它将每个条目哈希到同一索引，那么填充它的最小和最大时间都将花费 O(n) 时间，无论序列看起来如何喜欢。在一般情况下，我假设哈希函数没问题，我怎么知道该哈希函数填满表需要多长时间？
这些问题与哈希函数的联系是否比与哈希序列的联系更强？
对于第二个问题，我可以假设，无论哈希函数如何，大小为 m 且相同 key 重复 m 次的序列将提供最大时间，因为它将导致从第二个条目开始线性探测。我认为这将花费 O(n) 时间。这是正确的吗？
最佳答案
嗯，这些问题背后的想法是测试您对探测风格的理解。对于线性探测，如果发生碰撞，您只需测试下一个单元即可。如此继续下去，直到找到可用的单元格来存储数据。
您的哈希表的大小不需要为 m，但它需要至少为 m。
第一个问题是，如果你有一个完美的哈希函数，填充表的复杂度是多少。完美的散列函数对每个元素进行寻址而不会发生冲突。因此，对于 m 中的每个元素，您需要 O(1) 时间。总复杂度为 O(m)。
第二个问题是要求 hash(X)=cell(0) 的情况，所有元素将搜索到第一个空单元格(就在当前填充的表格的后面)。
对于第一个元素，您探测一次 -> O(1)
对于第二个元素，您探测两次 -> O(2)
对于第 n 个元素，您探测 n 次 -> O(n)
总共有 m 个元素，所以 -> O(n*(n+1)/2)
对于二次探测，您有相同的策略。最小情况是相同的，但最大情况将具有 O(nlogn)。 (我没有解决这个问题，这只是我有根据的猜测。)
关于hashtable - 填充哈希表的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11277694/