[数据结构与算法]mybatis缓存LruCache源码分析

LruCache是如何实现的

LruCache的关键代码：

public class LruCache implements Cache {

  private final Cache delegate;
  private Map<Object, Object> keyMap;
  private Object eldestKey;

  public LruCache(Cache delegate) {
    this.delegate = delegate;
    // 设置缓存的键值对最大数量
    setSize(1024);
  }

  public void setSize(final int size) {
    /**
     * 重写方法：是否移除最老的链表节点，最老的链表节点就是链表的头节点
     */
    keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
      private static final long serialVersionUID = 4267176411845948333L;

      @Override
      protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
        // 判断什么时候需要移除最老的节点
        boolean tooBig = size() > size;
        if (tooBig) {
          // 保存最老的链表节点的key，方便cycleKeyList()删除相应的key
          eldestKey = eldest.getKey();
        }
        return tooBig;
      }
    };
  }

  @Override
  public Object getObject(Object key) {
    // 虽然没有使用这个返回值，但是需要更细linkedHashMap的使用情况
    keyMap.get(key); // touch
    return delegate.getObject(key);
  }

  private void cycleKeyList(Object key) {
    /**
     * 这个方法会更新eldestKey的值
     * 此方法在hashMap当中，调用过程：hashmap.put()->linkedHashMap.afterNodeInsertion()->linkedHashMap.removeEldestEntry()
     * 最终eldestKey的值被更新
     */
    keyMap.put(key, key);
    // 如果eldestKey的值被更新，则需要到真正存储缓存的地方删除键值对
    if (eldestKey != null) {
      delegate.removeObject(eldestKey);
      eldestKey = null;
    }
  }

}

linkedHashMap源码分析

双向链表

链表优点

1. 插入，删除，新增操作的时间复杂度都是O(1)
2. 可以利用不连续的内存空间

链表缺点

1. 不能随机查找，随机查找的时间复杂度是o(n)
2. 因为要保存前后节点的引用，所以占用的内存空间会变大

双向链表节点

/**
     * 继承了HashMap.Node
     * 其实就是在hashMap节点的基础上加入before和after节点
     * 构成了双向链表的节点
     * @param <K>
     * @param <V>
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

移动节点到链表的尾部

当get()被调用了，当前节点就变成最新被访问的了，需要移动到链表的尾部

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        /**
         * 两个判断逻辑：
         * 1 链表是否支持按照最近最新使用规则排序，默认按照插入顺序排序
         * 2 当前节点是否已经是尾节点了
         */
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null) // 说明当前节点是head
                head = a; //重新定义head 
            else
                b.after = a; // 重新定义p.before的指向
            
            if (a != null) 
                a.before = b; // 重新定义p.after的指向
            else // a==null说明b已经是尾节点了
                last = b;
            
            if (last == null) // 说明当前链表为空
                head = p;
            else {   // 定义新的为节点
                p.before = last;
                last.after = p;
            }
            // 新的尾节点产生，可以看出移动链表的节点不需要通过遍历链表
            tail = p;
            ++modCount;
        }
    }

为什么要散列表和链表搭配使用

针对链表不能随机访问的缺点，如果使用散列表随机访问时间复杂度为O(1)的有点，两者扬长避短，充分发挥各自的优势

这样一来，可以创建有序的map键值对

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>