LRUCache原理解析

• LRUCache底层维护了一个LinkedHashMap
  这个LinkedHashMap对象是实现Lru算法的关键，Lru是最近最少使用算法的简称，意思呢就是查询出最近的时间使用次数最少的那个对象。
  new LinkedHashMap<K, V>(0, 0.75f, true)这句代码表示，初始容量为零，0.75是加载因子，表示容量达到最大容量的75%的时候会把内存增加一半。最后这个参数至关重要。表示访问元素的排序方式，true表示按照访问顺序排序，false表示按照插入的顺序排序。
  跟一下LinkedHashMap的构造方法就能看出

 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        throw new RuntimeException("Stub!");
    }

进行了这样一个测试，当设置为true的时候

   LinkedHashMap<Integer,Integer> lru = new LinkedHashMap<>(0,0.75f,true);
        lru.put(0,0);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        lru.put(4,4);
        lru.put(5,5);
        lru.put(6,6);
        lru.put(7,7);
        lru.get(1);
        lru.get(2);
        for(Map.Entry<Integer,Integer> entry :lru.entrySet()){
            Log.w("TAG","entry.getKey:"+entry.getKey()+",entry.getValue:"+entry.getValue());
        }

打印出的结果为:

W/TAG: entry.getKey:0,entry.getValue:0
W/TAG: entry.getKey:3,entry.getValue:3
W/TAG: entry.getKey:4,entry.getValue:4
W/TAG: entry.getKey:5,entry.getValue:5
W/TAG: entry.getKey:6,entry.getValue:6
W/TAG: entry.getKey:7,entry.getValue:7
W/TAG: entry.getKey:1,entry.getValue:1
W/TAG: entry.getKey:2,entry.getValue:2

可以看到,我操作了一下get,key为1和2，那么1和2对应的value就被放到了集合的最后面，这里也能看出

到了这里我们可以知道，这个LinkedHashmap正是实现Lru算法的核心之处，当内容容量达到最大值的时候，只需要移除这个集合的前面的元素直到集合的容量足够存储数据的时候就可以了。而最近最常用的数据被放到了集合的最后面

@Override 
public V put(K key, V value) {
        if (key == null) {
        //如果key为null调用该方法处理，需要注意的是HashMap允许key和value为null
            return putValueForNullKey(value);
        }
        //根据key得到hash值
        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        //根据hash值和内部维护数组的长度得到索引
        int index = hash & (tab.length - 1);
        //如果index处的e不为null，通过循环不断遍历e的下一个元素
        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
        // 找到指定 key 与需要放入的 key 相等（hash 值相同  
     // 并且key的值相等）说明map中已经存在该数据，那么执行替换
            if (e.hash == hash && key.equals(e.key)) {
                //该方法是空实现，注意LinkedHashMap中会用到
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for (non-null) key is present; create one
        //index处的Entry为null，说明此处还没有数据Entry
        modCount++;
        if (size++ > threshold) {
        //大于数组的长度，扩容 大小x2
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }