上一篇基于哈希表实现 HashMap 核心源码彻底分析 分析了 HashMap 的源码, 主要分析了扩容机制, 如果感兴趣的可以去看看, 扩容机制那几行最难懂的代码真是花费了我很大的精力.
好了本篇我们分析一下 HashMap 的儿子 LinkedHashMap 的核心源码, 提到 LinkedHashMap 做安卓的同学肯定会想到 Lru(Least Recently Used)算法, Lru 算法就是基于 LinkedHashMap 来实现的, 明白了 LinkedHashMap 中基于访问排序逻辑 Lru 算法自然就明白了.
进入正题, 源码基于 Android-23.
一, LinkedHashMap 中成员变量
- /**
- * A dummy entry in the circular linked list of entries in the map.
- * The first real entry is header.nxt, and the last is header.prv.
- * If the map is empty, header.nxt == header && header.prv == header.
- */
- transient LinkedEntry<K, V> header;
- /**
- * True if access ordered, false if insertion ordered.
- */
- private final boolean accessOrder;
很简单, 就两个成员变量. 不过这里要明白 LinkedHashMap 是继承 HashMap 也就是 HashMap 中一些成员变量, 方法 LinkedHashMap 中都是有的, 父类的玩意就不提了, 这里只说一下子类自己的.
header 双向循环链表的头结点, 看注释 The first real entry is header.nxt, and the last is header.prv. 翻译过来就是第一个加入链表的结点是 header.nxt, 最后被加入链表的是 header.prv.
accessOrder 控制链表的排序方式, 如果是 true 那么链表节点是基于访问排序的, 什么是访问排序? 就是我们访问链表中某一节点的时候会将这个结点从链表中删除然后在放入链表的尾部, 表示用户最近使用了这个结点, 最近被 "宠幸" 了一次, 那好, 我把你放入链表尾部, 链表删除是从头部删除的, 插入数据是从尾部插入的, 如果遇到一些情况要删除链表中节点数据, 那么优先删除的是链表头部不经常使用的节点数据. 如果为 false 则表示链表节点是基于插入排序的, 理解起来很简单, 就是平常的插入顺序了, 先插入的在头部优先被删除.
二, LinkedHashMap 构造方法
接下来看下构造方法, 如下:
- public LinkedHashMap() {
- init();
- accessOrder = false;
- }
- public LinkedHashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- this(initialCapacity, loadFactor, false);
- }
- public LinkedHashMap(
- int initialCapacity, float loadFactor, boolean accessOrder) {
- super(initialCapacity, loadFactor);
- init();
- this.accessOrder = accessOrder;
- }
- @Override
- void init() {
- header = new LinkedEntry<K, V>();
- }
以上就是初始化的主要方法, 大体上和 HashMap 差不多, 不在细说, 主要一点是默认的 accessOrder 值为 false, 也就是链表节点按照插入排序来排序的, 当然我们也可以在初始化的时候指定 accessOrder 值, 比如 LruCache 中 LinkedHashMap 初始化的时候 accessOrder 就指定为 true.
三, LinkedHashMap 中数据项 LinkedEntry
LinkedHashMap 中每个数据节点类型为 LinkedEntry,LinkedEntry 为 HashMapEntry 子类, 我们直接看其源码:
- static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
- LinkedEntry<K, V> nxt;
- LinkedEntry<K, V> prv;
- /** Create the header entry */
- LinkedEntry() {
- super(null, null, 0, null);
- nxt = prv = this;
- }
- /** Create a normal entry */
- LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
- LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
- super(key, value, hash, next);
- this.nxt = nxt;
- this.prv = prv;
- }
- }
LinkedEntry 多了两个成员变量 nxt 与 prv, 分别只向后一个节点与前一个节点, 这里暂且称呼为前向指针与后向指针, 方便理解.
每个数据节点结构类似如下图所示:
并且稍有经验就知道了 LinkedHashMap 中链表为双向循环链表, 其数据结构如下图所示:
四, LinkedHashMap 中 put 方法
我们会发现 LinkedHashMap 中并没有重写 put 方法, 只是重写了 addNewEntry 方法, 很好理解, HashMap 与 LinkedHashMap 二者数据结构都不一样, 肯定无法共用同一个 put 方法, 这里 LinkedHashMap 重写了 addNewEntry 方法根据自己需要放入数据即可, 至于 hash 值, index 等父类已经帮我算好了, 直接继承传递过来用就可以了, 接下来我们分析 LinkedHashMap 中 addNewEntry 方法, 源码如下:
- @Override
- void addNewEntry(K key, V value, int hash, int index) {
- LinkedEntry<K, V> header = this.header;
- // Remove eldest entry if instructed to do so.
- LinkedEntry<K, V> eldest = header.nxt;
- if (eldest != header && removeEldestEntry(eldest)) {
- remove(eldest.key);
- }
- // Create new entry, link it on to list, and put it into table
- LinkedEntry<K, V> oldTail = header.prv;
- LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
- key, value, hash, table[index], header, oldTail);
- table[index] = oldTail.nxt = header.prv = newTail;
- }
3 行, 获取链表的头结点 header.
6 行, 获取链表中最先被加入的数据节点 eldest, 也就是最老的数据节点, 位于队头.
7-9 行, 判断最老的数据节点 eldest 与 header 是否相等以及 removeEldestEntry(eldest)方法是否返回 true, 如果二者均为 true 则删除最老的数据节点.
什么情况下 eldest 与 header 是否相等? 很简单就是链表刚刚建立的时候啊, 只有一个 header 节点, nxt 与 prv 指针均指向自己.
removeEldestEntry(eldest)方法源码如下:
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
- return false;
- }
看到了吧, 超级简单, 直接返回 false, 也就是默认是不会删除最老的节点的.
12 行, 获取 oldTail, 这里 oldTail 是链表中最后被插入的数据节点, 也就是最新的数据, 位于链表最尾部.
13 行, 创建一个新的数据节点 newTail, 看这名字就知道了位于链表尾部, 翻译过来就是: 新的尾巴.
新节点的 nxt 指针指向 header,prv 指针指向 oldTail, 也就是加入之前链表的尾部, 13,14 行执行完链表图示如下: 红色部分为即将加入链表的节点.
15 行, oldTail 的 nxt 指针指向 newTail, 链表的头结点 header 的 prv 指针指向 newTail 节点, 此时链表结构如图所示:
此时, 新的数据节点 (红色部分) 就已经插入链表了, 最新插入的数据位于链表尾部.
以上就是 LinkedHashMap 放入数据的核心逻辑, 其实很简单, 就是操作双向链表而已.
接下来, 我们分析 get 方法, 看看怎么实现访问排序的.
五, LinkedHashMap 中 get 方法
再讲 get 方法之前我们稍微回顾一下 addNewEntry 方法的 13-15 行, 这几行中有个 table[index]没有提到, 其实上面我只是将双向循环链表提取出来讲放入数据的逻辑, 这样理解起来比较简单, 而 LinkedHashMap 中隐藏了 HashMap 中的单向链表, 全部展示出其数据结构如图所示:
是不是看着乱了很多, 如果一开始我就抛出此图, 估计很多就蒙圈了, 除去红色的线其就是一个双向循环链表, 为什么这时候要抛出这个图呢? 大家想一下我们如果要 get 一个数据没有单向链表的话很自然从 header 节点开始挨个遍历整个链表就完了, 和 LinkedList 算法就很像了, 显然效率低下, 这里有单向链表, 我们只需要算出将要获取的数据在 table 数组的哪一行, 只需要遍历那一行单向链表就完了, 效率自然提升很多, 这也是 LinkedHashMap 中存在单向链表的意义所在.
接下来我们分析 get 源码:
- @Override
- public V get(Object key) {
- /*
- * This method is overridden to eliminate the need for a polymorphic
- * invocation in superclass at the expense of code duplication.
- */
- if (key == null) {
- HashMapEntry<K, V> e = entryForNullKey;
- if (e == null)
- return null;
- if (accessOrder)
- makeTail((LinkedEntry<K, V>) e);
- return e.value;
- }
- int hash = Collections.secondaryHash(key);
- HashMapEntry<K, V>[] tab = table;
- for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
- e != null; e = e.next) {
- K eKey = e.key;
- if (eKey == key || (e.hash == hash && key.equals(eKey))) {
- if (accessOrder)
- makeTail((LinkedEntry<K, V>) e);
- return e.value;
- }
- }
- return null;
- }
7-14 行我们不做详细分析, 就是获取 key 的 null 的情况, 比较简单, 自己看看就行了.
16 行, 计算 key 的二次 hash 值, 上一篇分析 HashMap 的时候已经分析过, 不在分析.
17 行, 获取 table 数组.
18-26 行, 就是遍历 key 所在行的单向链表, 21 行如果链表中有此数据则执行 24 行逻辑返回对应数据, 如果循环整个所在行单向链表都没有那么执行 27 行逻辑返回 null, 表明链表中没有我们要获取的数据.
22-23 行, 核心所在, 我们说 LinkedHashMap 可以控制数据是插入排序还是访问排序, 这里 get 方法显示就是对数据的访问, 如果我们设 accessOrder 为 true, 表明我们想让 LinkedHashMap 数据基于访问排序, 则执行 makeTail 方法.
接下来我们看下 makeTail 都做了什么.
六, LinkedHashMap 中访问排序的实现
直接分析 makeTail 方法源码:
- private void makeTail(LinkedEntry<K, V> e) {
- // Unlink e
- e.prv.nxt = e.nxt;
- e.nxt.prv = e.prv;
- // Relink e as tail
- LinkedEntry<K, V> header = this.header;
- LinkedEntry<K, V> oldTail = header.prv;
- e.nxt = header;
- e.prv = oldTail;
- oldTail.nxt = header.prv = e;
- modCount++;
- }
又是对链表的操作, 而且还是双向链表, 很多同学估计一看就发愁了, 静下心来, 其实没那么难.
假设原链表如图所示:
此时访问数据1, 我们看下 makeTail 是如何处理数据1的.
3 行, 将 e 所在节点的 prv 指针指向的节点的 nxt 指针指向 e 所在节点的 nxt 指针指向的节点, 真是拗口.
4 行, 同理.
其实 3,4 行逻辑就是将 e 所在节点从链表中断开, 执行完 3,4 行逻辑, 图示如下:
主要信息图中已经体现, 不在过多解释.
7,8 行分别获取 header 与 oldTail 节点.
9 行, 将 e 所在节点的 nxt 指针指向 header 节点.
10 行, 将 e 所在节点的 prv 指针指向 oldTail 节点.
9,10 行执行完, 数据结构图示如下:
11 行, oldTail 所在节点的 nxt 指针指向 e,header 所在节点的 prv 指针指向 e,11 行完图示如下:
这样 e 所在节点就插入了链表的尾部, 成为最新的数据.
makeTail 方法就是将我们访问的数据通过调整指针的指向来将访问的节点调整到队列的尾部, 成为最新的数据. 是不是很简单?
七, 总结
到此我想讲的就都完了, 本篇希望你掌握 LinkedHashMap 的数据结构, 记住有个单向链表啊, 不仅仅是双向链表, 否则 get 方法的逻辑你是看不懂的.
此外, 掌握访问排序到底怎么实现的, 其实很简单, 就是对双向链表的操作.
好了, 本篇到此结束, 希望对你有用, 真好!!!!!!, 咱们下篇见.
来源: https://www.cnblogs.com/leipDao/p/9598790.html