caching - LRU 和 LFU 有什么区别

Question

LRU 和 LFU 缓存实现有什么区别？

我知道LRU可以使用LinkedHashMap来实现。 但如何实现LFU缓存呢？

Answer 1

让我们考虑缓存容量为 3 的恒定缓存请求流，如下所示:

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

如果我们只考虑使用 HashMap + 双向链表实现的最近最少使用 (LRU) 缓存，且具有 O(1) 驱逐时间和 O(1) 加载时间，我们将得到以下结果如上所述，在处理缓存请求时缓存的元素。

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better! 

当您查看这个示例时，您可以很容易地看到我们可以做得更好 - 考虑到将来请求 A 的预期机会更高，我们不应该驱逐它，即使它最近最少使用。

A - 12
B - 2
C - 2
D - 1

最不频繁使用 (LFU) 缓存通过跟踪缓存请求在其逐出算法中使用的次数来利用此信息。