常用缓存过期算法

LRU 最近最少使用

LRU缓存过期算法 最近最少使用的对象最先被删除

• 原理

  在Android中，底层由一个LinkHashMap[^1]的链表组成，根据LinkHashMap的特性，插入排序，每一个最近的添加的元素都在队末。当一个元素被访问时候，也把他移到队末
  当链表满了以后，把队头的数据淘汰

  trimToSize重新计算长度，并删除第一个元素

public void trimToSize(int maxSize) {
   while (true) {
       K key;
       V value;
       synchronized (this) {
           if (size < 0 || (map.isEmpty() && size != 0)) {
               throw new IllegalStateException(getClass().getName()
                       + ".sizeOf() is reporting inconsistent results!");
           }

           if (size <= maxSize || map.isEmpty()) {
               break;
           }

           Map.Entry<K, V> toEvict = map.entrySet().iterator().next();//删除第一个元素
           key = toEvict.getKey();
           value = toEvict.getValue();
           map.remove(key);
           size -= safeSizeOf(key, value);
           evictionCount++;
       }

       entryRemoved(true, key, value, null);
   }
}

LFU 最近访问频率最低

LFU缓存过期算法 最近访问频率最低的对象最先被删除

• 原理

  双链表，其中一个用来维护元素的访问次数。缺点：无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责，并且消耗较多的内存

HashMap和LinkHashMap,ArrayMap,SpareArray的差异

HashMap

HashMap 在JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树

• 原理

  HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
  HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。HashMap扩容的时候，需要重建哈希表，即 new Entry[],在把老的数据复制过来

• 结构

  
  hashmap.png

• 注意点

  • 重写equal方法必须要重写hashCode方法

  class Test{
    int a;
    int b;
    public boolean equals(Object obj){
      if (this == obj)
          return true;
  
      if ((obj == null) || (obj.getClass() != this.getClass()))
          return false;
  
      Test test = (Test) obj;
      return num == test.a;
  }
  
  public int hashCode(){
      int hash = 7;
      hash = 31*hash+a.hashCode();
      return hash;
  
  }
  }
  

如上面代码，equal比对的时候只关心a字段，而不进行b字段比对，如果不重写hashCode方法，那么默认的hashCode比对的是整体的obj，那么会导致hashCode不同，而找不到Entry对应的值

LinkHashMap

LinkHashMap 继承HashMap，但是保存Entry的时候，除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。

• 原理 重写父类HashMap的put方法调用的子方法 addEntry和createEntry方法，保存上一个元素before和下一个元素after的引用，到达类似于List的结构。get方法的时候，取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的末端，并从原来的位置删除

SpareArray

SpareArray 定义了2个数组，int[] mKeys和 Object[] mValues， mKeys中的数据为升序有序排列。还有兄弟类，例如LongSparesArray，不是SparesLongArray

• 原理 通过二分查找在mKeys找到key值对应的index，再根据index找到mValues中对应的value，是一个稀疏数组不是一个哈希表
• 亮点设计 删除延迟 gc回收 二分查找
  • 删除延迟 删除的元素不是马上删除而是打个标记，等待被覆盖或者gc回收
  • gc回收 通过定期（如put方法和append方法中）的调用gc方法，回收空间压缩空间
  • 二分查找 快速查询获取数据

ArrayMap

ArrayMap 实现 Map<K，V>接口，基于两个数组，一个int保存hashCode，一个为Obj保存key/value键值对。容量是上一个数组的两倍。

• 原理

  • get方法采用二分查找 找到hashCode数组中所在的index，然后在Obj数组中按key= 2index，value=2index+1 得到对应的 key和value

  • put方法 通过key计算hash值，再使用得到的hash值二分查找（indexOf，调用的ContainerHelpers.binarySearch ）在mhashes 数组中的index 下标值，通过这个方法，我们在没有查找到元素时，只需要将返回值取反即可获取待插入元素需要插入的位置，然后接下来数组容量满的时候进行扩容，然后会执行数组移动的工作，为相应的元素插入腾出空间，最后插入，结束。扩容的缓存原理比较复杂，有兴趣可以自己了解一下，主要基于扩容后大小是否为BASE_SIZE=4或BASE_SIZE=42，BASE_SIZE=4为固定值。因为ArrayMap是一个用来放少量数据的优化版本HashMap,所以BASE_SIZE=4。也正是因为缓存的存在扩容时只需要数组拷贝工作，不需要重建哈希表。但是如果不为BASE_SIZE=4或BASE_SIZE=42，那么还是采取new的方式进行

  • 结论
    当数据量低于1000的时候，可以使用，对比SpareArray，优点是key的类型不受限制，缺点是SpareArray的key为int,或者long等得时候，没有自动装箱的过程，所以查询速度SpareArray比ArrayMap，和HashMap快