關於使用HashMap和鏈接列表組合的LRU緩存設計

我有一個關於答案的問題。

說我的哈希映射表已滿（面試官給了我一個最大大小）[我明白如果我需要獲取已經存在的地圖對，我會將列表條目移到前面以指示最近的使用。]

但是，如果我有一個要添加的條目並且此密鑰散列到與另一個密鑰相同的位置，該怎麼辦。（碰撞）我該如何解決它？

做鏈接還是探測？如果我做鏈接，我應該增加地圖大小嗎？如果我刪除最舊的條目，它將清空我的哈希映射中的某個位置。但是一個新條目可能不會散列到這個位置？它可能會哈希到另一個完整的條目？（不同的鍵，值對）如何解決這個問題？

這不是完全獨立於LRU緩存中的使用，而僅僅是哈希映射的實現細節？ – delnan

是的，我也更新了標題。 – user1071840

這種設計將不包括鏈接，因爲我們在這裏設計一個直接映射高速緩存，這權衡已知的是，直接映射緩存僅考慮一個條目的近因然後將其從緩存中刪除，而不是被要求的頻率。

最大大小限制將施加在鏈接列表大小上，並且每當我們嘗試添加新條目時，鏈接列表已滿，鏈接列表中最後一次使用的條目和相應的映射條目被刪除。新條目要插入的位置與刪除的內容無關。

關於併發檢查的更多細節this鏈接。

2013-01-29 17:16:16 user1071840

LRU高速緩存上的不錯鏈接。 – raffian

map的大小是Map中存在的鍵值對的數量，因此它與鍵值對是否存在於同一個哈希桶中或不同。
所以如果你檢查hashmap的數據結構是它的鏈表的數組，那麼當有hash衝突時就存在鏈接和映射的大小也增加。
現在，如果您的新條目散列到不爲空的位置，則需要像鏈接列表中那樣鏈接。

PS：對於LRU高速緩存可以看到LinkedHashMap

2012-10-11 05:19:30 banjara

回答