这是一个家庭作业问题，但我认为它缺少一些东西。它问：
提供一个由m个键组成的序列来填充一个使用线性探测实现的哈希表，从而使填充它的时间最短。
进而
提供另一个m键序列，但要使填充它的时间最大。如果哈希表实现二次探测，重复这两个问题
我只能假设哈希表的大小为m，既因为它是唯一给出的数字，又因为我们在描述负载因子之前一直使用该字母来解决哈希表大小。但是如果不知道将序列散列到表中的散列函数，我想不出任何序列来做第一个。
如果它是一个糟糕的哈希函数，例如，它将每个条目哈希到同一个索引，那么填充它的最小和最大时间都将花费 O(n) 时间，而不管序列是什么样的。在平均情况下，我假设散列函数没问题，我怎么知道该散列函数填充表需要多长时间？
这些问题与散列函数的关联是否比与散列序列的关联更强？
至于第二个问题，我可以假设，不管散列函数如何，一个大小为m且具有相同键重复m次的序列将提供最大时间，因为它将导致从第二个条目开始的线性探测。我认为这需要 O(n) 时间。那是对的吗？
这个问题听起来并不十分关心散列函数，但如果有的话就好了。不过，你似乎几乎明白了。在我看来，这个问题更关心“你知道最坏情况下的键列表是什么吗？” 而不是“你知道如何利用糟糕的哈希函数吗？”
显然，如果你想出一个所有条目散列到不同位置的序列，那么你总共有 O(1) 次插入 O(m) 时间。
对于您所说的将所有键散列到同一位置的内容，如果这是您的建议，则每次插入都应采用 O(n)。但是，这并不是插入所有元素的总时间。此外，您可能要考虑不要从字面上一遍又一遍地使用相同的键，而是使用会在表中产生相同位置的键。我认为，按照惯例，插入相同的密钥应该会导致替换，尽管我不是 100% 确定。
如果我提供太多信息或留下任何不清楚的地方，我会提前道歉。这个问题似乎很简单，除了实际上不知道哈希函数的部分之外，如果不回答整个问题，很难说太多。
好吧，这些问题背后的想法是测试你对探测风格的理解。对于线性探测，如果发生碰撞，您只需测试下一个单元。它会一直这样下去，直到你找到一个可用的单元格来存储你的数据。您的哈希表不需要大小为 m，但它必须是at least size 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)。（我没有解决它，只是我有根据的猜测。）