当前位置：首页 > news >正文

认识LinkedHashMap

news 2025/6/14 15:51:46

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桶之外，同时按照存储数据的先后顺序创建双向链表。