我知道您保留這些專案，并在使用線性探測在 HashMap 中洗掉它們時將它們標記為已洗掉。但是，當您調整 HashMap 的大小時，您是否也添加了已洗掉的專案？
uj5u.com熱心網友回復：
如果您在可調整大小的哈希表中使用這種線性探測，您應該對通常的調整大小規則進行一些更改。
請記住，目標是：
- 維持每個操作的預期攤銷 O(1) 成本
- 永遠不要使用少于四分之一（例如）的桌位
- 永遠不要使用超過一半（例如）的桌子插槽
因此，當表格填滿時（在本例中為 1/2 個插槽），您調整大小，然后：
- 新表的大小應該是4N，其中N是表中未洗掉的專案數。
- 只復制未洗掉的專案。這將使您的插槽中正好有 1/4 已滿。
具有 N 個未洗掉項的調整大小需要 O(N) 時間，并且每次調整大小后至少需要 N 個操作才能到達下一個，這提供了我們需要的每個操作的 O(1) 分攤預期時間。
如果您的實作需要 2 的冪或質數表大小，那么您可以選擇最接近 4N 的一個或下一個更大的一個。
uj5u.com熱心網友回復：
有一個技巧可以輕松調整 HashMap 的大小——不要調整它的大小。相反，讓您的 resize() 方法執行以下操作：
- 創建第二個 HashMap，用比當前更大的內部陣列初始化（兩倍大是好的）
- 迭代當前 HashMap 的內容，使用 HashMap 的常規
put(key,value)方法（或您呼叫的任何方法）將當前 HashMap 中的每個鍵值對插入到新創建的 HashMap 中。（由于您新創建的 HashMap 的內部陣列比您當前的陣列大得多，因此可以保證適合而無需進一步調整大小） - 交換當前 HashMap 和更新/更大的 HashMap 的內容（如果您已將 HashMap 的內容分配為單獨的堆物件，這就像單個指標交換一樣簡單）
- 就是這樣; 現在您的原始 HashMap 被調整得更大，您不必撰寫任何額外的調整大小邏輯來執行此操作，因為您重新使用了您已經實作的邏輯。現在可以丟棄第二個 HashMap（現在包含較舊/較小的內部陣列）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362056.html
下一篇：為BST實作Add方法