LinkedHashMap与LruCache的源码分析

最近在公司的项目中，需要从后台获取JSON，按循序拼接后使用HMAC加密校验，在这里要保证校验一致性，就需要保证各个字段加密顺序不能变。
为了方便处理，我用JSONObject类解析了JSON数据，通过查看JSONObject类内部实现，发现的确是用LinkedHashMap实现的，可以保证顺序。

JSONObject部分代码

 private final LinkedHashMap<String, Object> nameValuePairs;

    public JSONObject() {
        nameValuePairs = new LinkedHashMap<String, Object>();
    }

LinkedHashMap代码分析

以前只知道LinkedHashMap可以保证顺序，却不知道如何实现，怎么保证HashMap的有序性，通过查看源码发现LinkedHashMap还是继承了HashMap，另外把HashMap中保存的Entry重写为双向链表的节点元素，维护链表来保证访问顺序。

• 双向链表的定义

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /**
     *  双向链表的头节点
     */
    private transient LinkedHashMapEntry<K,V> header;

• 双向链表的初始化
  LinkedHashMap重写了init函数，该函数在HashMap的构造函数里会进行调用。

 @Override
    void init() {
        header = new LinkedHashMapEntry<>(-1, null, null, null);
        header.before = header.after = header;
    }

• 添加数据(put)
  LinkedHashMap并没有重写put方法，而是重写父类put方法会调用的addEntry和createEntry方法

 void addEntry(int hash, K key, V value, int bucketIndex) {
        LinkedHashMapEntry<K,V> eldest = header.after;
        if (eldest != header) {
            boolean removeEldest;
            size++;
            try {
              // 删除最近最早使用元素的策略
              // 现在Android里removeEldestEntry一直返回false
                removeEldest = removeEldestEntry(eldest);
            } finally {
                size--;
            }
            if (removeEldest) {
                removeEntryForKey(eldest.key);
            }
        }
       // 父类的这个方法会调用createEntry方法
        super.addEntry(hash, key, value, bucketIndex);
    }

 void createEntry(int hash, K key, V value, int bucketIndex) {
     // 创建节点，并在双向链表的前面插入该节点
        HashMapEntry<K,V> old = table[bucketIndex];
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

        //插入节点到链表前面
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

画了一个简单的流程图，可以有更直观的感受

image.png

• 获取数据(get)
  get方法很简单，直接调用父类的getEntry就可以获取数据了，
  但里面recordAccess方法很有意思，如果accessOrder为True,
  可以把最近访问的元素移动到链表表头，这个方法在LruCache的实现中很有用。

 public V get(Object key) {
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

   void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            //如果accessOrder为True, 将自己从链表中移除，
            // 并重新插入到表头
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

• 迭代器（Iterator）
  LinkedHashMap还重写了key,value,entry三个迭代器的实现, 使我们用for循环的时候能够有序访问map中的元素

    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

以下是Iterator的几个关键函数实现，参照上面的链表图，我们可以知道遍历是从链表的最后面往前遍历的，与List一样，越后面put进去的元素越晚遍历到。

  private abstract class LinkedHashIterator<T> implements Iterator<T> {
    LinkedHashMapEntry<K,V> nextEntry   = header.after;
    public boolean hasNext() {
            return nextEntry != header;
    }

    Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
     }

LruCache代码分析

LruCache是使用最近最少使用算法实现的缓存类，在Android系统以及各个图片框架中基本上都有自己的LruCache实现，各个版本的实现基本大同小异，都是使用LinkedHashMap来实现的。

以下的分析代码是基于Glide中的LruCache实现

• 创建LinkedHashMap

public class LruCache<T, Y> {
    private final LinkedHashMap<T, Y> cache = new LinkedHashMap<T, Y>(100, 0.75f, true);

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

这里LinkedHashMap构造函数的几个参数说明一下

    - initialCapacity  
      LinkedHashMap初始申请的容量大小
    - loadFactor 
      负载因子, 超过后需要扩充容量，Android中这个值其实是固定的，一直是0.75f
    - accessOrder
      访问顺序，设置为True后，调用LinkedHashMap的get方法会调整链表元素位置

• 构造函数

   //设置LruCache的大小
    public LruCache(int size) {
        this.initialMaxSize = size;
        this.maxSize = size;
    }

• 添加数据（put)

 public Y put(T key, Y item) {
        final int itemSize = getSize(item);
       //超出大小后，不加入cache
        if (itemSize >= maxSize) {
            onItemEvicted(key, item);
            return null;
        }

       //直接调用LinkedHashMap的put方法保存数据
      // 新添加的数据会放在双向链表的表头
        final Y result = cache.put(key, item);
        if (item != null) {
            currentSize += getSize(item);
        }
        //如果元素已经存在Map中了，恢复currentSize
        if (result != null) {
            // TODO: should we call onItemEvicted here?
            currentSize -= getSize(result);
        }

       //移除最近最少使用的元素
        evict();

        return result;
    }

  private void evict() {
      //大小超过定义的最大值后，移除其中最近最少访问的元素
        trimToSize(maxSize);
  }

• 获取数据(get)

//由于LinkedHashMap的accessOrder设置为True了，
//访问get方法会将被访问元素移动到链表头
   public Y get(T key) {
        return cache.get(key);
    }

• 调整大小（trimToSize）
  超出LruCache中得定义的最大容量后，会调用trimToSize函数移除最近最少访问的元素。
  由于LinkedHashMap的put和get方法都会将元素移动到链表的最前面，那么链表最后面的元素就是最近最少访问的，所以调整LruCache大小时直接从最后面开始删除即可。

 protected void trimToSize(int size) {
        Map.Entry<T, Y> last;
        while (currentSize > size) {
          //从双向链表尾部的元素开始移除
            last = cache.entrySet().iterator().next();
            final Y toRemove = last.getValue();
            currentSize -= getSize(toRemove);
            final T key = last.getKey();
            cache.remove(key);
            onItemEvicted(key, toRemove);
        }
    }

---

扫一扫下方二维码，关注我的微信公众号，第一时间获得Android开发进阶文章

APP开发进阶