3分钟轻松理解单线程下的HashMap工作原理

语言: CN / TW / HK

HashMap主要是用来处理键值对数据。随着JDK版本的更新,JDK1.8对HashMap对底层也做了一些优化。今天我带大家一起来结合源码,深入浅出HashMap工作原理。   l

HashMap是基于哈希表对Map接口的实现类,它的特点是访问数据的速度快,并不是按顺序来遍历。 HashMap提供所有可选的映射操作,但不能保证映射顺序不变,并且允许使用空值和空键。HashMap也并不是线程安全的,当存在多个线程同时写入时,可能会导致数据不一致的情况。

1、HashMap中的关键属性

要透彻理解HashMap原理,首先需要对以下几个关键属性有一个基本的认识。

我们看到,HashMap的源码片段:

第一个属性  loadFactor,它是负载因子,默认值是0.75,表示扩容前 。

第二个属性  threshold 它是记录HashMap所能容纳的键值对的临界值,它的计算规则是负载因子  乘以 数组长度。

第三个属性 size,它用来记录HashMap实际存在的键值对的数量。

第四个属性 modCount,它用来记录HashMap内部结构发生变化的次数。

第五个是常量属性DEFAULT_INITIAL_CAPACITY ,它规定 的默认容量是16。

2、HashMap的存储结构

HashMap采用的是 的存储结构。HashMap的数组部分称为Hash桶,数组元素保存在一个叫做table的属性中。当链表长度大于等于8时,链表数据将会以红黑树的形式进行存储,当长度降到6时,又会转成链表形式存储。

每个Node节点,保存了用来定位数组索引位置的hash值、Key、Value和链表指向的下一个Node节点。而Node类是HashMap的内部类,它实现了Map.Entry接口,它的本质其实可以简单的理解成就是一个键值对。来看一下源码。

3、HashMap的工作原理

当我们向HashMap中插入数据时,首先要确定Node在数组中的位置。那如何确定Node的存储位置呢?以添加Key为字符串“e”的对象为例:

HashMap首先调用hashCode()方法,获取Key的hashCode值为h。然后对h值进行高位运算;将h右移16位取得h的高16位,与 进行异或运算,最后得到h的值与 ( table.length - 1 )进行与运算获得该对象的保留位,最后计算出下标。当然,这是最官方的描述。有的小伙伴可能已经迷糊了。其实,这段运算过程,简单地理解成求模取余法。

就是用hash值和数组的长度减1,取模,最后得到数组的下标,这样可以保证数组下标不越界。只不过,位运算是二进制运算,效率更高。

最后,来看一段动画演示,假设有“a”、“b”、“d”、“r”,“t”,“e”的Key。通过计算得到的下标分别为  1  、2  、 4 、2  、4  、5\

它们的插入顺序如动画所示。

如果我们再次插入 "a",“g”,“i”,null 四个Key,来看HashMap的内部变化。

当插入第二个以a为Key的对象时,会将新值赋值给a的值。当插入的对象大小超过临界值时,HashMap将新建一个桶数组并重新赋值(当然,JDK1.7和1.8重新赋值的方式略有不同)

这个时候,HashMap键的输出顺序为 null、a、b、r、d、t、e、g、i

HashMap的工作原理,你搞懂了吗?

需要1v1单独模拟面试,以及需要做职业规划的同学可S我【666】或【Tom】还有10万+字面试文档已经整理成PDF可免费领取! 我是被编程耽误的文艺Tom,