单位建设网站硬件,网站域名怎么改,wordpress文章发布时间,网站空间续费合同LinkedHashMap源码分析以及LRU的应用
LinkedHashMap简介
LinkedHashMap我们都知道是在HashMap的基础上#xff0c;保证了元素添加时的顺序#xff1b;除此之外#xff0c;它还支持LRU可以当做缓存中心使用
源码分析目的 分析保持元素有序性是如何实现的 LRU是如何实现的…LinkedHashMap源码分析以及LRU的应用
LinkedHashMap简介
LinkedHashMap我们都知道是在HashMap的基础上保证了元素添加时的顺序除此之外它还支持LRU可以当做缓存中心使用
源码分析目的 分析保持元素有序性是如何实现的 LRU是如何实现的
源码分析
有序性的实现
public class LinkedHashMapK,V extends HashMapK,V implements MapK,V{transient LinkedHashMap.EntryK,V head;transient LinkedHashMap.EntryK,V tail;final boolean accessOrder;static class EntryK,V extends HashMap.NodeK,V {EntryK,V before, after;Entry(int hash, K key, V value, NodeK,V next) {super(hash, key, value, next);}}NodeK,V newNode(int hash, K key, V value, NodeK,V e) {}void afterNodeAccess(NodeK,V p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(NodeK,V p) { }
}LinkedHashMap继承自HashMap并主要重写了HashMap中四个方法分别是newNode、afterNodeAccess、afterNodeInsertion、afterNodeRemoval,这几个方法分别会在HashMap创建元素、访问元素、添加元素、删除元素之后回调LinkedHashMap主要通过这几个方法构建成双向链表将元素连接起来从而实现顺序访问的目的。 变量head和tail分别指向第一个元素和最后一个元素 添加的元素会包装成Entry对象Entry继承自HashMap.Node在此基础上增加before和after 变量用于指向当前元素的前后两个元素形成链式结构 accessOrdertrue表示对元素根据LRU来排序也就是最近访问过的放链表尾部最后访问过的放链表头部默认为false
添加元素
在LinkedHashMap中并没有重写HashMap的put方法根据HashMap的put方法源码可以知道当添加一个元素时会调用newNode方法去创建一个Node对象接着会调用afterNodeInsertion方法我们先来看看LinkedHashMap是如何重写这两个方法的
NodeK,V newNode(int hash, K key, V value, NodeK,V e) {LinkedHashMap.EntryK,V p new LinkedHashMap.EntryK,V(hash, key, value, e);linkNodeLast(p);return p;
}private void linkNodeLast(LinkedHashMap.EntryK,V p) {LinkedHashMap.EntryK,V last tail;tail p;if (last null)head p;else {p.before last;last.after p;}
}在创建元素节点时会先创建一个LinkedHashMap.Entry节点然后将该元素添加链表的尾部
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}元素添加后会调用afterNodeInsertion方法LinkedHashMap重写该方法后根据removeEldestEntry方法决定是否要将表头元素删除这里主要是为了支持LRU如果该方法返回true则表示缓存已满会移除链表头元素 其中evict 变量在HashMap中的解释是如果false表示创建模式也就是反序列化时初始化HashMap数据时调用的put方法
获取元素
public V get(Object key) {NodeK,V e;if ((e getNode(hash(key), key)) null)return null;if (accessOrder)afterNodeAccess(e);return e.value;
}void afterNodeAccess(NodeK,V e) { // move node to lastLinkedHashMap.EntryK,V last;if (accessOrder (last tail) ! e) {LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.after null;if (b null)head a;elseb.after a;if (a ! null)a.before b;elselast b;if (last null)head p;else {p.before last;last.after p;}tail p;modCount;}
}LinkedHashMap重写了HashMap的get方法主要是为了在获取元素后根据accessOrder变量来判断是否要根据LRU调整元素位置默认为false所以获取元素后顺序是不会变的也就是保证了原有的顺序
但是如果要作为LRU缓存中心来存储数据则需要设置为true接着调用重写了HashMap的afterNodeAccess方法对元素位置进行调整其实也就是将当前访问的元素移动到链表的尾部
移除元素
void afterNodeRemoval(NodeK,V e) { // unlinkLinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.before p.after null;if (b null)head a;elseb.after a;if (a null)tail b;elsea.before b;
}在元素移除后需要将该元素从双向链表中移除逻辑也是比较简单
遍历集合
LinkedHashMap重写了Map相关集合遍历的方法比如entrySet、keySet等让外部能够根据双向链表顺序访问到元素
public SetMap.EntryK,V entrySet() {SetMap.EntryK,V es;return (es entrySet) null ? (entrySet new LinkedEntrySet()) : es;
}final class LinkedEntrySet extends AbstractSetMap.EntryK,V {public final int size() { return size; }public final void clear() { LinkedHashMap.this.clear(); }public final IteratorMap.EntryK,V iterator() {return new LinkedEntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry?,? e (Map.Entry?,?) o;Object key e.getKey();NodeK,V candidate getNode(hash(key), key);return candidate ! null candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?) o;Object key e.getKey();Object value e.getValue();return removeNode(hash(key), key, value, true, true) ! null;}return false;}public final SpliteratorMap.EntryK,V spliterator() {return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}public final void forEach(Consumer? super Map.EntryK,V action) {if (action null)throw new NullPointerException();int mc modCount;for (LinkedHashMap.EntryK,V e head; e ! null; e e.after)action.accept(e);if (modCount ! mc)throw new ConcurrentModificationException();}
}LRU的支持
LinkedHashMap天生支持LRU可以用于作为LRU缓存中心当LinkedHashMap创建时可以传入参数将成员变量accessOrder设置为true表示需要根据元素访问来调整顺序
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder accessOrder;
}这样当访问元素时会将该元素移动到队尾经过多次访问后最近访问的元素到了队尾而最早访问元素则到了队头
public V get(Object key) {NodeK,V e;if ((e getNode(hash(key), key)) null)return null;if (accessOrder)afterNodeAccess(e);//移动到队尾return e.value;
}当插入元素时提供了一个方法removeEldestEntry用于根据当前最大缓存容量来决定是否要删除队头元素
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}
protected boolean removeEldestEntry(Map.EntryK,V eldest) {return false;
}所以创建LRU的缓存中心只需要两步 创建LinkedHashMap时设置accessOrder为true 重写removeEldestEntry方法在该方法中如果当前元素个数大于最大允许的缓存元素个数则返回true已移除双向链表中的头元素
简单LRU缓存中心实现
public class LruCacheCenterK, V extends LinkedHashMapK, V {private int mMaxCacheSize;//最大缓存个数public LruCacheCenter() {this(MAX_CACHE_NUM);}public LruCacheCenter(int maxCacheSize) {super(maxCacheSize, 0.75f, true);//accessOrder设置为truethis.mMaxCacheSize maxCacheSize;}Overrideprotected boolean removeEldestEntry(Map.EntryK, V eldest) {return size() mMaxCacheSize;}
}
