在grokking algorithms一书中，作者说
In the worst case, a hash table takes O(n)—linear time—for everything, which is really slow.
在最坏的情况下，我知道哈希函数会将所有键映射到相同的槽中，哈希表在该槽中启动一个链表来存储所有项目。所以对于搜索来说，这将花费线性时间，因为你必须一项一项地扫描所有项目。
我不明白的是，对于插入和删除，哈希表需要线性时间来执行。在最坏的情况下，所有项目都存储在指向链表的同一个槽中。而对于链表，删除和插入需要常数时间。为什么哈希表需要线性时间？
对于insert，hash table可以直接追加链表末尾的项吗？这将需要恒定的时间。
最佳答案
删除不会是常量:您必须访问整个最坏情况链表才能找到要删除的对象。所以这也是一个 O(n) 的复杂度。
您将遇到相同的插入问题:您不想要任何重复项，因此，为了确保不创建其中一些，您将必须检查整个链表。
关于python - 为什么在最坏的情况下插入和删除哈希表需要线性时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47738554/