HashMap的这个小'坑',老司机也可能翻车

  |   0 评论   |   0 浏览

 如遇图片加载失败,可尝试使用手机流量访问

大家好,我是一航;

昨天一位粉丝朋友和我聊天,说遇到了一个莫名奇妙的问题,让我帮着分析一下;经过他的一轮描述,发现是一个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的插入过程

  1. 根据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)运算得来

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

    也就是上面的

    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
  3. 如果出现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;
          }
      }
      
  4. 如果联表的长度大于8个的时候,就会转换为红黑树的结构存储

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

示例数据保存分析

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

keyvalue数组下标i = (n - 1) & hash])
key:0va06
key:1va15
key:2va24
key:3va311
key:4va410

最终key、value分布情况:

下标01234567891011...
key key:2key:1key:0 key:4key:3
值1 va2va1va0 va4va3
值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
    

总结

每一种数据结构,都有他其独有的特性;因此,基础知识的部分,一定要将差异部分的原理了解清楚,只要这样,在遇到问题的时候,才能准确分析出问题的本质,否则很容易被表象,被日志给迷惑而陷入迷茫;

好了,今天的分享就到这里,不介意的话,三连给安排一下!感激不尽!



标题:HashMap的这个小'坑',老司机也可能翻车
作者:码霸霸
地址:https://lupf.cn/articles/2021/12/14/1639495841348.html