一行代码 一世浮生

详解 HashMap 数据结构

HashMap 这个数据结构,不管是日常开发,还是求职面试,它始终都是所有 Java 程序员绕不开的宿命,所以还是决定写篇文章来详细剖析下 HashMap 这个数据结构,探探期间到底有多少奥秘。


一、背景

很早的时候就想写点关于数据结构方面的文章,时隔多年,终于决定正式开始提笔了,那就先从最热门的 HashMap 开始吧。

HashMap 是 Java 程序中使用率最高的数据结构之一,其主要用于处理键值对这种数据结构。而且在 JDK 1.8 中对底层的实现进行了优化,比如引入了红黑树、优化了扩容机制等。

本文主要是基于 JDK 最常用的 1.8 版本来介绍,详细分析了几个最重要的参数和方法,比如索引的计算、数组的扩容、put() 方法等,末尾也会稍微对比下 1.8 和 1.7 版本之间的差异。

二、简介

2.1 特点

HashMap 继承自 Map,有如下特点:

  1. 存储 key – value 类型结构,数据类型不限制
  2. 根据 key 的 hashcode 值进行存储数据
  3. 最多只允许一条记录的键(key)为 null(对 value 值不约束)
  4. 它是无序的(其实一见 hash 我们便知道了)
  5. 查询效率很高
  6. 它是线程不安全的(要线程安全,可以使用 Collections 的 synchronizedMap,或者使用更加推荐的 ConcurrentHashMap)

它还有一些常见的兄弟姐妹,比如 LinkedHashMap、TreeMap、Hashtable,本文就不进行对比介绍了。

2.2 基本结构

HashMap 的结构,是数组+链表+红黑树的结构,草图可以见下图。

红黑树是在 JDK1.8 版本才引入的,目的是加快链表的查询效率

HashMap 数据结构草图
HashMap 数据结构草图

从上图可看出,HashMap 底层是一个哈希桶数组,名为 table,数组内存储的是基于 Node 类型的数据,所以,这个 Node 甚为关键,下文会详解。

然后同一个数组所以的位置可以存储多个 Node,并以链表或红黑树的形式来实现,所以很容易猜到,既然是链表,那么每个 Node 必然会记录下一个 Node。但是如果链表很长,那查询效率便会降低,所以自 JDK1.8 开始便引入了红黑树,即当链表长度超过 8 的时候,链表便会转为红黑树,另外,当链表长度小于 6 的时候,会从红黑树转为链表。

2.3 链地址法

HashMap 是使用哈希表来存储数据的。哈希表为了解决冲突,一般有两种方案:开放地址法 和 链地址法

开放地址法:哈希完后如果有冲突,则按照某种规则找到空位插入

HashMap 采用的便是 链地址法,即在数组的每个索引处都是一个链表结构,这样就可以有效解决 hash 冲突。

当两个 key 的 hash 值相同时,则会将他们至于数组的同一个位置处,并以链表的形式呈现。

但是如果大部分的数据都集中在了数组中的同一索引处,而其余索引处的数据比较少,即分配不均衡,则说明哈希碰撞较多。

所以为了提高 HashMap 的存取效率,我们需要将数据尽可能多地分散到数组中去,即减少哈希碰撞,为了达到这一目的,最直接的方案便是改善 hash 算法,其次是扩大哈希桶数组的大小(扩容),在下文会详细介绍。

三、字段和属性

3.1 一些默认参数

初始容量是 16,可以扩容,但是扩容之后的容量,也是 2 的幂次方,比如 32、64,why?这里面涉及到很多巧妙的设计,下文介绍 resize() 方法的时候会详细介绍。

另外,我们解释下 MIN_TREEIFY_CAPACITY,虽然说当链表长度大于 8 的时候,链表会转为红黑树,但是也是需要满足桶内存储的数据量大于上述这个参数的值,否则不仅不会转红黑树,反而会进行扩容操作。

比如下面这段代码是判断是否要将链表转为红黑树,乍看,只是将链表长度和 UNTREEIFY_THRESHOLD 进行对比,其实不然,点开 treeifyBin(tab, hash) 这个方法,我们便可以看到,如果此时桶数组内的数据量小于 MIN_TREEIFY_CAPACITY,则不会将链表转红黑树,而是进行扩容操作,见下图:

链表转红黑树
链表转红黑树

3.2 一些重要的字段

其中有两个参数需要注意一下,一个是 threshold,还有一个是 loadFactor

threshold 代表最多能容纳的 Node 数量,一般 threshold = length * loadFactor,也就是说要想 HashMap 能够存储更多的数据(即获得较大的 threshold),有两种方案,一种是扩容(即增大数组长度 length),另一种便是增大负载因子。

threshold 和数组长度不是一回事哦

0.75 这个默认的负载因子的值是基于时间和空间考虑而得的一个比较平衡的点,所以负载因子我们一般不去调整,除非有特殊的需求:

  1. 比如 以空间换时间,意思是如果内存比较大,并且需要有较高的存取效率,则可以适当降低负载因子,这样做的话,就会减小哈希碰撞的概率。
  2. 再比如 以时间换空间,意思是如果内存比较小,并且接受适当减小存取效率,则可以适当调大负载因子,哪怕大于 1,这样做的话,就会增大哈希碰撞的概率。

关于 0.75 这个负载因子的详细的解释,需要建立数学模型来分析,由于鄙人才疏学浅,暂不进行讨论。

3.3 Node<K,V>

HashMap 底层是一个 Node[] table,所以 Node 是一个很重要的数据结构。

Node 实现了 Entry 接口,所以,Node 本质上就是一个 Key-Value 数据结构。

四、构造函数

总共有四个构造函数,依次来讲解下。

构造函数列表
构造函数列表

4.1 HashMap()

构造一个空的 HashMap,初始容量为 16,负载因子为 0.75

4.2 HashMap(int initialCapacity)

构造一个空的 HashMap,并指定初始化容量,负载因子为默认的 0.75。

构造函数内部会调用下文紧接着讲到的第三种构造函数。

4.3 HashMap(int initialCapacity, float loadFactor)

构造一个空的 HashMap,并指定初始化容量,指定负载因子。

构造函数中会进行一系列的参数判断,并且会进行初始化操作。

  1. 如果初始容量小于 0,或者负载因子小于 0 或不为数字时,会抛出 IllegalArgumentException 异常。
  2. 如果初始容量大于最大值(2^30),则会使用最大容量。
  3. 设置 threshold,直接调用 tableSizeFor() 方法,该方法会返回一个大于等于指定容量的 2 的幂次方的整数,例如传入 6,则会返回 8。

tableSizeFor() 方法的详细解释会放到下文来讲解。

另外,直接将得到的值赋给 threshold,难道不是应该是这样的操作吗?this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;, 其实不然,我们再看一眼源码,会发现初始化的动作放在了 put 操作中。

4.4 HashMap(Map<? extends K, ? extends V> m)

构造一个非空的 HashMap,保证初始化容量能够完全容下传进来的 Map,另外,负载因子使用的是默认值 0.75。

putMapEntries() 方法是将传递进来的 Map 中的数据全都存入到当前的 HashMap 中去,方法的详解见下文。

五、关键方法

5.1 tableSizeFor(int cap)

顾名思义,初始化桶数组的大小。

该方法的作用是返回一个大于等于传入的参数的数值,并且返回值会满足以下两点:

  1. 返回值是 2 的幂次方
  2. 返回值是最接近传入的参数的值

比如:传入 5,则返回 8;传入 8,则返回 8;

这个方法的设计是很令人惊叹的,十分巧妙,除了敬仰还是敬仰。

2 的幂次方有个特点,就是它的字节码除了最高位是 1,其余全是 0。

比如 2,字节码为:10,最高位为 1,其余为 0

再比如16,字节码为:10000,最高位为 1,其余为 0

所以方法内使用了大量的 “或运算”和 “右移”操作,目的是保证从最高位起的每个 bit 都是 1。

  1. 首行 int n = cap - 1; 的作用,是为了防止传入的参数本身就是一个 2 的幂次方,否则会返回两倍于参数的值;
  2. n |= n >>> 1; 的作用,是保证倒数第二个高位也是 1,下面的代码类似。
  3. 最后一行之前,得到的数类似 0000 1111 这种从第一个高位起全是 1,这样只要加了 1,则返回的数值必然是 2 的幂次方。

详细的计算过程详解见下图:

tableSizeFor 过程
tableSizeFor 过程

5.2 putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

该方法是将参数 m 中的所有数据存入到当前的 HashMap 中去,比如在上文提到的第四种构造函数便调用了此方法。

此方法还是比较简单的,下文代码中都注释,其中涉及到的两个关键方法 resize() 和 putVal() 方法,作用分别为扩容和赋值,下文再详细介绍这两个方法。

5.3 hash(Object key)

HashMap 中的 hash 算法,是将 key 进行 hashCode 计算得到 h,然后将 h 的高16位与低16位进行异或运算。

这样做是从速度、质量等多方面综合考虑的,而且将高位和低位进行混合运算,这样是可以有效降低冲突概率的。

另外,高位是可以保证不变的,变的是低位,并且低位中掺杂了高位的信息,最后生成的 hash 值的随机性会增大。

下图举例介绍异或计算(例如 h 为 467,926,597):

异或运算
异或运算

从上图中也看出,高位的数字是不变的。

另外,hash() 的作用是根据 key 计算一个 hash 数值,然后根据这个 hash 数值计算得到数组的索引 i,基于这个索引我们才能进行相关的增删改查操作,所以这个索引甚是关键。

计算公式为:i = hash(key) & (n-1),即下面这个方法,但是这个下面这个方法仅限 1.8 以前的版本:

这里又是一个很精妙的设计,一般情况下,我们要获取索引 i,最常用的计算方式是取模运算:hash % length,但是此处却使用的是:hash & (length-1),妙哉妙哉。

为什么要这么做呢?因为 ‘%’ 操作相对于位运算是比较消耗性能的,所以采用了奇淫技巧 ‘&’ 运算。但是为什么结果是和取模运算是一致的呢?其实还是因为table的 length 的问题。

我们上文提到过,HashMap 的长度 length 始终是 2 的幂次方,这个是关键,所以才会有这种结果,简单分析见下图:

使用 & 位运算替代常规的 % 取模运算,性能上提高了很多,这个是 table 如此设计数组长度的优势之一,另一个很大的优势是在扩容的时候,下文会分析。

取模运算
取模运算

5.4 resize()

resize() 是一个很重要的方法,作用是扩容,从而使得 HashMap 可以存储更多的数据。

因为当我们不断向 HashMap 中添加数据时,它总会超过允许存储的数据量上限,所以必然会经历 扩容 这一步操作,但是 HashMap 底层是一个数组,我们都知道数组是无法增大容量的,所以 resize 的过程其实就是新建一个更大容量的数组来存储当前 HashMap 中的数据。

resize() 方法是很精妙的,我们就一起来看下 JDK1.8 的源码吧。

好了,下面我们就介绍下上面的源码中提到的计算索引的操作,即判断 if ((e.hash & oldCap) == 0)

下图展示的是扩容前和扩容后的计算索引的方法,主要关注红色框中的内容。这种方案是没问题的,但是之前我们提到,table 的大小为 2 的幂次方,这什么要这么设计呢,期间的又一个奥秘便体现在此,请看图中的备注。

扩容索引计算1
扩容索引计算1

既然扩容后每个 key 的新索引的生成规则是固定有规律的,即只有两种形式,要么不变 i,要么增加原先的数组大小的量(i+n),所以我们其实并不需要真的去计算每个 key 的索引,而只需要判断索引是否不变即可。所以此处巧妙地使用了 (e.hash & oldCap) == 0 这个判断,着实精妙,计算的细节过程看下面的图即可。

扩容索引计算2
扩容索引计算2

5.5 put(K key, V value)

此处介绍的是 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict),因为 put() 其实就是直接调用的 putVal();

put() 方法是 HashMap 中最常用的方法之一,我们先大体关注下 put() 方法的流程,文字就暂不赘述了,看下图便很清晰了:

put 流程
put 流程

下面简单分析下源码:

5.6 get(Object key)

此处介绍的是 getNode(int hash, Object key,因为 get() 其实就是直接调用的 getNode();

get() 方法也是比较简单的,就是根据 key 获取 table 的索引,然后再分情况查找拥有相同 key 的 Node;

源码大致如下:

六、JDK1.8 VS JDK1.7

1.7 和 1.8 之间的区别,最最主要的是如下三方面,当然,鄙人觉得这三点的变化可以算是比较成功的优化。

  1. 扩容后 Node 索引的计算方式不同。上文提到,由于 table 大小的这种神奇的设计,所以扩容时计算索引的时候,1.8 中只需要简单使用 & 运算来判断是否为 0 即可,并不需要像 1.7 一样每次都是用 & 运算来计算出索引值。
  2. 1.8 中引入了红黑树结构。上文也提到了,当链表长度大于 8 的时候会转换为红黑树,但是 1.7 中是数组+链表的组合。
  3. 1.8 中采用的是尾插法,而 1.7 中采用的是头插法。比如扩容的时候,头插法会使链表上 Node 的顺序调转,而尾插法则不会,另外,头插法也会造成环形链死循环等问题,本文就不深讨了。

七、其它

HashMap 是线程不安全的,因为它是允许多线程同时操作同一个数组的,比如 put(),比如 resize(),这些都会造成数据异常甚至死循环。

所以要使用线程安全的 Map 的时候,可以使用 HashTable,但是这个不推荐,或者使用自 JDK1.8 开始引入的 Concurrent 包中的 ConcurrentHashMap,这个是比较推荐的,具体的介绍就放到下文再说吧。

参考了美团的技术博客:传送门

image
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注