java - 认识LinkedHashMap_个人文章

来源：恒创科技编辑：恒创科技编辑部

2024-01-30 00:00:59

LinkedHashMap是HashMap的子类，上一节初步分析过HashMap，这一节分析LinkedHashMap。

LinkedHashMap的数据结构

Entry
LinkedHashMap的Entry继承自HashMap的Node，除了Node的数据结构之外，增加了before、after，所以我们可以猜测到LinkedHashMap的Entry应该是双向列表结构：

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

此外，LinkedHashMap定义了首节点和尾结点：

    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

table数组
继承自HashMap,没有变化！

数据依然保存在table数组中，不同的是table中的对象变成了Entry。

LinkedHashMap的初始化

与HashMap的初始化方式、以及涉及到的容量、装载因子、扩容阈值等概念基本相同。

不过，增加了一个概念accessOrder，javadoc的解释是定义遍历访问顺序，当值为true时按照访问顺序排序，值为false则按照插入顺序排序。

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    final boolean accessOrder;

LinkedHashMap赋值

LinkedHashMap的赋值逻辑如下（假设待存放的数据为e<key1,value1>）：

检查table数组为空的话，初始化指定容量或者默认容量的table数组根据key1的哈希值计算得出（算法为（容量 - 1） & hash(key1）)对应的桶。这一步很重要，一般来讲优秀的hash算法能够尽可能确保不同的key值得到不同的hash值，也就可以确保放入不同的桶内。但是不可避免的，可能会存在不同key值得到相同hash值的情况（hash冲突：key1<>key2,hash(key1)=hash(key2)），这种情况下就会放置在相同的桶（比如table[5]）内。得到桶之后，判断桶内是否已经有数据。没有数据则直接新建一个Node：newNode(hash, key1, value1, null)，放在桶中，结束LinkedHashMap新建的Node是他的Entry对象，所以创建对象的过程与HashMap的略有不同：创建的是双向链表（通过before、after首尾相连），并在创建的过程中指定LinkedHashMap的head和tail。否则，桶内有数据，有两种情况：一是为键值key1重复赋值、二是hash冲突。如果是hash冲突，则new一个Node：newNode(hash, key1, value1, null)并将其设置为桶内的最后一个Node。如果是重复赋值（桶内数据的key值=key1），则为key1重新赋值value1，并返回key1的旧值

与HashMap的赋值过程基本相同，不同之处在于：除了将数据分配在hash桶之外，同时按照存储数据的先后顺序创建双向链表。

从LinkedHashMap获取数据

LinkedHashMap通过key值获取数据的逻辑与HashMap的完全一致

通过get（key）方法获取数据的逻辑如下（假设要获取的数据key=key1）：

table数组不为空并且数组长度大于0，则采用与put数据相同的算法得到key1值对应的桶。桶内不空则从第一个节点开始检查，如果节点key值等于key1，则返回该节点的value。如果第一个节点不满足条件，则依次检查桶内所有其他节点。桶内空，或者桶内不空但是没有找到满足条件的对象（应该不可能）则返回null，表明当前HashMap中不存在key值为key1的对象

所以我们可以看到，正如名称给我们的启示一样，LinkedHashMap与HashMap的区别就是多了一个链表

大家知道LinkedHashMap能够确保按照存储顺序获取数据，而HashMap遍历到的数据是随机的，下次我们就具体分析一下其底层原因。

本文地址：https://www.henghost.com/jishu/20158/