一、摘要
在集合系列的第一章，咱们了解到，map的实现类有hashmap、linkedhashmap、treemap、identityhashmap、weakhashmap、hashtable、properties等等。
本文主要从数据结构和算法层面，探讨linkedhashmap的实现。
（推荐学习：java视频教程）
二、简介
linkedhashmap可以认为是hashmap+linkedlist，它既使用hashmap操作数据结构，又使用linkedlist维护插入元素的先后顺序，内部采用双向链表（doubly-linked list）的形式将所有元素（ entry ）连接起来。
linkedhashmap继承了hashmap，允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linkedlist和hashmap的混合体，也就是说它同时满足hashmap和linkedlist的某些特性，可将linkedhashmap看作采用linked list增强的hashmap。
打开 linkedhashmap 源码，可以看到主要三个核心属性：
public class linkedhashmap<k,v>    extends hashmap<k,v>    implements map<k,v>{    /**双向链表的头节点*/    transient linkedhashmap.entry<k,v> head;    /**双向链表的尾节点*/    transient linkedhashmap.entry<k,v> tail;    /**      * 1、如果accessorder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序      * 2、如果accessorder为false的话，则按插入顺序来遍历      */      final boolean accessorder;}
linkedhashmap 在初始化阶段，默认按插入顺序来遍历
public linkedhashmap() {        super();        accessorder = false;}
linkedhashmap 采用的 hash 算法和 hashmap 相同，不同的是，它重新定义了数组中保存的元素entry，该entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。
源码如下：
static class entry<k,v> extends hashmap.node<k,v> {        //before指的是链表前驱节点，after指的是链表后驱节点        entry<k,v> before, after;        entry(int hash, k key, v value, node<k,v> next) {            super(hash, key, value, next);        }}
可以直观的看出，双向链表头部插入的数据为链表的入口，迭代器遍历方向是从链表的头部开始到链表尾部结束。
除了可以保迭代历顺序，这种结构还有一个好处：迭代linkedhashmap时不需要像hashmap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说linkedhashmap的迭代时间就只跟entry的个数相关，而跟table的大小无关。
三、常用方法介绍
3.1、get方法
get方法根据指定的key值返回对应的value。该方法跟hashmap.get()方法的流程几乎完全一样，默认按照插入顺序遍历。
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;}
如果accessorder为true的话，会把访问过的元素放在链表后面，放置顺序是访问的顺序
void afternodeaccess(node<k,v> e) { // move node to last        linkedhashmap.entry<k,v> last;        if (accessorder && (last = tail) != e) {            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)                a.before = b;            else                last = b;            if (last == null)                head = p;            else {                p.before = last;                last.after = p;            }            tail = p;            ++modcount;        }}
测试用例：
public static void main(string[] args) {        //accessorder默认为false        map<string, string> accessorderfalse = new linkedhashmap<>();        accessorderfalse.put(1,1);        accessorderfalse.put(2,2);        accessorderfalse.put(3,3);        accessorderfalse.put(4,4);        system.out.println(acessorderfalse：+accessorderfalse.tostring());                //accessorder设置为true        map<string, string> accessordertrue = new linkedhashmap<>(16, 0.75f, true);        accessordertrue.put(1,1);        accessordertrue.put(2,2);        accessordertrue.put(3,3);        accessordertrue.put(4,4);        accessordertrue.get(2);//获取键2        accessordertrue.get(3);//获取键3        system.out.println(accessordertrue：+accessordertrue.tostring());}
输出结果：
acessorderfalse：{1=1, 2=2, 3=3, 4=4}accessordertrue：{1=1, 4=4, 2=2, 3=3}
3.2、put方法
put(k key, v value)方法是将指定的key, value对添加到map里。该方法首先会调用hashmap的插入方法，同样对map做一次查找，看是否包含该元素，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，将元素插入集合。
/**hashmap 中实现*/public v put(k key, v value) {    return putval(hash(key), key, value, false, true);}final v putval(int hash, k key, v value, boolean onlyifabsent,                   boolean evict) {        node<k,v>[] tab; node<k,v> p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newnode(hash, key, value, null);        else {            node<k,v> e; k k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof treenode)                e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);            else {                for (int bincount = 0; ; ++bincount) {                    if ((e = p.next) == null) {                        p.next = newnode(hash, key, value, null);                        if (bincount >= treeify_threshold - 1) // -1 for 1st                            treeifybin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                v oldvalue = e.value;                if (!onlyifabsent || oldvalue == null)                    e.value = value;                afternodeaccess(e);                return oldvalue;            }        }        ++modcount;        if (++size > threshold)            resize();        afternodeinsertion(evict);        return null;}
linkedhashmap 中覆写的方法
// linkedhashmap 中覆写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);    // 将 entry 接在双向链表的尾部    linknodelast(p);    return p;}private void linknodelast(linkedhashmap.entry<k,v> p) {    linkedhashmap.entry<k,v> last = tail;    tail = p;    // last 为 null，表明链表还未建立    if (last == null)        head = p;    else {        // 将新节点 p 接在链表尾部        p.before = last;        last.after = p;    }}
3.3、remove方法
remove(object key)的作用是删除key值对应的entry，该方法实现逻辑主要以hashmap为主，首先找到key值对应的entry，然后删除该entry（修改链表的相应引用），查找过程跟get()方法类似，最后会调用 linkedhashmap 中覆写的方法，将其删除！
/**hashmap 中实现*/public v remove(object key) {    node<k,v> e;    return (e = removenode(hash(key), key, null, false, true)) == null ?        null : e.value;}final node<k,v> removenode(int hash, object key, object value,                           boolean matchvalue, boolean movable) {    node<k,v>[] tab; node<k,v> p; int n, index;    if ((tab = table) != null && (n = tab.length) > 0 &&        (p = tab[index = (n - 1) & hash]) != null) {        node<k,v> node = null, e; k k; v v;        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            node = p;        else if ((e = p.next) != null) {            if (p instanceof treenode) {...}            else {                // 遍历单链表，寻找要删除的节点，并赋值给 node 变量                do {                    if (e.hash == hash &&                        ((k = e.key) == key ||                         (key != null && key.equals(k)))) {                        node = e;                        break;                    }                    p = e;                } while ((e = e.next) != null);            }        }        if (node != null && (!matchvalue || (v = node.value) == value ||                             (value != null && value.equals(v)))) {            if (node instanceof treenode) {...}            // 将要删除的节点从单链表中移除            else if (node == p)                tab[index] = node.next;            else                p.next = node.next;            ++modcount;            --size;            afternoderemoval(node);    // 调用删除回调方法进行后续操作            return node;        }    }    return null;}
linkedhashmap 中覆写的 afternoderemoval 方法
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;    // b 为 null，表明 p 是头节点    if (b == null)        head = a;    else        b.after = a;    // a 为 null，表明 p 是尾节点    if (a == null)        tail = b;    else        a.before = b;}
四、总结
linkedhashmap 继承自 hashmap，所有大部分功能特性基本相同，二者唯一的区别是 linkedhashmap 在hashmap的基础上，采用双向链表（doubly-linked list）的形式将所有 entry 连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。
主体部分跟hashmap完全一样，多了header指向双向链表的头部，tail指向双向链表的尾部，默认双向链表的迭代顺序就是entry的插入顺序。
本文来自，java教程栏目，欢迎学习！
以上就是深入浅出分析linkedhashmap（图文）的详细内容。