algorithm - 哈希表 : Search vs successor time complexity

Question

在Skiena's book of algorithm design ，鉴于哈希表最多可以有 m 个桶，元素总数为 n，观察到以下最坏情况下的时间复杂度:

搜索:O(n)

后继者:O(n + m)

为什么两者不同？查找后继者不也涉及搜索下一个元素吗？

Answer 1

哈希以破坏顺序为代价实现了恒定时间搜索。当我搜索一个元素时，我对其进行哈希处理 (O(1)) 并查看所选的存储桶 (O(n) 在最坏的情况下，如果我进行线性扫描，因为所有其他桶可能都是空的。)

当我想要给定元素之后的下一个元素时，我无法保证它会在同一个桶中。事实上，我根本不知道它在哪里。因为我还不知道继任者是什么，所以我无法对它进行散列以找到它的桶。相反，我被迫查看每个存储桶 (O(m)。)

如果我在扫描桶时按顺序探测项目，我最终也会对项目数量进行线性工作 (O(n))。这导致总复杂度为 O(n + m)。