我有一個軟件項目，可以根據不同大小的對象創建一系列指紋（哈希）值。對象大小越大，當然散列計算的代價越高。哈希用於比較目的。緩存項替換算法
我現在希望緩存哈希值以提高後續比較的性能。對於在緩存中的任何給定的條目，我已經準備好以下指標：
所以對我的問題。考慮到需要限制高速緩存的大小（將其限制爲特定數量的條目），取代高速緩存項目的平衡方法是什麼？
顯然，較大的對象哈希值較高，因此需要儘可能長時間地保留它們。但是，我想避免使用大量大對象填充緩存的情況，以防止未來（較小）的項目被緩存。
因此，根據我可用的度量標準（請參閱上文），我正在尋找一個很好的通用「公式」，用於在緩存變滿時過期（移除）緩存條目。
所有的想法，意見都表示讚賞。
您需要考慮對象的性質。想想對象很快被再次調用的可能性。並刪除最不可能的對象。
這對於您使用的軟件以及對象的性質非常具體。
如果他們在程序中連續使用，他們可能會遵守Locality of reference原則。所以你應該使用LRU（最近最少使用）算法。
如果命中數更高的對象更有可能再次被調用，那麼使用它（並刪除最低）。
原則上，你需要計算：
分鐘（P *成本）
p =概率再次調用。
成本 =再次緩存該對象的成本。
我同意。但是，如果具有較高命中次數的對象更有可能再次使用，則不需要使用命中次數，因爲它們也是最有可能最近被使用的次數。正如Erik所回答的那樣，hitcount是一個自我實現的預言。 – 2011-03-11 20:58:10
假設能夠記錄上次訪問條目的時間，我會爲每個條目添加一個「成本」，您隨時可以刪除最便宜的條目。
Cost = Size * N - TimeSinceLastUse * M
假設你完全從緩存中刪除條目（而不是保持周圍老hitcount數據），我會避免使用hitcount作爲一個指標，你最終與具有高hitcount的條目，因爲它已經在那裏很長一段時間，它會在那裏甚至更長，因爲它有很高的hitcount。
我通常使用嚴格的最近最少使用（LRU）方案來丟棄緩存中的東西，除非它是極其重要的重建某些項目更昂貴。 LRU具有實現起來非常簡單的好處，它適用於各種應用。它還將最常用的項目保存在緩存中。
實質上，我創建了一個鏈接列表，它也被字典索引。當客戶想要一個項目時，我會在字典中查找它。如果找到了，我將該節點從鏈接列表中解除鏈接並將其移動到列表頭部。如果該項目不在緩存中，我構建它（從磁盤或其他任何地方加載它），將它放在列表的頭部，插入到字典中，然後刪除列表尾部的項目。
可能想嘗試多級緩存風格。將一定比例的緩存分配給昂貴以創建項目，並將一部分緩存創建爲易於創建，但訪問次數更多的項目。然後，您可以使用不同的策略來維護昂貴的緩存，而不是比較便宜的緩存。
該算法可以考慮再現缺失元素的成本。這樣你就可以將最有價值的物品保存在緩存中。
您是否有上次訪問該條目的時間？ – Erik 2011-03-11 20:39:15
是的，當條目被訪問時，「last mod」也會被更新。 – MER 2011-03-11 21:30:10