Java中的單獨鏈接

Question

我們班正在學習散列表，我的一個學習問題涉及到使用具有單獨鏈接的散列表創建詞典。但是，問題在於我們不允許使用Java提供的方法來創建哈希表。相反，我們的講義注意到單獨的鏈接涉及數組中的每個單元格指向條目的鏈接列表。

因此，我的理解是我應該創建一個大小爲n的數組（其中n是素數），並向數組中的每個位置插入一個空鏈表。然後，我使用我的散列函數來散列字符串，並將它們插入到正確數組位置的相應鏈表中。我創建了我的散列函數，到目前爲止，我的字典構造函數需要一個大小，並創建一個這樣大小的數組（實際上，大小爲4999，無論是在課堂上討論的大小都是如此）。我在正確的軌道上嗎？我現在應該在每個位置插入一個新的鏈接列表，然後處理插入/刪除方法嗎？

Answer 1

你到目前爲止聽起來不錯。

請記住，默認情況下，對象引用數組的每個單元格都有每個單元格null，並且您可以編寫插入和刪除函數以使用該函數。如果您選擇創建不包含數據的鏈接列表對象（有時稱爲哨點節點），則創建單個不可變（只讀）實例以放入每個空槽是非常有利的，而不是創建4,999個單獨的實例與new（其中大多數不包含任何數據）。

Answer 2

這聽起來像你在正確的軌道上。

一些額外的指針：

• 不值得在創建每個桶一個LinkedList，直到它被實際使用。因此，您可以將這些存儲桶留空，直到它們被添加爲止。請記住寫入您的訪問函數來考慮這一點。
• 立即創建大型數組並不總是有效。從一個小陣列開始，跟蹤所用容量並在必要時放大該陣列（這涉及將這些值重新分組到新陣列）可能會更好一些
• 這是一個好主意，讓您的類實現整個Map<K,V>接口 - 只是爲了得到一些實踐其他標準Java收集方法的做法。