哈希表桶实现
Hashtable bucket implementation
在我见过的每个散列 table 实现中，散列用于选择 "bucket" 这是一个项目列表，然后遍历该列表，直到找到我们想要的项目。
我的问题是为什么它总是一个列表？据我所知，矢量几乎总是更有效，那么为什么不使用矢量作为桶呢？是否有一些 属性 列表使它们非常适合用作散列中的存储桶 table？
我在这里使用的是向量的 C++ 术语，但它确实适用于任何语言。
散列 table 用于需要考虑速度的地方。
与 std::list 相比，在 std::vector 中添加或删除元素要慢得多，std::list 是作为双向链表实现的。
向 std::vector 添加元素时，如果向量大小超过向量容量，则必须在内存中移动所有元素。在std::list中，只为新元素分配内存，必须调整最后一个元素的下一个指针。
从 std::vector 中删除一个元素时，所有后续元素都必须在内存中移动。在 std::list 中，只需要调整 prev 和 next 指针。
可能是另一个原因：如果使用std::list，元素将永远不会在内存中移动，你可以使用裸指针来寻址元素，一旦它们被添加到地图。使用 std::vector 时，如果调整矢量大小，则元素将被移动，并且所有裸指针都将悬空
OOT：另一种解决方案是根本不对存储桶使用列表：如果新元素散列到位置 7 并且该位置已被占用，则新元素将写入位置 8（这样在）。如果 hashtable 几乎为空，则此解决方案非常快；如果 table 几乎已满，则此解决方案很慢。如果元素数量超过散列 table 大小，则必须调整大小并重新组织，这是一项非常昂贵的操作。
在我见过的每个散列 table 实现中，散列用于选择 "bucket" 这是一个项目列表，然后遍历该列表，直到找到我们想要的项目。
我的问题是为什么它总是一个列表？据我所知，矢量几乎总是更有效，那么为什么不使用矢量作为桶呢？是否有一些 属性 列表使它们非常适合用作散列中的存储桶 table？
我在这里使用的是向量的 C++ 术语，但它确实适用于任何语言。
散列 table 用于需要考虑速度的地方。
与 std::list 相比，在 std::vector 中添加或删除元素要慢得多，std::list 是作为双向链表实现的。
向 std::vector 添加元素时，如果向量大小超过向量容量，则必须在内存中移动所有元素。在std::list中，只为新元素分配内存，必须调整最后一个元素的下一个指针。
从 std::vector 中删除一个元素时，所有后续元素都必须在内存中移动。在 std::list 中，只需要调整 prev 和 next 指针。
可能是另一个原因：如果使用std::list，元素将永远不会在内存中移动，你可以使用裸指针来寻址元素，一旦它们被添加到地图。使用 std::vector 时，如果调整矢量大小，则元素将被移动，并且所有裸指针都将悬空
OOT：另一种解决方案是根本不对存储桶使用列表：如果新元素散列到位置 7 并且该位置已被占用，则新元素将写入位置 8（这样在）。如果 hashtable 几乎为空，则此解决方案非常快；如果 table 几乎已满，则此解决方案很慢。如果元素数量超过散列 table 大小，则必须调整大小并重新组织，这是一项非常昂贵的操作。