一、前言

不同于之前LRU缓存算法，LFU（全称是Least Frequently Used）即最不经常使用页置换算法，当到达存储上限时，优先淘汰最早最少访问的对象元素。

二、代码示例

package com.xwood.gw.accesslog;@b@@b@import java.util.Collections;@b@import java.util.HashMap;@b@import java.util.Map;@b@ @b@public class LFUCache<k,v> {@b@	@b@	  private final int capcity;@b@@b@	  private Map<k, v> cache = new HashMap<k, v>();@b@@b@	  private Map<k, HitRate> count = new HashMap<k,HitRate>();@b@@b@	  public LFUCache(int capcity) {@b@	    this.capcity = capcity;@b@	  }@b@	  @b@	  public  boolean containKey(k keyObj){@b@		  return  cache.keySet().contains(keyObj);@b@	  }@b@	  @b@	  public  boolean  containValue(v valueObj){@b@		  return cache.entrySet().contains(valueObj);@b@	  }@b@@b@	  public void put(k key, v value) {@b@	    v v = cache.get(key);@b@	    if (v == null) {@b@	      if (cache.size() == capcity) {@b@	        removeElement();@b@	      }@b@	      count.put(key, new HitRate(key, 1, System.nanoTime()));@b@	    } else {@b@	      addHitCount(key);@b@	    }@b@	    cache.put(key, value);@b@	  }@b@@b@	  public v get(k key) {@b@	    v value = cache.get(key);@b@	    if (value != null) {@b@	      addHitCount(key);@b@	      return value;@b@	    }@b@	    return null;@b@	  }@b@@b@	  //移除元素@b@	  private void removeElement() {@b@	    HitRate hr = Collections.min(count.values());@b@	    cache.remove(hr.key);@b@	    count.remove(hr.key);@b@	  }@b@@b@	  //更新访问元素状态@b@	  private void addHitCount(k key) {@b@	    HitRate hitRate = count.get(key);@b@	    hitRate.hitCount = hitRate.hitCount + 1;@b@	    hitRate.lastTime = System.nanoTime();@b@	  }@b@@b@	  //内部类@b@	  class HitRate implements Comparable<HitRate> {@b@	    private k key;@b@	    private int hitCount;@b@	    private long lastTime;@b@@b@	    private HitRate(k key, int hitCount, long lastTime) {@b@	      this.key = key;@b@	      this.hitCount = hitCount;@b@	      this.lastTime = lastTime;@b@	    }@b@@b@	    @Override@b@	    public int compareTo(HitRate o) {@b@	      int compare = Integer.compare(this.hitCount, o.hitCount);@b@	      return compare == 0 ? Long.compare(this.lastTime, o.lastTime) : compare;@b@	    }@b@	  }@b@@b@@b@	  public static void main(String[] args) {@b@	  @b@	    LFUCache<Integer, Integer> cache = new LFUCache<Integer, Integer>(3);@b@	    cache.put(2, 2);@b@	    cache.put(1, 1);@b@@b@	    System.out.println(cache.get(2));@b@	    System.out.println(cache.get(1));@b@	    System.out.println(cache.get(2));@b@@b@	    cache.put(3, 3);@b@	    cache.put(4, 4);@b@@b@	    //1、2元素都有访问次数，放入3后缓存满，加入4时淘汰3@b@	    System.out.println(cache.get(3));@b@	    System.out.println(cache.get(2));@b@	    System.out.println(cache.get(4));@b@@b@	    cache.put(5, 5);@b@	    //目前2访问2次，1访问一次，4访问一次，由于4的时间比较新，放入5的时候移除1元素。@b@	    System.out.println("-------");@b@	    @b@	    @b@	    for(int ckey:cache.cache.keySet()){@b@	    	System.out.println("ckey---"+cache.cache.get(ckey));@b@	    }@b@@b@	  }@b@	  @b@}

控制台打印结果

2@b@1@b@2@b@null@b@2@b@4@b@-------@b@ckey---2@b@ckey---4@b@ckey---5