Java LinkedHashMap 底层实现原理分析-编程学习网


import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>();
        map.put("ahdjkf", "1");
        map.put("ifjdj", "2");
        map.put("giafdja", "3");
        map.put("agad", "4");
        map.put("ahdjkge", "5");
        map.put("iegnj", "6");
        System.out.println("LinkedHashMap的迭代顺序(accessOrder=false)：");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
        map1.put("ahdjkf", "1");
        map1.put("ifjdj", "2");
        map1.put("giafdja", "3");
        map1.put("agad", "4");
        map1.put("ahdjkge", "5");
        map1.put("iegnj", "6");

        map1.get("ahdjkf");
        map1.get("ifjdj");
        System.out.println("LinkedHashMap的迭代顺序(accessOrder=true)：");
        Iterator iterator1 = map1.entrySet().iterator();
        while (iterator1.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator1.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map2 = new HashMap<>();
        map2.put("ahdjkf", "1");
        map2.put("ifjdj", "2");
        map2.put("giafdja", "3");
        map2.put("agad", "4");
        map2.put("ahdjkge", "5");
        map2.put("iegnj", "6");

        System.out.println("HashMap的迭代顺序：");    
        Iterator iterator2 = map2.entrySet().iterator();
        while (iterator2.hasNext()) {
            Map.Entry aMap = (Map.Entry) iterator2.next();
            System.out.println(aMap.getKey() + "=" + aMap.getValue());
        }
    }
}
Output：
LinkedHashMap的迭代顺序(accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap的迭代顺序(accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap的迭代顺序：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5

可以看到 LinkedHashMap在每次插入数据，访问、修改数据时都会调整链表的节点顺序。以决定迭代时输出的顺序。

下面我们来看LinkedHashMap具体是怎么实现的：

LinkedHashMap继承了HashMap，内部静态类Entry继承了HashMap的Entry，但是LinkedHashMap.Entry多了两个字段：before和after，before表示在本节点之前添加到LinkedHashMap的那个节点，after表示在本节点之后添加到LinkedHashMap的那个节点，这里的之前和之后指时间上的先后顺序。


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);
    }
}

同时类里有两个成员变量head和tail,分别指向内部双向链表的表头、表尾。


//双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
//双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;

将LinkedHashMap的accessOrder字段设置为true后，每次访问哈希表中的节点都将该节点移到链表的末尾，表示该节点是最新访问的节点。即循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点。

由于增加了一个accessOrder属性，LinkedHashMap相对HashMap来说增加了一个构造方法用来控制迭代顺序。


final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//指定初始化时的容量，
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子，以及迭代输出节点的顺序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
//利用另一个Map 来构建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //该方法上文分析过，批量插入一个map中的所有数据到 本集合中。
    putMapEntries(m, false);
}

添加元素

LinkedHashMap在添加元素的时候，依旧使用的是HashMap中的put方法。不同的是LinkedHashMap重写了newNode()方法在每次构建新节点时，通过linkNodeLast(p);将新节点链接在内部双向链表的尾部。


//将新增的节点，连接在链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    //如果集合之前是空的
    if (last == null)
        head = p;
    else {//将新节点连接在链表的尾部
        p.before = last;
        last.after = p;
    }
}

删除元素

LinkedHashMap并没有重写HashMap的remove()方法，但是他重写了afterNodeRemoval()方法，这个方法的作用是在删除一个节点时，同步将该节点从双向链表中删除。该方法将会在remove中被回调。


//在删除节点e时，同步将e从双向链表上删除
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //将待删除节点 p 的前置后置节点都置空
    p.before = p.after = null;
    //如果前置节点是null，则说明现在的头结点应该是后置节点a
    if (b == null)
        head = a;
    else//否则将前置节点b的后置节点指向a
        b.after = a;
    //同理如果后置节点时null ，则尾节点应是b
    if (a == null)
        tail = b;
    else//否则更新后置节点a的前置节点为b
        a.before = b;
}

删除过程总的来说可以分为三步：

根据 hash 定位到桶位置
遍历链表或调用红黑树相关的删除方法
回调afterNodeRemoval，从 LinkedHashMap 维护的双链表中移除要删除的节点

更新元素


// 清除节点时要将头尾节点一起清除 
public void clear() {
    super.clear();
    head = tail = null;
}

查找元素

LinkedHashMap重写了get()和getOrDefault()方法
默认情况下，LinkedHashMap是按插入顺序维护链表。不过如果我们在初始化 LinkedHashMap时，指定 accessOrder参数为 true，即可让它按访问顺序维护链表。访问顺序的原理是，当我们调用get/getOrDefault/replace等方法时，会将这些方法访问的节点移动到链表的尾部。


public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 回调afterNodeAccess(Node<K,V> e)
        afterNodeAccess(e);  // 将节点e移至双向链表的尾部（保证迭代顺序）
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);    // 作用同上
   return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;//原尾节点
    //如果accessOrder 是true ，且原尾节点不等于e
    if (accessOrder && (last = tail) != e) {
        //节点e强转成双向链表节点p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //p现在是尾节点， 后置节点一定是null
        p.after = null;
        //如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a
        if (b == null)
            head = a;
        else//否则更新p的前直接点b的后置节点为 a
            b.after = a;
        //如果p的后置节点不是null，则更新后置节点a的前置节点为b
        if (a != null)
            a.before = b;
        else//如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b
            last = b;
        if (last == null) //原本尾节点是null  则，链表中就一个节点
            head = p;
        else {//否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p
            p.before = last;
            last.after = p;
        }
        //尾节点的引用赋值成p
        tail = p;
        //修改modCount。
        ++modCount;
    }
}
// 因为LinkedHashMap中维护了一个双向链表所以相对于HashMap中的双重循环遍历这个方法要优化很多
LinkedHashMap
public boolean containsValue(Object value) {     
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {   // 通过双向链表来遍历
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}
HashMap
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

其他方法

LinkedHashMap还有一个比较神奇的存在。


void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除最近最少被访问的节点
    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;
}

上面的方法一般不会被执行，但是当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。

迭代器


public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        //返回LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
    }
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
    abstract class LinkedHashIterator {
        //下一个节点
        LinkedHashMap.Entry<K,V> next;
        //当前节点
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;
        LinkedHashIterator() {
            //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头
            next = head;
            //记录当前modCount，以满足fail-fast
            expectedModCount = modCount;
            //当前节点为null
            current = null;
        }
        //判断是否还有next
        public final boolean hasNext() {
            //就是判断next是否为null，默认next是head  表头
            return next != null;
        }
        //nextNode() 就是迭代器里的next()方法 。
        //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
        final LinkedHashMap.Entry<K,V> nextNode() {
            //记录要返回的e。
            LinkedHashMap.Entry<K,V> e = next;
            //判断fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //如果要返回的节点是null，异常
            if (e == null)
                throw new NoSuchElementException();
            //更新当前节点为e
            current = e;
            //更新下一个节点是e的后置节点
            next = e.after;
            //返回e
            return e;
        }
        //删除方法 最终还是调用了HashMap的removeNode方法
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。

总结

在日常开发中LinkedHashMap 的使用频率没有HashMap高，但它也个重要的实现。
在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。
HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。
LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。
TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。具体实现我们下次分析。

以上就是Java LinkedHashMap 底层实现原理分析的详细内容，更多关于Java LinkedHashMap 底层实现原理的资料请关注编程网其它相关文章！

文章详情

Java LinkedHashMap 底层实现原理分析

目录

添加元素

删除元素

更新元素

查找元素

其他方法

迭代器

总结

软考中级精品资料免费领

相关文章

猜你喜欢

Java LinkedHashMap 底层实现原理分析

Java中LinkedHashMap 的底层原理是什么

Java中集合底层原理分析

Java并发编程之synchronized底层实现原理分析

HashMap底层原理分析

Java中SynchronousQueue的底层实现原理剖析

Spring Boot底层原理实例分析

Java@Autowired注解底层原理详细分析

源码分析Java中ThreadPoolExecutor的底层原理

微信小程序底层的实现原理分析

hashmap底层实现原理

Spring底层原理深入分析

synchronized底层实现原理

C语言函数调用底层实现原理分析

Java同步关键字synchronize底层实现原理解析

HashMap的底层实现原理

Javasynchronized底层的实现原理

微信小程序底层实现原理的示例分析

java并发编程synchronized底层实现原理

Java必会的Synchronized底层原理剖析