使用線性探測的C++集？

Question

是否有類似於使用線性探測的unordered_set的數據結構？這樣的數據結構不會利用緩存命中嗎？如果是這樣，爲什麼unordered_set使用鏈接鏈接？

Answer 1

標準庫關聯容器不能使指針或對元素的引用無效（當然，除非它們被擦除）。因此，線性探測不會提供更多好處：元素需要分配在陣列外部以支持調整陣列大小。一旦元素不是數組的一部分，鏈接它們似乎可以更好地控制碰撞。

Answer 2

該方法允許對存儲對象的引用保持有效，即使在重做和迭代器在大多數操作後也保持有效。另一方面，希望散列表包含匹配散列的單個元素纔有效 - 否則無論如何不會使用如此有效的線性搜索。