哈希表 Ω(n^2) 运行时间？
Hash tables Ω(n^2) runtime?
我真的很困惑。读了课本，做了练习，还是不明白是怎么回事，遗憾的是我不能亲自去见教授，联系起来有点困难（暑期在线课程，不同的时区）。我觉得如果我只知道如何做这道题，它会 'click'。教科书分别详细介绍了哈希函数和运行时，但我觉得这个问题超出了我们所学的范围。如果有人能指出任何可能有用的东西，那就太好了。
1) 考虑将 m 键插入散列 table T[0..m − 1 的过程]，其中 m 是质数，我们使用开放寻址。我们使用的哈希函数是 h(k, i) = (k + i) mod m.举例m键 k1, k2 ... km，使得以下操作序列需要 Ω(n^2) 时间：
插入(k1), 插入(k2), ..., 插入(km)
我知道插入操作应该花费 O(1) 时间，或者在某些情况下，O(n)。我到底应该如何想出将其转换为 Ω(n^2) 时间的密钥？我希望能理解这一点，但我觉得我错过了一些重要的提示，因为教科书的章节看起来很简单，对我来说很有意义，但根本没有帮助。在问题中指出 m 是素数，这很重要吗？我只是迷路了，Google 这一次让我失望了。
这里的关键词是哈希冲突:
为了使哈希函数正常工作，您需要将特定输入的值均匀分布在存储条目的所有 m 个可能值中。如果哈希 table 具有与插入的元素一样多的条目，您可以期望每个元素都存储在（或接近）其哈希值（意味着只需要少量探测），从而使访问、插入和删除成为常量时间操作。
但是，如果您发现哈希函数每次都映射到相同值的不同输入值（冲突），则在插入期间，探测步骤将不得不跳过所有先前添加的元素，每次花费 Ω(n) 次元素平均。因此我们得到 Ω(n²)
的运行时间
我真的很困惑。读了课本，做了练习，还是不明白是怎么回事，遗憾的是我不能亲自去见教授，联系起来有点困难（暑期在线课程，不同的时区）。我觉得如果我只知道如何做这道题，它会 'click'。教科书分别详细介绍了哈希函数和运行时，但我觉得这个问题超出了我们所学的范围。如果有人能指出任何可能有用的东西，那就太好了。
1) 考虑将 m 键插入散列 table T[0..m − 1 的过程]，其中 m 是质数，我们使用开放寻址。我们使用的哈希函数是 h(k, i) = (k + i) mod m.举例m键 k1, k2 ... km，使得以下操作序列需要 Ω(n^2) 时间：
插入(k1), 插入(k2), ..., 插入(km)
我知道插入操作应该花费 O(1) 时间，或者在某些情况下，O(n)。我到底应该如何想出将其转换为 Ω(n^2) 时间的密钥？我希望能理解这一点，但我觉得我错过了一些重要的提示，因为教科书的章节看起来很简单，对我来说很有意义，但根本没有帮助。在问题中指出 m 是素数，这很重要吗？我只是迷路了，Google 这一次让我失望了。
这里的关键词是哈希冲突:
为了使哈希函数正常工作，您需要将特定输入的值均匀分布在存储条目的所有 m 个可能值中。如果哈希 table 具有与插入的元素一样多的条目，您可以期望每个元素都存储在（或接近）其哈希值（意味着只需要少量探测），从而使访问、插入和删除成为常量时间操作。
但是，如果您发现哈希函数每次都映射到相同值的不同输入值（冲突），则在插入期间，探测步骤将不得不跳过所有先前添加的元素，每次花费 Ω(n) 次元素平均。因此我们得到 Ω(n²)
的运行时间