Java JDK1.8（五） - LinkedHashMap源码解析
LinkedHashMap
|
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> |
LinkedHashMap继承自HashMap，底层依然是基于拉链式散列结构，并且是在HashMap的基础上，通过维护一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序的一致性问题，即维持键值对的插入顺序，同时通过对链表的相应操作，实现了访问顺序的相关逻辑。
LinkedHashMap对访问顺序提供了相关的支持，在一些场景下，这些特性还是很有用的，比如缓存（LRU算法[系列首篇文章]）。
LinkedHashMap在实现上很多方法直接继承自HashMap，仅为维护双向链表复写了部分方法，所以在看LinkedHashMap之前要先了解HashMap底层，建议看此系列的上一篇HashMap源码分析文章。
可以看到LinkedHashMap并没有添加、删除方法，因此LinkedHashMap的部分方法都是来自父类HashMap的。
LinkedHashMap是继承自HashMap，那么自然HashMap的负载因子这些都是有的，这些在HashMap讲过就不在细细叙述了。
|
//===================== 继承自HashMap Start =====================
/** * 存储的表 */ transient Node<K,V>[] table;
/** * 实际存储的K-V键值对的个数 */ transient int size;
/** * 阈值，当table == {}时，初始化容量默认为16，当table被填充了，也就是为table分配内存空间后， * threshold一般为capacity * loadFactory，超过就会扩容 */ int threshold;
/** * 负载因子，代表了table的填充度有多少，默认是0.75，加载因子存在的原因在于减缓哈希冲突， * 如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。 * 所以加载因子默认为0.75，也就是说大小为16的HashMap，到了13个元素，就会扩容成为32。 */ final float loadFactor;
/** * HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时， * 如果期间其他线程的参与导致HashMap结构出现变化了，就需要抛出ConcurrentModificationException（ArrayList的Fail-Fast机制） */ transient int modCount;
//===================== 继承自HashMap End =====================
/** * LinkedHashMap中存储的节点类 * before和after表示前后元素，这是维护双向链表的基础。 */ static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
/** * 双向链表的头部元素，表示最久未使用的元素（旧数据） */ transient LinkedHashMap.Entry<K,V> head;
/** * 双向链表的末尾元素，表示最近使用的元素（新数据） */ transient LinkedHashMap.Entry<K,V> tail;
/** * 这个变量决定链表的存储方式，false按照插入顺序存储，true标识按照访问顺序存储（LRU算法） * 在构造器中可以看到，默认为false，即迭代时的输出顺序就是插入顺序，如插入1、2、3，输出1、2、3 * 若为true，输出顺序即节点访问顺序，如插入1、2、3，迭代之前访问了2，又访问了1，迭代出来就是3、2、1 */ final boolean accessOrder; |
构造器：
|
/** * 1、空构造参数，默认accessOrder=false，即插入顺序 */ public LinkedHashMap() { super(); accessOrder = false; }
/** * 2、指定初始化容量 *默认accessOrder=false，即插入顺序 * @param initialCapacity 初始容量 */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; }
/** * 3、指定初始化容量和负载因子 * 默认accessOrder=false，即插入顺序 * @param initialCapacity 初始化容量 * @param loadFactor 负载因子 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; }
/** * 4、指定初始化容量、负载因子、访问顺序类型 * * @param initialCapacity 初始化容量 * @param loadFactor 负载因子 * @param accessOrder 访问顺序方式，false插入顺序、true访问顺序 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
/** * 5、将一个Map包装成为LinkedHashMap * 默认accessOrder=false，即插入顺序 * @param m 要包装的Map */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } |
辅助方法putMapEntries：
可以看到这个方法也是来自于HashMap的。
|
/** * 读取Map中所有元素，转换成目标类型的Map * @param m 要包装的Map * @param evict 驱逐出去最老的节点，即LRU算法的最少使用节点 * */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //1、获取m的元素数量 int s = m.size(); //2、小于0就没有转换的意义了 if (s > 0) { //2.1、当前的表是否为空 if (table == null) { //2.1.1、根据m的元素数量和当前的表的加载因子，计算出阈值 float ft = ((float)s / loadFactor) + 1.0F;
//2.1.2、修正阈值边界，不能超过MAXIMUM_CAPACITY int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
//2.1.3、如果新的阈值>当前阈值，要满足2的n次方阈值 if (t > threshold) threshold = tableSizeFor(t); }
//2.2、table不为空，而且m的元素数量大于阈值 else if (s > threshold) //2.2.1、扩容 resize();
//2.3、遍历m元素，依次放入表中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } |
在putMapEntries方法中可以看到，最后还是依旧是调用HashMap的putVal方法，即新增方法。
新增的钩子方法有afterNodeAccess()和afterNodeInsertion
|
/** * HashMap方法中的新增方法 * @param hash 新建K-V的key的哈希值 * @param key 新增的key * @param value 新增的value * @param onlyIfAbsent 如果是true，不改变键值对中的旧值 * @param evict 驱逐出去，即驱逐最老的节点，LRU算法 * @return V */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; //桶 Node<K,V> p; //当前桶位置元素的key int n, i; //当前元素位置
//1、判断table是否为空，或者table长度是否为0 if ((tab = table) == null || (n = tab.length) == 0) //1.2、在1的条件成立的情况下，调用resize()对容器进行扩容 n = (tab = resize()).length;
//2、计算插入元素在hash桶中的位置，并且这个位置如果没有元素，则将数据封装成一个Node对象 if ((p = tab[i = (n - 1) & hash]) == null) //2.1、新建一个Node tab[i] = newNode(hash, key, value, null);
else { //3、如果这个位置有元素则执行以下逻辑 Node<K,V> e; //当前桶位置元素 K k; //当前桶位置元素的key
//3.1、如果这个位置的元素的key和要插入的一样（hashCode一样，equals一样） if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //3.1.1、那么就替换一下，记录该节点到变量e e = p;
//3.2、判断该节点是否是树类型的节点 else if (p instanceof TreeNode) //3.2.1、是树类型节点，就按照树类型的添加方法进行添加 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.3、第一个元素即不是和插入的节点相同，又不是树类型的节点，那么则遍历链表 else { //3.3.1、遍历链表 for (int binCount = 0; ; ++binCount) { //3.3.1.1、先将下一个节点赋给e，如果该节点为空，则表示已经遍历到链表的最后了 if ((e = p.next) == null) { //3.3.1.1.1、新建一个节点并加入到末尾 p.next = newNode(hash, key, value, null);
//3.3.1.1.2、此时判断链表长度是否大于8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //3.3.1.1.2.1、链表大于8，则将链表转换为红黑树 treeifyBin(tab, hash); break; } //3.3.1.2、如果某个节点和要插入的节点相同，则跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;
//3.3.1.3、由于在3.3.1.1中p已经把下一个节点给了，e因此， //此时p重新拿到下一个节点，重新进入循环，在回到3.3.1.1中又会把下一个节点给到e，不断循环 p = e; } }
//3.4、此时e节点中记录的是hashMap中与要插入的节点相同的节点，在这里统一进行处理 if (e != null) { //3.4.1、记录旧的value值 V oldValue = e.value; //3.4.2、通过对onlyIfAbsent与oldValue的值判断是否需要覆盖，需要则覆盖 if (!onlyIfAbsent || oldValue == null) e.value = value;
//此方法与LinkedHashMap相关，是一个回调方法，在HashMap中没有任何作用 afterNodeAccess(e);
//3.4.3、返回旧的值 return oldValue; } } //4、操作+1，与之前的ArrayList的Fail-Fast机制是一样的 ++modCount; //5、判断是否需要进行扩容 if (++size > threshold) //5.1、调用resize()方法进行扩容 resize();
//6、此方法也是与LinkedHashMap相关的方法，在HashMap中没有任何作用 afterNodeInsertion(evict); return null; }
//============== putVal - 涉及LinkedHashMap的方法 Start ==============
/** * 新建一个节点 * @param hash key的hash值 * @param key 新增的key * @param value 新增的value * @param e 下一个节点 * @return Node<K,V> */ Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { //1、最终初始化的构造方法就是父类的HashMap.Node的构造方法 //key的hash值、新增的key、新增的value、下一个节点 LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//2、调用linkNodeLast，将新增节点放到链表的后面 linkNodeLast(p); return p; } /** * 新增节点放到链表的后面 * @param p 新增的节点 */ private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { //1、将当前已知最后的一个节点赋给临时变量last LinkedHashMap.Entry<K,V> last = tail;
//2、最后一个节点为当前节点p tail = p;
//3、如果当前已知的最后一个节点为空 if (last == null) //3.1、即当前节点为首节点 head = p;
//如果当前已知节点的最后一个节点不为空 else { //当前节点的上一个节点为已知最后的一个节点，即last p.before = last; //将p节点连接到链表的末尾 last.after = p; } }
/** * 将当前被访问的节点e，移动到内部的双向链表的尾部，并且将节点e之后的元素往前移动 * @param e 当前节点 */ void afterNodeAccess(Node<K,V> e) { //1、原来的尾节点 LinkedHashMap.Entry<K,V> last;
//2、如果accessOrder是true（输出顺序是节点的访问顺序），且原尾节点不等于e，即当前节点e不是尾节点，不然就没有必要移动了 if (accessOrder && (last = tail) != e) { //2.1、将节点e强制转换为LinkedHashMap.Entry，b为这个节点的前一个节点，a为它的后一个节点。 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//2.2、p为尾节点，后置节点必然是空 p.after = null;
//2.3、如果p的前一个节点是null，则p以前是开始节点（首节点） if (b == null) //2.3.1、要把p移动到链表的尾部，所以现在更新的头节点是p的后置节点a head = a; //2.4、如果p不是首节点 else //2.4.1、将p的前节点b的后置节点设置为，原有p的后节点a //原 b p a //现 b a p b.after = a;
//2.5、如果p的后置节点a不是为空 if (a != null) //2.5.1、p的后置节点a的前置节点，为p的前置节点b //原 b p a //现 b a p a.before = b; //2.6、如果p的后置节点a为空 else //2.6.1、那么说明p就是尾节点，此时last引用更新为p的前置节点b //last b p last = b;
//2.7、原本尾节点是空，则链表中就一个节点 if (last == null) //2.7.1、p就是首节点 head = p; //2.8、如果尾节点不为空 else { //2.8.1、当前节点p的前置节点为这个last尾节点，last的后置节点是p p.before = last; last.after = p; }
//2.9、尾节点引用赋值为p tail = p; //2.10、修改操作次数+1 ++modCount; } }
/** * 判断是否需要移除最老的元素 * 注：这个方法需要重写removeEldestEntry方法才能实现， * 因为该方法默认返回false，即不删除，也有可能是作为钩子给子类用 * @param evict 是否驱逐，true驱逐，false不驱逐 */ void afterNodeInsertion(boolean evict) { //1、定义临时变量first LinkedHashMap.Entry<K,V> first;
//2、把首元素赋给临时变量first，但是进入removeEldestEntry方法会发现是返回false，所以除非重写 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
//============== putVal - 涉及LinkedHashMap的方法 End ============== |
删除：钩子方法有afterNodeRemoval()。
|
/** * 删除指定的key对应的Entry * @param key 要删除的节点的key * @return V 1、返回被删除的Value，2、返回null，说明key可能不存在（可用containsKey方法确认），也有可能key对应的值就是null */ public V remove(Object key) { //1、临时变量，存储要删除的节点 Node<K,V> e;
//2、计算这个key的hash值，调用removeNode方法进行删除，并将要删除的节点赋给变量e //如果返回值是null，就返回null，否则返回被删除的节点的value return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
/** * 注：这个方法是final修饰，子类可以通过实现afterNodeRemoval方法来增强处理逻辑 * @param hash key的hash值 * @param key 要删除的Node的key * @param value 删除的Node的value，这个值作为是否删除的条件取决于matchValue是否为true * @param matchValue 如果为true，则key对应的Node的valueequals(vaue)为true时才删除，否则不关心value的值，即如果为true，说明key相同，value相同才删除 * @param movable 删除后是否移动节点，如果为false就不移动 * @return Node<K,V> */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
//1、临时变量 Node<K,V>[] tab; //存储节点的数组 Node<K,V> p; //当前节点 int n, //数组长度 index; //当前节点的索引值
//2、一系列的判断，避免为空，浪费查找资源 if ((tab = table) != null //先将节点数组变量赋给临时变量tab，判断这个数组不为空 && (n = tab.length) > 0 //将数组长度赋给临时变量n，判断这个长度>0 &&(p = tab[index = (n - 1) & hash]) != null) { //根据hash定位到节点对象，并赋给临时变量p（该节点为树的根节点或链表首节点） ，判断不为空
Node<K,V> node = null, //要返回的节点对象 e; //临时节点 K k; //键 V v; //值
//2.1、如果当前节点的key和传进来的key相等（hashCode && eqauls相等），那么当前节点就是要删除的节点 //当前节点的key赋值给临时变量k if (p.hash == hash && ( (k = p.key) == key || (key != null && key.equals(k)) ) ) //2.1.1、赋值给要返回的临时变量 node = p;
//2.2、到这说明首节点没有匹配上，那么将当前节点的下一个节点赋给变量e //如果没有next节点，就说明该节点所在的位置上没有发生hash碰撞，就一个节点并且还没有匹配上，也就没有这个节点，即没得删，直接返回null //如果存在next节点，说明这个数组位置上发生了hash碰撞，此时可能存在一个链表，也可能是一颗树 else if ((e = p.next) != null) { //2.2.1、判断是否是一个树 if (p instanceof TreeNode) //2.2.1.1、调用树结构查找节点的方法，获得要删除的节点 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//2.2.2、如果不是一个树类型的，那么说明是一个链表结构 else { //进入循环这个链表 do { //2.2.2.1、判断这个链表内的元素和当前元素是否key的hashCode && equals相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { //2.2.2.1.1、相等，直接将这个要删除的对象赋给临时变量node node = e; //2.2.2.1.2、终止循环，跳出 break; } //2.2.2.2、如果在2.2.2.1的判断条件中不相等，那么则将e赋给p，说明p永远指向就是下一次循环的e的父节点了，如果下一次匹配上了，p就是node的下一个节点。 p = e; //2.2.2.3、如果e存在下一个节点就继续匹配，直到某个节点跳出，或者遍历完链表所有节点 } while ((e = e.next) != null); } }
//2.3、如果node不为空，说明根据key匹配到了要删除的节点 //如果不需要对比value值，或需要对比value值，但是value值也相等 //那么就可以删除node节点了 if (node != null && ( !matchValue || (v = node.value) == value || (value != null && value.equals(v)) ) ) { //2.3.1、如果这个节点是树结构的节点，那么调用树的删除方法进行删除removeTreeNode if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//2.3.2、如果该节点不是树结构的节点，判断该节点是否是首节点 else if (node == p) //首节点删除的话，直接将该节点数组对应位置指向第二个节点即可 tab[index] = node.next;
//2.3.3、如果node节点不是首节点 else //2.3.3.1、此时p是node的父节点，由于要删除node，所有只需要把p的下一个节点指向node的下一个节点即可把node从链表删除 p.next = node.next;
//2.3.4、修改次数+1 ++modCount; //2.3.5、HashMap的容量 -1 --size; //2.3.6、这个方法没有任何实现逻辑，目的是让子类根据需要重写，并且是应用在LinkedHashMap的 afterNodeRemoval(node); return node; } } //3、没有找到返回null return null; }
//============== removeNode - 涉及LinkedHashMap的方法 Start ==============
/** * 删除节点e，同时将e从双向链表上删除 * @param e 要删除的节点 */ void afterNodeRemoval(Node<K,V> e) {
//1、将e节点强制转换为LinkedHashMap.Entry，b为这个节点的前一个节点，a为后一个节点 LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//2、将当前节点的前后节点都置空 p.before = p.after = null;
//3、如果当前节点的前置节点为空 if (b == null) //3.1、说明上一个节点接着的，应该是当前节点的后置节点a head = a; //4、如果当前节点的前置节点不为空 else //4.1、当前节点的前置节点的后一个节点为当前节点的后一个节点a //b p a //b a b.after = a;
//5、如果当前节点的后置节点为空 if (a == null) //5.1、尾节点应该是当前节点的前置节点 tail = b; //6、如果当前节点的后置节点不为空 else //6.1、当前节点的后置节点的上一个节点应该是当前节点的前置节点b //b p a //b a a.before = b; }
//============== removeNode - 涉及LinkedHashMap的方法 End ============== |
查找：从源码中可以发现，这个方法LinkedHashMap重写了。
|
/** * 根据key查找value * @param key 要查找的value的key * @return V */ public V get(Object key) { Node<K,V> e;
//调用父类HashMap的hash()方法获取到key的hash值，在调用getNode方法，获取到对应的节点 if ((e = getNode(hash(key), key)) == null) return null;
//accessOrder为true，即输出节点按照访问顺序，就是把当前这个节点放到链表的末尾 //1、2、3，访问1、2，此时遍历输出的结果是3、2、1 if (accessOrder) //调用afterNodeAccess()方法将当前这个节点放到列表末尾 afterNodeAccess(e); return e.value; }
//======================= getNode - 来自HashMap Start =======================
/** * 获取Node * @param hash key的hash值，即存储在数组的位置 * @param key key * @return Node<K,V> */ final Node<K,V> getNode(int hash, Object key) { //1、存放数组table（临时） Node<K,V>[] tab;
Node<K,V> first, //链表的第一个节点 e; //存放first的下一个节点 int n; //存放数组的长度 K k; //存放的key（临时）
//2、判断存放元素数组不为空，并且长度大于0，而且数组中首个元素不为空 if ((tab = table) != null //存放数组的table赋给临时的tab && (n = tab.length) > 0 //table的长度赋给临时变量n && (first = tab[(n - 1) & hash]) != null) { //获取数组里存放元素位置的的第一个链表元素
//2.1、判断存放在数组的第一个元素的hash值，是否和要查找的value的key的hash值相等，并且key也相等 //key的hashCode相等，equals也相等 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) //2.1.1、直接返回 return first;
//2.2、如果key和第一个元素不相等，那么则和第一个元素的下一个元素，即第二个元素比较，并将这个元素赋给变量e，进而判断e是否为空 if ((e = first.next) != null) { //2.2.1、第一个元素是否是树结构类型 if (first instanceof TreeNode) //2.2.1.1、按照树结构的查找方法进行查找，key的first为根节点 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//2.2.2、不是红黑树，那么就是一个普通的建表 do { //2.2.2.1、判断key的hashCode和equals是否同时相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //2.2.2.2.1.1、相等直接返回 return e;
//2.2.3、一直循环下一个节点，直到节点为null，结束循环 } while ((e = e.next) != null); } } //3、查找不到，返回null return null; }
//======================= getNode - 来自HashMap End =======================
/** * 将当前被访问的节点e，移动到内部的双向链表的尾部，并且将节点e之后的元素往前移动 * @param e 当前节点 */ void afterNodeAccess(Node<K,V> e) { //1、原来的尾节点 LinkedHashMap.Entry<K,V> last;
//2、如果accessOrder是true（输出顺序是节点的访问顺序），且原尾节点不等于e，即当前节点e不是尾节点，不然就没有必要移动了 if (accessOrder && (last = tail) != e) { //2.1、将节点e强制转换为LinkedHashMap.Entry，b为这个节点的前一个节点，a为它的后一个节点。 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//2.2、p为尾节点，后置节点必然是空 p.after = null;
//2.3、如果p的前一个节点是null，则p以前是开始节点（首节点） if (b == null) //2.3.1、要把p移动到链表的尾部，所以现在更新的头节点是p的后置节点a head = a; //2.4、如果p不是首节点 else //2.4.1、将p的前节点b的后置节点设置为，原有p的后节点a //原 b p a //现 b a p b.after = a;
//2.5、如果p的后置节点a不是为空 if (a != null) //2.5.1、p的后置节点a的前置节点，为p的前置节点b //原 b p a //现 b a p a.before = b; //2.6、如果p的后置节点a为空 else //2.6.1、那么说明p就是尾节点，此时last引用更新为p的前置节点b //last b p last = b;
//2.7、原本尾节点是空，则链表中就一个节点 if (last == null) //2.7.1、p就是首节点 head = p; //2.8、如果尾节点不为空 else { //2.8.1、当前节点p的前置节点为这个last尾节点，last的后置节点是p p.before = last; last.after = p; }
//2.9、尾节点引用赋值为p tail = p; //2.10、修改操作次数+1 ++modCount; } } |
总结
1、LinkedHashMap继承自Hashmap，并实现了HashMap中预留的钩子方法，因此不必重写HashMap的许多方法，这个设计也是很巧妙的设计。
2、LinkedHashMap和HashMap的结构是一样的，都是数组+链表/红黑树，并且扩容机制也是一样的，如默认容量为16，扩容因子默认为0.75都是继承自HashMap的。
3、LinkedHashMap底层使用双向链表来维护数据的（可以看成LinkedList+HashMap），HashMap是单链表，都是具有Fail-Fast机制的。
4、LinkedHashMap的存储顺序和添加顺序是一样的，即是有序的集合，可以根据accessOrder的值（false-插入顺序，true-访问顺序），来决定是否移动元素来达到LRU算法的实现。
5、put方法并没有重写，只是重写了newNode方法，并通过一系列辅助方法来把新构建的节点连接到双向链表的尾部。