Java哈希表實現

Question

在我的哈希表實現中，我的哈希函數只需要我傳遞的項的值，調用hashCode（從Object類繼承），並以內部數組的大小爲模。這個內部數組是一個LinkedLists數組。現在，如果我的LinkedLists變得太長了（我的效率開始從O（1）滑到O（n）），我認爲僅僅增加數組的大小是有意義的。但這就是我的問題所在，因爲我聲明我散列了我傳遞的項目並以數組的大小（剛剛更改）爲模。如果我繼續，那麼哈希將不會指向數組中的不同索引，從而失去了引用哈希表中項目的能力？我怎麼能解決這個問題？

Answer 1

您需要每個項目的實際散列值，以便您可以將它們放入調整大小的表中正確的散列鏈中。 （否則，當你觀察到的，項目是容易最終在錯誤的鏈條，並沒有可定位的結果。）

有兩種方法來處理這個：

• 你可以只需在將其添加到新表格時重新計算每個項目的散列值即可。

• 您可以保留哈希鏈中每個項目的原始哈希值的副本。這是標準Java HashMap實現的功能......至少在我看過的版本中。

（後者是時間與空間的權衡，如果您的項目有一個昂貴hashcode方法可以還清大的時候。但是，如果分攤在哈希表的壽命，這種優化不會改變任何公共API方法的「大O」複雜性......假設您的哈希表調整大小是指數;例如，您每次大致將表大小加倍）。