在Java中自定義實現HashTable？

我正在解決Quora problem和我的特殊解決方案，我需要一個散列表（long-keys，int-values）來緩存值。我希望Java HashMap可以得到改進，因爲我知道我的數據類型的鍵和值，它們是原語，也是我的問題空間。我決定天真地繼續使用「鏈表陣列」結構實現一個簡單的哈希表（甚至我的linkedList是我自己實現的Node類）。但我注意到，我自己的樸素實現比普通的Java HashMap慢大約4倍。我也嘗試使用Trove's LongToIntMap庫來查看它們的功能。有沒有人有任何好的建議來構建一個自定義的Long to Int哈希表，它明顯優於Java HashMap？在Java中自定義實現HashTable？

來源

2011-08-20 pathikrit

你是否分析了你的代碼，看看它花費了多少時間？在散列函數？附加鏈接列表？添加？查詢？ –

還記得Knuth的口頭禪：「過早優化是萬惡之源」。除非你有 - 或有理由懷疑 - 標準庫實現的問題，否則你可能不應該擔心。至少不是「過早地」;-) – paulsm4

看看Javolution的FastMap。源代碼可用here。

來源

2011-08-20 06:37:01 Behrang

我也嘗試使用Trove的LongToIntMap庫來查看它們的功能。

你試過看代碼，看看它們是如何做到的嗎？

無法確定地說出你在執行過程中做了什麼錯誤而沒有看代碼。然而，一種可能的改進可能是將LinkedList<Integer>替換爲使用int[]來表示列表的自定義「整數列表」類型。取決於你的散列表API，你應該能夠避免將你的值表示爲對象（特別是Integer s）的代價。（並且作爲推論，通過不執行具有用於鍵和/或值類型的通用類型的API，您將獲得更好的性能和空間利用率。）

對於什麼是值得的，可能導致窮人的一個錯誤性能忽略實施散列表大小調整。沒有調整大小，表上的get和put操作的複雜性將爲O(N)而不是O(1) ...，因爲哈希鏈長度將與哈希表條目的數量成比例地增長。

最後，您需要清楚自己是否在優化性能或空間利用率。最佳的解決方案將有所不同....

來源

2011-08-20 06:40:51

「...將是O（N）而不是O（N）...」，它仍然漸近地比O（N）快，我猜...： - ） – Dirk

@Dirk - 固定。（你知道我的意思是......） –

在Java中自定義實現HashTable？

回答

相關問題