如何存儲幾百萬高速緩存，然後跟蹤20最老的高速緩存

我有一個採訪問題，說我需要存儲幾百萬高速緩存，然後我需要保持一個跟蹤20年前最早的高速緩存，並儘快緩存集合增加，將最舊的20個緩存替換爲下一個最早的緩存集。如何存儲幾百萬高速緩存，然後跟蹤20最老的高速緩存

我回答，以保持一個HashMap吧，問題又來了增加如果我們想訪問任何元素對HashMap的快速度，怎麼辦，所以我告訴它的地圖，訪問不會被時間但採訪者並不滿意。那麼這樣的情景應該是什麼樣的閒置方式。

2012-05-03 Abhishek Choudhary

您的面試官似乎在描述一個[LRU緩存]（http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used），它似乎沒有任何微不足道的實現。應該讓有趣的學習... – maerics

A queue非常適合查找和刪除最舊的成員。

實現爲雙向鏈表的隊列在兩端都有O（1）插入和刪除。

A priority queue有助於給隊列中不同的項目賦予不同的權重（例如，某些隊列元素可能比其他隊列重新創建更昂貴）。

您可以使用一個哈希表來保存實際元素，並迅速找到它們基於哈希鍵，哈希鍵隊列追蹤緩存元素的年齡。

來源

2012-05-03 04:50:56

它意味着保持一個獨立的隊列，將保持20個最古老的Map？的參考，但是在Map中是數百萬記錄的存儲是高效的事情要做 –

沒有...有一個持有對所有緩存元素的引用的隊列。基於散列鍵查找元素的映射非常有效，但是根據搜索條件（如時間戳）查找元素的效率非常低。該隊列只能保存散列鍵...使用隊列根據年齡排隊和出隊元素，並使用散列映射來保存實際對象。 –

通過使用隊列的雙鏈表以及維護元素的哈希映射，您應該可以創建支持最大大小（甚至是LRU緩存）的緩存。這應該導致引用的對象被存儲3次而不是對象被存儲兩次，如果你實現了這個功能，一定要檢查這個（避免這種情況的一個簡單方法是隻對散列鍵進行排隊）

當檢查對於溢出，只需將最後一個項目從隊列中彈出，然後將其從散列映射中刪除即可

訪問項目時，可以使用散列映射查找緩存項目。然後，如果你正在實現一個LRU緩存，你只需將它從隊列中移出並添加回到開頭即可。

通過使用此結構插入，更新，讀取，刪除都將是O(1)。

下面的問題是面試官要求物品具有隨每個緩存物品而變化的生存時間（TTL）的能力。爲此，您需要有另一個隊列來維護按生存時間排序的項目，這裏唯一的問題是插入現在變爲O(n)，因爲您必須掃描TTL隊列並找到過期點，所以您必須決定是否將TTL隊列存儲爲n樹的內存使用情況值得（因此產生O(log n)插入時間）。或者你可以在每個〜1分鐘的時間間隔或類似情況下將你的TTL隊列實現爲桶，你會得到〜O(1)插入仍然會稍微但不是很大（並且它是一個後臺進程）降級到期後臺進程的性能。

來源

2012-05-03 09:04:33 Seph

如何存儲幾百萬高速緩存，然後跟蹤20最老的高速緩存

回答

相關問題