散列 Table 与链接搜索时间？
Hash Table With Chaining Search Time?
如果我实现一个散列 table，我知道插入是在常数时间内完成的。我也明白，如果没有碰撞，我可以在恒定时间内找到物品。但是，如果我插入一个项目并使用某个任意索引中的链接列表将其链接起来，它最终位于位置 2，但它链接到列表下方的 3 个链接，这是 O(n) 时间，用于搜索吗？
这是对O(n)时间的误解。 Big-O 分析与一般情况有关，而不是特定情况。直观地，想想你的哈希 table 随着时间的推移进行数千或数百万次查找，然后退后一步，判断它是否在做哈希 table 应该做的事情。
如果你有一个完全退化的散列 table 将所有内容散列到同一个槽中，你将拥有 O(n) 查找性能。
如果 n >> m，其中 n 是存储的元素数，m 是散列的大小 table，您的散列 table 查找性能将降低到 O(n)。
一般来说，哈希 table 的性能与 平均 链长有关。如果这个平均值是一个（小的）常量，那么它 不是 n 的函数，那么你就有了想要的 O(1) 查找性能。
如果我实现一个散列 table，我知道插入是在常数时间内完成的。我也明白，如果没有碰撞，我可以在恒定时间内找到物品。但是，如果我插入一个项目并使用某个任意索引中的链接列表将其链接起来，它最终位于位置 2，但它链接到列表下方的 3 个链接，这是 O(n) 时间，用于搜索吗？
这是对O(n)时间的误解。 Big-O 分析与一般情况有关，而不是特定情况。直观地，想想你的哈希 table 随着时间的推移进行数千或数百万次查找，然后退后一步，判断它是否在做哈希 table 应该做的事情。
如果你有一个完全退化的散列 table 将所有内容散列到同一个槽中，你将拥有 O(n) 查找性能。
如果 n >> m，其中 n 是存储的元素数，m 是散列的大小 table，您的散列 table 查找性能将降低到 O(n)。
一般来说，哈希 table 的性能与 平均 链长有关。如果这个平均值是一个（小的）常量，那么它 不是 n 的函数，那么你就有了想要的 O(1) 查找性能。