数据结构-LinkdHashMap

本系列主要是针对常用的几个数据结构的源码解析, 本篇主要是针对LinkedHashMap的源码解析, 本篇源码依赖于Android SDK -29版本

在前两年, 为了看LruCache, 曾经粗略得看过 LinkedHashMap的原理, 并了解了下HashMap的几个关键方法的原理, 最近重新看这块的代码, 又发现一些新的心得, 决定把LinkedHashMap单独开一篇写一下.

HashMap基本原理

在理解LinkedHashMap之前, 我们再回顾下HashMap的基本原理. HashMap内部维护了一个数组table(哈希桶), 这个数组内的元素是Node类型, 正常情况下, Node对象内部会维护一个指向下一个Node对象的引用, 这样就形成了一个单向链表, 而当这个单向链表的长度超过8的情况下, 会转为TreeNode树节点对象, 它继承于LinkedHashMap内的节点类LinkedHashMapEntry, 所以我们都会说HashMap是通过数组+链表/红黑树组成的一张哈希表.

通过构造函数, 我们可以传递两个值进去, 分别是初始容量initialCapacity和负载因子loadFactor, 初始容量决定了我们哈希桶的大小, 而负载因子决定了我们何时进行扩容.

当我们通过HashMap#put方法填充元素的时候, 首先会计算key的hash值, 通过(n - 1) & hash以此作为哈希桶的下标索引.

当首次填充数据的时候, 会进行初始扩容, 这里的插入判断可分为以下几个步骤

1. 根据hash计算索引位置, 替换或者插入相关节点
   1. 若哈希桶对应索引位置无值, 则通过HashMap#newNode新建新的链表节点, 并插入
   2. 若对应索引位置有内容, 如果当前头部节点的hash和key值都能对上, 则直接替换节点内容
   3. 若对应索引位置节点为链表节点, 则遍历查询, 如果hash和key能对上, 则替换节点内容; 否则在链表尾部通过HashMap#newNode新建新的链表节点, 并接入. 然后判断链表长度是否超过8, 若超过, 则转为树节点, 如果新增树节点, 则会通过HashMap#newTreeNode新建树节点
   4. 若对应索引位置节点为树节点, 则树节点插入.
2. 如果是节点值替换, 则返回老的值, 并触发afterNodeAccess回调
3. 如果是节点新增
   1. 触发afterNodeInsertion回调
   2. 如果键值对数量超过阈值大小, 则触发扩容机制

删的流程比较简单, 通过hash值以及key值匹配对应节点, 进行节点摘除即可, 后触发afterNodeRemoval回调

查也一样, 也是通过hash值和key值匹配对应的节点

扩容我们分为两个步骤

1. 计算新容量和新阈值
   1. 初始化哈希桶时的扩容, 则初始阈值为初始容量(默认16)*负载因子(默认0.75)
   2. 如果哈希桶已初始, 则每次扩容以之前容量的2的幂次增长, 同时阈值永远为容量*负载因子
2. 初始化新容量的哈希桶, 并将老哈希桶的键值对重新映射到新的哈希桶中
   1. 如果老哈希桶中对应索引的节点为链表节点, 则根据hash & oldCap==0来进行链表分组, 分别指向对应的索引位置.
   2. 如果是树节点, 则进行拆分处理

LinkedHashMap原理

在已经大致略过HashMap的基础原理后, 我们再回过头来看LinkedHashMap, 它集成于HashMap, 大体的处理逻辑都来自HashMap.

在前面简述的HashMap的流程内, 我们知道当插入一个新增的节点, 我们都会调用到HashMap#newNode方法, LinkedHashMap在新建节点的时候, 返回的是他内部的LinkedHashMapEntry节点类, 然后通过调用linkNodeLast(newNode)方法进行内部维护的双向链表的顺序维护, 在LinkedHashMap内维护了两个对象head和tail, 分别代表内部的维护的双向链表的头部和尾部节点, 在新增节点的时候, 会将对应新增的节点插入到这个链表的尾部, 在新增树节点的时候, 先会做相同的处理, 将对应新增节点放在维护的双向链表尾端

1
2
3
4
5
6
7
8
9
10

private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

在对应哈希桶内成功插入相关节点后, 如果是原来对应的key对应的位置有节点的情况下, 那么会触发到afterNodeAccess回调, 这个方法在LinkedHashMap内被继承实现, 当我们插入数据的时候, 原来的key值对应存在节点时, 这个节点的值会被覆盖, 而这个节点就是afterNodeAccess方法的入参e, 在访问到的这个老节点(值已被覆盖)时, 会通过afterNodeAccess方法, 将这个老节点插入到双向链表的尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e,
                    b = p.before,
                    a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

最后, 在是存在新增节点的时候, (即不存在对应key的老节点), 最后会回调到afterNodeInsertion方法, 他也在LinkedHashMap中实现

1
2
3
4
5
6
7

void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

在通过重载LinkedHashMap#removeEldestEntry(Map.Entry<K,V> eldest)配置删除最老的节点时, 会直接通过HashMap#removeNode移除对应的节点, 而对于LinkedHashMap来说最老的节点, 就是它内部维护的双向链表的头部节点.

而移除对应节点, 最终会触发afterNodeRemoval(node)回调, 这里的node是对应的被删除的节点, 在对应的回调里, LinkedHashMap又会对双向链表进行维护, 把对应的节点移除.

1
2
3
4
5
6
7
8
9
10
11
12
13

void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMapEntry<K,V> p =
            (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

LinkedHashMap覆写了get方法, 相比HashMap主要增加下触发节点访问回调afterNodeAccess, 当我们通过构造函数配置需要以访问顺序排序时, 会将查找的对应的节点维护放到双向链表的尾部.

1
2
3
4
5
6
7
8

public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

由此, 我们才可以真正理解LinkedHashMap如果对内部节点进行顺序维护