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方法会调用的addEntrycreateEntry方法
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开发进阶文章