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