泛型 - 泛型的应用 - 《Huang Java 开发学习》

- 泛型实现 LRU 缓存

泛型实现 LRU 缓存

LRU(Least Recently Used,最近最久未使用)缓存思想：

(1)固定缓存大小，需要给缓存分配一个固定的大小
(2)每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新
(3)需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存

实现思路：使用LinkedHashMap来实现LRU缓存。

LinkedHashMap的一个构造函数：

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

传入的第三个参数:
accessOrder为true的时候，就按访问顺序对LinkedHashMap排序，
accessOrder为false的时候,就按插入顺序(默认情况)。
当把accessOrder设置为true后（按照访问顺序），就可以将最近访问的元素置于最前面。这样就可以满足上述的(2)。
LinkedHashMap是自动扩容的，当table数组中元素大于Capacity loadFactor的时候，就会自动进行两倍扩容。但是为了使缓存大小固定，就需要在初始化的时候传入容量大小和*负载因子。为了使得到达设置缓存大小不会进行自动扩容，需要将初始化的大小进行计算再传入，将初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容了。这样就解决了上述的(1)。

实现
```java public class LRUCache { private final int MAX_CACHE_SIZE; private final float DEFAULT_LOAD_FACTORY = 0.75f; private LinkedHashMap map;;

public LRUCache(int cacheSize){

  MAX_CACHE_SIZE=cacheSize;
  int capacity=(int)Math.ceil(MAX_CACHE_SIZE/DEFAULT_LOAD_FACTORY)+1;
  //初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容
  map=new LinkedHashMap<K,V>(capacity,DEFAULT_LOAD_FACTORY,true){
      //true表示按照访问顺序
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
          return size()>MAX_CACHE_SIZE;
      }
  };

}

//为了线程安全所有方法都是同步方法 public synchronized void put(K key,V value){

  map.put(key,value);

}

public synchronized V get(K key){

  return map.get(key);

}

public synchronized void remove(K key){

  map.remove(key);

}

public synchronized Set> getAll(){

  return map.entrySet();

}

@Override public String toString() {

  StringBuilder sb=new StringBuilder();
  for(Map.Entry<K,V> entry:map.entrySet()){
      sb.append(String.format("%s: %s\n",entry.getKey(),entry.getValue()));
  }
  return sb.toString();

}

public static void main(String[] args) {

  LRUCache<Integer,Integer> lru=new LRUCache<Integer, Integer>(5); 
  //该缓存的容量是5
  lru.put(1, 1);
  lru.put(2, 2);
  lru.put(3, 3);
  System.out.println(lru);
  lru.get(1); //这里访问了 key=1的元素
  //按照访问顺序排序 --> key=1的元素是最新才访问的，所以key=2的元素是最近最久未访问的元素
  System.out.println(lru);
  lru.put(4,4);
  lru.put(5,5);
  lru.put(6,6);
  //容器的容量是5，当超过该容量时，会删除最近最久未访问的元素，也就是删除了key=2的元素
  System.out.println(lru);

} } /* 输出结果 1: 1 2: 2 3: 3

2: 2 3: 3 1: 1

3: 3 1: 1 4: 4 5: 5 6: 6 */


<a name="djg6y"></a>
### 泛型实现 FIFO 缓存
- FIFO设计思路：FIFO就是先进先出，可以使用LinkedHashMap进行实现。<br />
LinkedHashMap 的构造函数：
```java
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

当第三个参数传入为false或者是默认的时候，就可以实现按插入顺序排序，就可以实现FIFO缓存了。

public class FIFOCache<K,V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;
    private LinkedHashMap<K, V> map;
    public FIFOCache(int cacheSize) {
        this.MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        map=new LinkedHashMap<K,V>(capacity,DEFAULT_LOAD_FACTORY,false){
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }
    public synchronized void put(K key,V value){
        map.put(key,value);
    }
    public synchronized V get(K key){
        return map.get(key);
    }
    public synchronized void remove(K key){
        map.remove(key);
    }
    public synchronized Set<Map.Entry<K,V>> getAll(){
        return map.entrySet();
    }
    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for(Map.Entry<K,V> entry:map.entrySet()){
            sb.append(String.format("%s: %s\n",entry.getKey(),entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        //按照插入顺序
        FIFOCache<Integer,Integer> fifo=new FIFOCache<Integer, Integer>(5);
        fifo.put(1, 1);
        fifo.put(2, 2);
        fifo.put(3, 3);
        System.out.println(fifo);
        fifo.get(1);
        System.out.println(fifo);
        fifo.put(4,4);
        fifo.put(5,5);
        fifo.put(6,6);
        System.out.println(fifo);
    }
}
/* 输出结果
1: 1
2: 2
3: 3
1: 1
2: 2
3: 3
2: 2
3: 3
4: 4
5: 5
6: 6
*/