[Java知识库] HashMap无序的这个小“坑“，一不小心就翻车了

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Java知识库 -> HashMap无序的这个小“坑“，一不小心就翻车了 -> 正文阅读

[Java知识库]HashMap无序的这个小“坑“，一不小心就翻车了

大家好，我是一航；

昨天一位粉丝朋友和我聊天，说遇到了一个莫名奇妙的问题，让我帮着分析一下；经过他的一轮描述，发现是一个HashMap元素顺序小’坑’；但是一不留神，老司机也容易在这里翻车。

一句话来描述一下他的问题：明明我数据库语句使用了Order by进行了排序，日志中也看到数据是按顺序查出来了，但业务层收到数据依然还是乱序的呢？；

整个过程，确实出现了好几处的迷惑现象，影响了他对问题的判断；下面就从一个小案例加上源码分析，来看看到底发生了什么。

问题复现

为了方便说明问题，这里用一个简单的业务场景来模拟一下；

数据表

一张简单的学生信息表

需求

需要按id顺序（order by id）获取出学号（student_id）对应的学生信息；为了方便业务层面根据学号获取数据，这位朋友采用了如下的数据格式，并用了HashMap在业务代码中接收数据：

{
	"S000001": {
		"name": "张三",
		"student_id": "S000001",
		"age": 7
	},
	"S000002": {
		"name": "李四",
		"student_id": "S000002",
		"age": 7
	},
	"S000003": {
		"name": "王五",
		"student_id": "S000003",
		"age": 8
	},
	"S000004": {
		"name": "赵六",
		"student_id": "S000004",
		"age": 8
	}
}

代码实现

Dao

@MapKey("student_id")
HashMap<String, Object> getStudentId();

xml

<select id="getStudentMap" resultType="java.util.HashMap">
    select student_id , `name` , age
    from student_info
    order by id
</select>

测试用例

@Autowired
StudentInfoMapper studentInfoMapper;

@Test
void map() {
    HashMap<String, Object> studentId = studentInfoMapper.getStudentMap();
    studentId.forEach((id, studentInfo) -> log.info("学号：{} 信息：{}", id, JSON.toJSONString(studentInfo)));
}

问题点

以上代码的执行日志；

当学号是如下数据再查询的时候，整个数据查询和使用都是没有任何问题的

==>  Preparing: select student_id , `name` , age from student_info order by id
==> Parameters: 
<==    Columns: student_id, name, age
<==        Row: S000001, 张三, 7
<==        Row: S000002, 李四, 7
<==        Row: S000003, 王五, 8
<==        Row: S000004, 赵六, 8
<==      Total: 4
Closing non transactional SqlSession 
StudentTest    : 学号：S000001 信息：{"name":"张三","student_id":"S000001","age":7}
StudentTest    : 学号：S000002 信息：{"name":"李四","student_id":"S000002","age":7}
StudentTest    : 学号：S000003 信息：{"name":"王五","student_id":"S000003","age":8}
StudentTest    : 学号：S000004 信息：{"name":"赵六","student_id":"S000004","age":8}

但是当把学号换成以下数据之后：

根据查询结果和输出日志可以看到，数据库查询出来的数据是顺序的；但是返回到业务层的HashMap中的数据就变成无序的了；

==>  Preparing: select student_id , `name` , age from student_info order by id
==> Parameters: 
<==    Columns: student_id, name, age
<==        Row: S000001, 张三, 7
<==        Row: K000002, 李四, 7
<==        Row: M000003, 王五, 8
<==        Row: N000004, 赵六, 8
<==      Total: 4
Closing non transactional SqlSession 
StudentTest    : 学号：M000003 信息：{"name":"王五","student_id":"M000003","age":8}
StudentTest    : 学号：K000002 信息：{"name":"李四","student_id":"K000002","age":7}
StudentTest    : 学号：N000004 信息：{"name":"赵六","student_id":"N000004","age":8}
StudentTest    : 学号：S000001 信息：{"name":"张三","student_id":"S000001","age":7}

明明前面查询出来是正常的，咋换了个数据就不正常呢？原因只是前面的那批数据碰巧是对的而已，不要被表象给迷惑了，实际上两组数据这样返回都是不对的。

而实际的业务Bug中，往往也会因为这些迷惑数据（A用户访问正常，B用户访问就不正常了），导致一度怀疑人生…

问题分析

既然数据库的日志是顺序的获取出了数据，说明SQL层面是没有问题的，那问题点肯定是出在了HashMap；了解HashMap都知道，HashMap本身是无序的，但最让很多新手朋友疑惑的是，你无序没关系，但我是插入的时候是按我需要的顺序插入，这难道不行？如果你疑惑的是这个点，那说明你还没有理解这个无序的意思；HashMap的插入顺序和迭代取出顺序是没有任何关系的；

除非你在获取的时候，已知了插入时的所有key且都保存了下来；就可以按这个顺序key去获取；但实际的使用过程，很少会出现这么使用的情况；

简单的插入、获取示例：

public static void t1() {
    HashMap<String, Object> map = new HashMap<>();
    for (int i = 0; i < 5; i++) {
        String k = "key:" + i;
        String v = "va" + i;
        map.put(k, v);
        log.info("顺序插入 key:{} <-- va:{}", k, v);
    }
    log.info("-----------------------------");
    map.forEach((k, v) -> log.info("迭代获取 key:{} --> va:{}", k, v));
}

执行日志：

Main - 顺序插入 key:key:0 <-- va:va0
Main - 顺序插入 key:key:1 <-- va:va1
Main - 顺序插入 key:key:2 <-- va:va2
Main - 顺序插入 key:key:3 <-- va:va3
Main - 顺序插入 key:key:4 <-- va:va4
Main - -----------------------------
Main - 迭代获取 key:key:2 --> va:va2
Main - 迭代获取 key:key:1 --> va:va1
Main - 迭代获取 key:key:0 --> va:va0
Main - 迭代获取 key:key:4 --> va:va4
Main - 迭代获取 key:key:3 --> va:va3

源码原因分析

接下来就从源码的角度来详细的说一说HashMap的无序到底是怎么回事！

HashMap的数据结构

Java8 HashMap的数据结构如下图；采用的是数组+联表+红黑树的方式；因此元素所处的数组（黄色区域）下标位置是通过(n - 1) & hash])来定位的，当如果出现不同key的hash值相同时，就会将同下标的值以联表或者红黑树的方式存起来；

HashMap的插入过程

根据key的hash值和数组长度的与运算定位数组下标
```
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
	//...
}
```
关键代码(n - 1) & hash])，其中n为数组的长度，hash值是通过hash(key)运算得来

tab[i]下标i的值为null时，就直接实例化放在下标位置

也就是上面的

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

如果出现hash冲突，tab[i]已经有值了，就会以链表方式跟在Node后面

联表中key存在了

修改值

当if ((e = p.next) == null)下一个节点为空的时候

就实例化一个新的Node，跟在后面

// ....
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;
    }
}

如果联表的长度大于8个的时候，就会转换为红黑树的结构存储

经过上面4个步骤，元素并没有按顺序存储，而是被打散在数组的各个下标下面；链表或红黑树的元素位置也没有固定顺序；同一hash的key，插入的时机不同，所处的位置也就不同；

示例数据保存分析

有了源码分析的支持，下面就来详细的看一下保存在hashMap中的key、value在使用(n - 1) & hash])计算之后的下标位置：

key	value	数组下标i = (n - 1) & hash])
key:0	va0	6
key:1	va1	5
key:2	va2	4
key:3	va3	11
key:4	va4	10

最终key、value分布情况：

下标	4	5	6	10	11
key	key:2	key:1	key:0	key:4	key:3
值1	va2	va1	va0	va4	va3
值2

迭代获取

HashMap元素的迭代获取，就是先从左到右遍历数组，当数组索引位置有值时，再从上往下遍历联表或者红黑树；

源码如下：

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

核心代码

第一个循环for (int i = 0; i < tab.length; ++i)：左到右遍历数组

第二个循环for (Node<K,V> e = tab[i]; e != null; e = e.next)：从上往下遍历联表或者红黑树

for (int i = 0; i < tab.length; ++i) {
    for (Node<K,V> e = tab[i]; e != null; e = e.next)
        action.accept(e.key, e.value);
}

对着前面key、value分布情况表格，再来回看输出日志，就能明白，为啥迭代出来是下面这样的输出结果了

Main - 获取 key:key:2 --> va:va2
Main - 获取 key:key:1 --> va:va1
Main - 获取 key:key:0 --> va:va0
Main - 获取 key:key:4 --> va:va4
Main - 获取 key:key:3 --> va:va3

有序问题如何解决

当需要保证插入顺序和获取顺序一致时，可以采取有序的数据结构来保存数据，如List，LinkedHashMap等…

MyBatis数据查询

例如一开始列举的示例；当数据查询需要按顺序返回时，可以变换一下方式，采用List接收数据；如果业务真的需要通过Map参与，可以通过转换，来重新构造一个LinkedHashMap的有序数据结构用于业务逻辑的需要；

示例如下：

dao
```
List<StudentInfo> getStudentList();
```

xml

<select id="getStudentList" resultType="com.ehang.springboot.mybatisplus.generator.student.demain.StudentInfo">
    select student_id , `name` , age
    from student_info
    order by id
</select>

test

@Autowired
StudentInfoMapper studentInfoMapper;

@Test
void list() {
    List<StudentInfo> studentList = studentInfoMapper.getStudentList();
    studentList.forEach(studentInfo -> log.info("{}", JSON.toJSONString(studentInfo)));
}

测试输出

==>  Preparing: select student_id , `name` , age from student_info order by id
==> Parameters: 
<==    Columns: student_id, name, age
<==        Row: S000001, 张三, 7
<==        Row: S000002, 李四, 7
<==        Row: S000003, 王五, 8
<==        Row: S000004, 赵六, 8
<==      Total: 4
Closing non transactional SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession@ae5fa7]
StudentTest    : {"age":7,"name":"张三","studentId":"S000001"}
StudentTest    : {"age":7,"name":"李四","studentId":"S000002"}
StudentTest    : {"age":8,"name":"王五","studentId":"S000003"}
StudentTest    : {"age":8,"name":"赵六","studentId":"S000004"}

LinkedHashMap

简介

当Map需要有序时，也只需将HashMap换成LinkedHashMap即可保证插入和取出的顺序一致；

LinkedHashMap是HashMap的子类

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	//....
}

因此LinkedHashMap拥有了HashMap的所有功能；但是LinkedHashMap采用的是双向联表的方式保存数据；因此就能保证数据保存顺序和读取顺序的一致性

以下是读取数据的源码；可以看出是有序的遍历了整个联表；

public void forEach(BiConsumer<? super K, ? super V> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

测试示例改造：

public static void t1() {
    HashMap<String, Object> map = new LinkedHashMap<>();
    for (int i = 0; i < 5; i++) {
        String k = "key:" + i;
        String v = "va" + i;
        map.put(k, v);
        log.info("插入 key:{} <-- va:{}", k, v);
    }
    log.info("-----------------------------");
    map.forEach((k, v) -> log.info("获取 key:{} --> va:{}", k, v));
}

输出：

Main - 插入 key:key:0 <-- va:va0
Main - 插入 key:key:1 <-- va:va1
Main - 插入 key:key:2 <-- va:va2
Main - 插入 key:key:3 <-- va:va3
Main - 插入 key:key:4 <-- va:va4
Main - -----------------------------
Main - 获取 key:key:0 --> va:va0
Main - 获取 key:key:1 --> va:va1
Main - 获取 key:key:2 --> va:va2
Main - 获取 key:key:3 --> va:va3
Main - 获取 key:key:4 --> va:va4