c++ - 哈希表桶实现

Question

在我见过的每个哈希表实现中，哈希用于选择一个“桶”，它是一个项目列表，然后迭代该列表，直到我们找到我们想要的项目。

我的问题是为什么它总是一个列表？据我所知， vector 几乎总是更有效，那么为什么不使用 vector 作为桶呢？列表是否有某些特性使其非常适合用作哈希表中的存储桶？

我在这里使用的是 vector 的 C++ 术语，但它确实适用于任何语言。

Answer 1

哈希表用于需要考虑速度的地方。

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

将元素添加到 std::vector 时，如果 vector 大小超过 vector 容量，则所有元素都必须在内存中移动。在 std::list 中，只有新元素的内存被分配，最后一个元素的 next-pointer 必须被调整。

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

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

OOT:另一种解决方案是根本不对存储桶使用列表:如果新元素散列到位置 7 并且该位置已被占用，则新元素将写入位置 8(依此类推) .如果散列表几乎为空，则此解决方案非常快，如果表几乎已满，则速度较慢。如果元素的数量超过哈希表的大小，则必须调整大小并重新组织，这是一项非常昂贵的操作。