Hashtable桶实现

Question

在我看到的每一个哈希表实现中，都会使用散列来选择一个“桶”，它是一个项列表，然后遍历该列表，直到找到我们想要的项为止。

我的问题是为什么它总是一张清单？据我所知，向量几乎总是更有效，那么为什么不使用向量作为桶呢？是否有一些列表的属性使它们成为哈希表中的一个桶？

这里我使用了向量的C++术语，但它确实适用于任何语言。

Answer 1

哈希表用于关注速度的地方。

与作为双链接列表实现的std::vector相比，在std::list中追加或删除元素要慢得多。

当向std::vector添加元素时，如果向量大小超过矢量容量，则所有元素都必须在内存中移动。在std::list中，只分配新元素的内存，必须调整最后一个元素的下一个指针。

从std::vector中删除元素时，所有后续元素都必须在内存中移动。在std::list中，只有prev和下一个指针必须进行调整。

可能是的另一个原因:如果使用std::list，元素将永远不会在内存中移动，并且一旦元素添加到映射中，就可以使用裸指针来寻址这些元素。当使用std：：向量时，如果调整了矢量的大小，并且所有裸指针都将被悬空，元素就会被移动。

OOT:另一种解决方案是根本不为桶使用列表:如果新元素将散列到位置7，并且这个位置已经被接受，那么新元素将被写入位置8 (an等)。如果哈希表几乎为空，则此解决方案非常快速；如果表已几乎满，则此解决方案非常慢。如果元素的数量超过了哈希表的大小，则必须对其进行调整和重新组织，这是一项非常昂贵的操作。