HashMap的工作原理

  • HashMap存储结构
    简单来说,HashMap的存储结构是由数组和链表组成的。

    HashMap-1

从上图可以看出HashMap是Y轴方向是数组,X轴方向就是链表的存储方式。
大家都知道数组的存储方式在内存的地址是连续的,大小固定,一旦分配不能被其他引用占用。
它的特点是查询快,时间复杂度是O(1),插入和删除的操作比较慢,时间复杂度是O(n),
链表的存储方式是非连续的,大小不固定,特点与数组相反,
插入和删除快,查询速度慢。HashMap可以说是一种折中的方案吧。

  • HashMap基本原理

1、首先判断Key是否为Null,如果为null,直接查找Enrty[0],如果不是Null,先计算Key的HashCode,然后经过二次Hash。得到Hash值,这里的Hash特征值是一个int值。

2、根据Hash值,要找到对应的数组,所以对Entry[]的长度length求余,得到的就是Entry数组的index。

3、找到对应的数组,就是找到了所在的链表,然后按照链表的操作对Value进行插入、删除和查询操作。

  • HashMap为什么是线程不安全的?

当hashMap扩容的时候会调用transfer方法,它是采用头插法来转移旧值到新的hashMap中去,
假如转移前链表顺序是1->2->3,那么转移后就会变成3->2->1,那么在多线程的情况下就可能造成1->2的同时2->1的环形链表,进而形成死循环。

-------------本文结束感谢您的阅读-------------
0%