文章目录

前言
一、LinkedHashMap数据结构
二、源码分析
- 1.主要属性
- 2.构造函数
- 3.关键方法
- - 1、get(Object key)
  - 2、afterNodeAccess(Node e)
  - 3、afterNodeInsertion(boolean evict)
- 4.遍历方式
总结

前言

继承自HashMap，LinkedHashMap = HashMap + LinkedList，话不多说，直接上源码。

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

二、源码分析

1.主要属性

/** * 链表头结点 */
transient LinkedHashMap.Entry<K,V> head;

/** * 链表的尾节点 */
transient LinkedHashMap.Entry<K,V> tail;

/** * 是否按访问顺序，true-按访问顺序，false-按插入顺序 */
final boolean accessOrder;

2.构造函数

都是调用HashMap的构造函数，双向链表默认按插入顺序排列，也提供可选排列方式顺序的构造函数。

public LinkedHashMap() { 
    super();
    accessOrder = false; // 默认按插入顺序
}

public LinkedHashMap(int initialCapacity) { 
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) { 
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

3.关键方法

关键方法有两个，之前在分析HashMap源码的时候也提了一下，afterNodeAccess方法和afterNodeInsertion方法。那么首先我们来看下get方法。

1、get(Object key)

与HashMap的get方法相比，仅仅是多了一个访问顺序问题。

public V get(Object key) { 
   Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)// 仅仅是多了这个判断，如果为true，就要维护访问顺序
        afterNodeAccess(e);
    return e.value;
}

2、afterNodeAccess(Node e)

其实就是把传入的e节点放在双向链表的末尾。

void afterNodeAccess(Node<K,V> e) {  // move node to last
 LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {  // accessOrder为true且访问的节点不是链尾的节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 把访问节点的前节点后节点都标记好
        p.after = null;
        if (b == null)	// 说明当前访问节点是头节点，那就把它后节点放头结点
            head = a;
        else	// 不是头结点，那就直接把前节点的后指针指向后节点
            b.after = a;
        if (a != null) // 一般情况下都为true
            a.before = b;
        else
            last = b;
        if (last == null)// 如果链表中还没有元素，则将e设置为头结点
            head = p;
        else { //否则的话将e挪到链表末尾
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3、afterNodeInsertion(boolean evict)

这个方法表示插入之后是否删除最老的节点，即头结点。evict这个参数如果为true才可能会删除。但是我看了调用这个方法的地方传入的都是true。除了构造函数调用、克隆时为false。

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

刚开始看源码的时候很好奇这个head是在哪里赋值了？于是我找到了put方法，新建节点的时候做了如下事情：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);// 这个方法做了啥呢？
    return 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;
    }
}

由此可见put的时候就默认把元素按插入顺序排好了，如果accessOrder为false的话那这个双向链表的顺序就不会变了，即按插入顺序排列，如果accessOrder为true，则按访问顺序排列。

4.遍历方式

还记得HashMap遍历方式是怎么遍历的吗？先从数组下标0开始遍历链表，直到遍历到最后一个数组下标的链表末尾。
但是LinkedHashMap也是这样遍历的吗？我们来看看。

abstract class LinkedHashIterator { 
   LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() { 
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() { 
        return next != null;
    }
	// 关键是获取下一个元素的方法，我们可以看到，直接用的是双向链表的方式，so easy
    final LinkedHashMap.Entry<K,V> nextNode() { 
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }

    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遍历只能说招式是一样的，提供一样的遍历api，结构也是一样的，但是遍历方式本质上完全不一样。

总结

LinkedHashMap是基于HashMap做的操作，所以阅读完HashMap源码再来看LinkedHashMap源码显得很简单。

加油吧，骚年！

本文地址：https://blog.csdn.net/Soldier_son/article/details/110001988

LinkedHashMap比HashMap多了啥？