這是我之前提出的一個問題，我發現我對如何實現unordered_map感到困惑。我敢肯定，其他許多人也會與我混淆。根據我不閱讀標準而知道的信息：每個unordered_map實現都將一個鏈接列表存儲到存儲桶數組中的外部節點上……不，這根本不是最通用的實現哈希映射的最有效方法。不幸的是，unordered_map規范中的一個小“疏忽”幾乎都需要這種行為。必需的行為是，元素的迭代器在插入或刪除其他元素時必須保持有效我希望有人可以解釋該實現及其與C ++標準定義的適應性（就性能要求而言），如果它確實不是實現哈希圖數據結構的最有效方法，則如何對其進行改進？
3 回答
慕萊塢森
TA貢獻1810條經驗 獲得超4個贊
我在上面的回復回答了您的第二條評論，但只是注意到我從未回答過您的第一條評論。關于“實際上，它的確會逐漸降低……從（例如）100％充滿到1000％充滿” –由于最大負載因數而不會發生–表的大小調整為100％。但是，您并不是在談論我提到的開放式散列的性能問題，這是當您擦除某個元素時，要么必須將存儲桶標記為已使用并繼續進行搜索（代價不菲） ），或將碰撞鏈“壓縮”到鏟斗中（較高的前期成本）。
- 3 回答
- 0 關注
- 373 瀏覽
添加回答
舉報
0/150
提交
取消