Java中实现TreeMap缓存驱逐策略
内容提要
Java中使用TreeMap实现LFU（最不常用）缓存驱逐策略的方法。LFUCache类使用TreeMap来跟踪键的频率，并使用Map存储键值对。通过put()和get()方法将键值对添加到缓存中并进行检索。示例程序创建了一个容量为3的LFUCache对象，并添加和检索了值。
延伸解读
TreeMap 在 LFU 中的角色
TreeMap 的排序特性使其能快速定位最小频率。代码中 frequencyCounter 以频率为键，存储具有该频率的键集合。通过 firstKey() 可立即获取最低频率，从而找到最不常用的键。这避免了遍历所有频率，提升了驱逐效率。
频率更新与顺序维护
每次 get 或 put 操作都会更新键的频率。get 时，从原频率集合移除键，并添加到频率加一的集合中；若原集合为空则删除该频率。put 新键时，频率初始化为 1。LinkedHashSet 保持了同频率键的插入顺序，但 LFU 不保证淘汰顺序。
容量与边界处理
构造函数接受容量参数，若容量小于等于 0，put 方法直接返回，不进行缓存。当缓存大小达到容量时，put 会先驱逐最不常用的键，再添加新键。这确保了缓存大小不超过容量，但未处理键已存在时的更新情况。
示例演示与注意事项
示例创建容量为 3 的缓存，依次添加键 1、2、3，访问键 1 后添加键 4，此时键 2 因频率最低被驱逐。后续 get 2 返回 null，get 3 和 4 返回对应值。注意，此实现未考虑并发，且未处理相同键的重复 put。
Q&A
Java中如何用TreeMap实现LFU缓存驱逐策略？
使用TreeMap作为频率计数器，键为频率，值为LinkedHashSet存储该频率的所有键。同时用HashMap存储键值对和键的频率。get()方法更新频率并移动键到更高频率的集合；put()方法在缓存满时从TreeMap的第一个键（最低频率）对应的集合中移除一个键（最久未使用），然后添加新键并设置频率为1。
LFU缓存驱逐策略中，当缓存满时如何选择要删除的元素？
选择频率最低的元素。如果有多个元素频率相同，则选择最早加入该频率集合的元素（通过LinkedHashSet的迭代顺序保证）。
LFUCache类的get()方法是如何更新频率的？
get()方法首先检查键是否存在，若不存在返回null。然后从frequencyMap获取当前频率，将其加1并更新frequencyMap。接着从frequencyCounter中当前频率的集合移除该键，如果集合为空则移除该频率条目。最后将键添加到频率加1的集合中（若不存在则创建），并返回缓存中的值。
LFUCache类的put()方法在缓存未满和已满时分别如何处理？
如果容量<=0，直接返回。如果缓存大小>=容量，则从frequencyCounter的第一个键（最低频率）对应的集合中取出一个键（最久未使用），从cache、frequencyMap和frequencyCounter中移除该键。然后无论是否已满，都将新键值对放入cache，在frequencyMap中设置频率为1，并在frequencyCounter的频率1集合中添加该键。
能否给出一个使用LFUCache的示例？
可以。示例中创建容量为3的LFUCache，依次put(1,"One")、put(2,"Two")，然后get(1)返回"One"并增加键1的频率。接着put(3,"Three")、put(4,"Four")，此时缓存满，会驱逐频率最低的键（键2频率为1，且最早加入）。最后get(2)返回null，get(3)返回"Three"，get(4)返回"Four"。
为什么选择TreeMap来实现LFU缓存？
TreeMap提供了排序映射，可以高效地获取最小频率（firstKey()），并且能快速迭代。结合LinkedHashSet可以维护相同频率下键的插入顺序，从而在频率相同时实现最久未使用（LRU）的驱逐。
