JDK集合源码之HashMap解析(上)

声明:转载请附带原文链接!

超长文章警告:耐心看下去肯定有收获!

0.前言

提示:对于初识HashMap的小伙伴来说,不推荐直接硬啃,建议先看一下如下几个视频教程之后在回头自己反复琢磨。(一遍不懂反复看,一小块儿一小块的找博客阅读)

HashMap简述:

  • HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,即主要用来存放键值对。HashMap 的实现不是同步的,这意味着它不是线程安全的。它的 key、value 都可以为 null,此外,HashMap 中的映射不是有序的。
  • jdk1.8 之前 HashMap 由 数组 + 链表 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64 时,此时此索引位置上的所有数据改为使用红黑树存储

HashMap扩容机制简述:

HashMap == 数组+散链表+红黑树

  • HashMap 默认初始桶位数16,如果某个桶中的链表长度大于8,则先进行判断:

  • 如果桶位数小于64,则先进行扩容(2倍),扩容之后重新计算哈希值,这样桶中的链表长度就变短了(之所以链表长度变短与桶的定位方式有关,请接着往下看)。

  • 如果桶位数大于64,且某个桶中的链表长度大于8,则对链表进行树化(红黑树,即自平衡的二叉树)

  • 如果红黑树的节点数小于6,树也会重新变会链表。

所以得出树化条件链表阈值大于8,且桶位数大于64(数组长度),才进行树化

元素放入桶(数组)中,定位桶的方式:通过数组下标 i 定位,添加元素时,目标桶位置 i 的计算公式,i = hash & (cap - 1),cap为容量。

为什么优先扩容桶位数(数组长度),而不是直接树化?

  • 这样做的目的是因为,当桶位数(数组长度)比较小时,应尽量避开红黑树结构,这种情况下变为红黑树结构,反而会降低效率。因为红黑树需要逬行左旋,右旋,变色这些操作来保持平衡。同时数组长度小于64时,搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间,底层阈值大于8并且数组长度大于64时,链表才转换为红黑树,具体可以参考下文要讲述的 treeifyBin() 方法。
  • 而当阈值大于 8 并且数组长度大于 64 时,虽然增了红黑树作为底层数据结构,结构变得复杂了,但是,长度较长的链表转换为红黑树时,效率也变高了。

HashMap 特点:

  1. 存储无序;
  2. 键和值位置都可以是 null,但是键位置只能存在一个 null;
  3. 键位置是唯一的,是由底层的数据结构控制的;
  4. jdk1.8 前数据结构是链表+数组,jdk1.8 之后是链表+数组+红黑树;
  5. 阈值(边界值)> 8 并且桶位数(数组长度)大于 64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询;

1.HashMap存储数据的过程

注意:相对于直接去读HashMap源码来说,先debug一下其执行数据存储的流程,更方便大家理解

测试代码:

@Test
public void test01() {
    HashMap<String, Integer> hashMap = new HashMap();
    hashMap.put("a", 3);
    hashMap.put("b", 4);
    hashMap.put("c", 5);
    hashMap.put("a", 88888);// 修改
    System.out.println(hashMap);
}

输出结果:

{a=88888, b=456, c=789}

执行流程分析:

  1. 首先,HashMap<String, Integer> hashMap = new HashMap();当创建 HashMap 集合对象的时候,HashMap 的构造方法并没有创建数组,而是在第一次调用 put 方法时创建一个长度是16 的数组(即,16个桶) ,Node[] table (jdk1.8 之前是 Entry[] table)用来存储键值对数据。

  2. 当向哈希表中存储put("a", 3)的数据时,根据"a"字符串调用 String 类中重写之后的 hashCode() 方法计算出哈希值,然后结合数组长度(桶数量)采用某种算法计算出向 Node 数组中存储数据的空间索引值(比如table[i],这里的i就是该Node数组的空间索引)。如果计算出的索引空间没有数据(即,这个桶是空的),则直接将<"a", 3>存储到数组中。

    举例:如果计算出的索引是 3,则存储到如下桶位:

    coding-JDK集合源码之HashMap解析(上)-

  3. 当向哈希表中存储数据<"b", 4>时,假设算出的 hashCode() 方法结合数祖长度计算出的索引值也是3,那么此时数组空间不是 null(即,这个桶目前不为空),此时底层会比较 "a""b" 的 hash 值是否一致,如果不一致,则在空间上划出一个结点来存储键值对数据对 <"b", 4>,这种方式称为拉链法

  4. 当向哈希表中存储数据<"a", 88888>时,那么首先根据 "a"调用 hashCode() 方法结合数组长度计算出索引肯定是 3,此时比较后存储的数据"a"和已经存在的数据的 hash 值是否相等,如果 hash 值相等,此时发生哈希碰撞。那么底层会调用 "a"所属类 String 中的 equals() 方法比较两个内容是否相等:

    • 相等:将后添加的数据的 value 覆盖之前的 value。

    • 不相等:继续向下和其他的数据的 key 进行比较,如果都不相等,则划出一个结点存储数据,如果结点长度即链表长度大于阈值 8 并且数组长度大于 64 则将链表变为红黑树
      coding-JDK集合源码之HashMap解析(上)-

  5. 在不断的添加数据的过程中,会涉及到扩容问题,当超出阈值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的 2 倍,并将原有的数据复制过来。

  6. 综上描述,当位于一个表中的元素较多,即 hash 值相等但是内容不相等的元素较多时,通过 key 值依次查找的效率较低。而 jdk1.8 中,哈希表存储采用数组+链表+红黑树实现,当链表长度(阈值)超过8且当前数组的长度大于64时,将链表转换为红黑树,这样大大减少了查找时间。

    简单的来说,哈希表是由数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的。如下图所示:
    coding-JDK集合源码之HashMap解析(上)-

  7. jdk1.8 中引入红黑树的进一步原因:

    • jdk1.8 以前 HashMap 的实现是数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有n个元素,遍历的时间复杂度就是O(n),完全失去了它的优势

    • 针对这种情况,jdk1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。

  8. 总结

coding-JDK集合源码之HashMap解析(上)-

说明:

  • size 表示 HashMap 中键值对的实时数量(即,所存储元素的数量),注意这个不等于数组的长度
  • threshold(临界值)= capacity(容量)* loadFactor(负载因子)。这个值是当前已占用数组长度的最大值。size 超过这个值就重新 resize(扩容),扩容后的 HashMap 容量是之前容量的2倍

2.HashMap相关面试题

具体原理我们下文会具体分析,这里先大概了解下面试的时候会问什么,带着问题去读源码,便于理解!

  1. HashMap 中 hash 函数是怎么实现的?还有哪些hash函数的实现方式?

    • 对 key 的 hashCode 做 hash 操作,如果key为null则直接赋哈希值为0,否则,无符号右移 16 位然后做异或位运算,如,代码所示:(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    • 除上面的方法外,还有平方取中法伪随机数法取余数法。这三种效率都比较低,而无符号右移 16 位异或运算效率是最高的。
  2. 当两个对象的 hashCode 相等时会怎么样?
    :会产生哈希碰撞。若 key 值内容相同则替换旧的 value,不然连接到链表后面,链表长度超过阈值 8 就转换为红黑树存储。

  3. 什么是哈希碰撞,如何解决哈希碰撞?
    :只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8之后使用链表 + 红黑树解决哈希碰撞。

  4. 如果两个键的 hashCode 相同,如何存储键值对?
    :通过 equals 比较内容是否相同。

    • 相同:则新的 value 覆盖之前的 value。

    • 不相同:遍历该桶位的链表(或者树):

      • 如果找到相同key,则覆盖该key对应的value;
      • 如果找不到,则将新的键值对添加到链表(或者树)中;

3.HashMap继承体系

coding-JDK集合源码之HashMap解析(上)-
从继承体系可以看出:

  • HashMap 实现了Cloneable接口,可以被克隆。
  • HashMap 实现了Serializable接口,属于标记性接口,HashMap 对象可以被序列化和反序列化。
  • HashMap 继承了AbstractMap,父类提供了 Map 实现接口,具有Map的所有功能,以最大限度地减少实现此接口所需的工作。

知识扩展:

通过上述继承关系我们发现一个很奇怪的现象,就是 HashMap 已经继承了AbstractMap 而 AbstractMap 类实现了Map 接口,那为什么 HashMap 还要在实现 Map 接口呢?同样在 ArrayList 中 LinkedLis 中都是这种结构。
    
据 Java 集合框架的创始人 Josh Bloch 描述,这样的写法是一个失误。在 Java 集合框架中,类似这样的写法很多,最幵始写 Java 集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,jdk 的维护者,后来不认为这个小小的失误值得去修改,所以就这样保留下来了。

存储结构(再过一遍)
coding-JDK集合源码之HashMap解析(上)-
在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作

在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部

当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率

数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

2.HashMap基本属性与常量

/*
 * 序列化版本号
 */
private static final long serialVersionUID = 362498820763181265L;

/**
 * HashMap的初始化容量(必须是 2 的 n 次幂)默认的初始容量为16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * 最大的容量为2的30次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认的装载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 树化阈值,当一个桶中的元素个数大于等于8时进行树化
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 树降级为链表的阈值,当一个桶中的元素个数小于等于6时把树转化为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 当桶的个数达到64的时候才进行树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * Node数组,又叫作桶(bucket)
 */
transient Node<K,V>[] table;

/**
 * 作为entrySet()的缓存
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 元素的数量
 */
transient int size;

/**
 * 修改次数,用于在迭代的时候执行快速失败策略
 */
transient int modCount;

/**
 * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor
 */
int threshold;

/**
 * 装载因子
 */
final float loadFactor;

(1)容量:容量为数组的长度,亦即桶的个数,默认为16 ,最大为2的30次方,当容量达到64时才可以树化

(2)装载因子:装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。

(3)树化:树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化

2.1 DEFAULT_INITIAL_CAPACITY

集合的初始化容量(必须是 2 的 n 次幂):

// 默认的初始容量是16	1 << 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

面试问题:为什么必须是 2 的 n 次幂?如果输入值不是 2 的幂比如 10 会怎么样?

HashMap 构造方法可以指定集合的初始化容量大小,如:

// 构造一个带指定初始容量和默认负载因子(0.75)的空 HashMap。
HashMap(int initialCapacity)

根据上述讲解我们已经知道,当向 HashMap 中添加一个元素的时候,需要根据 key 的 hash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。

这个算法实际就是取模,hash % length,而计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1)而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。(这段话是摘抄传智播客锁哥的,这个解释确实很完美!)

例如,数组长度为 8 的时候,3 & (8 - 1) = 3,2 & (8 - 1) = 2,桶的位置是(数组索引)3和2,不同位置上,不碰撞。

再来看一个数组长度(桶位数)不是2的n次幂的情况:

coding-JDK集合源码之HashMap解析(上)-

从上图可以看出,当数组长度为9(非2 的n次幂)的时候,不同的哈希值hash, hash & (length - 1)所得到的数组下标相等(很容易出现哈希碰撞)。

小结一下HashMap数组容量使用2的n次幂的原因:(面试也会问)

coding-JDK集合源码之HashMap解析(上)-


问题:如果创建HashMap对象时,输入的数组长度length是10,而不是2的n次幂会怎么样呢

HashMap<String, Integer> hashMap = new HashMap(10);

HashMap双参构造函数会通过tableSizeFor(initialCapacity)方法,得到一个最接近length且大于length的2的n次幂数(比如最接近10且大于10的2的n次幂数是16)

这一块儿比较难理解,下文讲构造方法的时候还会再举例一个例子

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

说明

当在实例化 HashMap 实例时,如果给定了 initialCapacity,由于 HashMap 的 capacity 必须是 2 的幂,因此这个方法tableSizeFor(initialCapacity);用于找到大于等于 initialCapacity 的最小的 2 的幂。

分析

  1. int n = cap - 1;为什么要减去1呢
    防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂,又没有这个减 1 操作,则执行完后面的几条无符号操作之后,返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)

  2. 最后为什么有个 n + 1 的操作呢

    如果 n 这时为 0 了(经过了cap - 1后),则经过后面的几次无符号右移依然是 0,返回0是肯定不行的,所以最后返回n+1最终得到的 capacity 是1。

  3. 注意:容量最大也就是 32bit 的正数,因此最后 n |= n >>> 16;最多也就 32 个 1(但是这已经是负数了,在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY,会执行位移操作。所以这里面的位移操作之后,最大 30 个 1,不会大于等于 MAXIMUM_CAPACITY。30 个 1,加 1 后得 2 ^ 30)。

完整例子

coding-JDK集合源码之HashMap解析(上)-

所以由结果可得,当执行完tableSizeFor(initialCapacity);方法后,得到的新capacity是最接近initialCapacity且大于initialCapacity的2的n次幂的数。

2.2 DEFAULT_LOAD_FACTOR

默认的负载因子(默认值 0.75)

static final float DEFAULT_LOAD_FACTOR = 0.75f;

2.3 MAXIMUM_CAPACITY

集合最大容量

static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂

2.4 TREEIFY_THRESHOLD

当链表的值超过8则会转为红黑树(jdk1.8新增)

// 当桶(bucket)上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD = 8;

面试问题:为什么 Map 桶中结点个数超过 8 才转为红黑树?

8这个阈值定义在HashMap中,针对这个成员变量,在源码的注释中只说明了 8 是 bin( bucket 桶)从链表转成树的阈值,但是并没有说明为什么是 8。

在 HashMap 中有一段注释说明:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins
contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
small (due to removal or resizing) they are converted back to plain bins.  In usages with
well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, 
the frequency of nodes in bins follows a Poisson distribution 
(http://en.wikipedia.org/wiki/Poisson_distribution) 
with a parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, 
the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:

翻译:因为树结点的大小大约是普通结点的两倍,所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
当它们变得太小(由于删除或调整大小)时,就会被转换回普通的桶。在使用分布良好的用户 hashCode 时,很少使用树箱。
理想情况下,在随机哈希码下,箱子中结点的频率服从泊松分布。
默认调整阈值为0.75,平均参数约为0.5,尽管由于调整粒度的差异很大。忽略方差,列表大小k的预朗出现次数是(exp(-0.5)*pow(0.5, k) / factorial(k)
第一个值是:

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

TreeNodes(树) 占用空间是普通 Nodes(链表) 的两倍,所以只有当 bin(bucket 桶) 包含足够多的结点时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESH〇LD 的值决定的。当 bin(bucket 桶) 中结点数变少时,又会转成普通的 bin(bucket 桶)。并且我们查看源码的时候发现,链表长度达到 8 就转成红黑树,当长度降到 6 就转成普通 bin(bucket 桶)。

这样就解释了为什么不是一开始就将其转换为 TreeNodes,而是需要一定结点数之后才转为 TreeNodes,说白了就是权衡空间和时间

这段内容还说到:当 hashCode 离散性很好的时候,树型 bin 用到的概率非常小,因为数据均匀分布在每个 bin 中,几乎不会有 bin 中链表长度会达到阈值。但是在随机 hashCode 下,离散性可能会变差,然而 jdk 又不能阻止用户实现这种不好的 hash 算法,因此就可能导致不均匀的数据分布。不理想情况下随机 hashCode 算法下所有 bin 中结点的分布频率会遵循泊松分布,我们可以看到,一个 bin 中链表长度达到 8 个元素的槪率为 0.00000006,几乎是不可能事件。所以,之所以选择 8,不是随便決定的,而是裉据概率统计决定的。甶此可见,发展将近30年的 Java 每一项改动和优化都是非常严谨和科学的。

面试答案:hashCode 算法下所有 桶 中结点的分布频率会遵循泊松分布,这时一个桶中链表长度超过 8 个元素的槪率非常小,权衡空间和时间复杂度,所以选择 8 这个数宇。

扩展补充

  • Poisson 分布(泊松分布),是一种统计与概率学里常见到的离散[概率分布]。泊松分布的概率函数为:
    coding-JDK集合源码之HashMap解析(上)-
    泊松分布的参数 A 是单位时间(或单位面积)内随机事件的平均发生次数。泊松分布适合于描述单位时间内随机事件发生的次数。

  • 以下是我在研究这个问题时,在一些资料上面翻看的解释,供大家参考:

    红黑树的平均查找长度是 log(n),如果长度为 8,平均查找长度为 log(8) = 3,链表的平均查找长度为 n/2,当长度为 8 时,平均查找长虔为 8/2 = 4,这才有转换成树的必要;链表长度如果是小于等于 6, 6/2 = 3,而 log(6) = 2.6,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。

2.5 UNTREEIFY_THRESHOLD

当链表的值小于 6 则会从红黑树转回链表

// 当桶(bucket)上的结点数小于这个值,树转为链表 
static final int UNTREEIFY_THRESHOLD = 6;

2.6 MIN_TREEIFY_CAPACITY

当 Map 里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4*TREEIFY_THRESHOLD(8)

// 桶中结构转化为红黑树对应的数组长度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

2.7 table(重点)

table 用来初始化(必须是二的n次幂)

// 存储元素的数组 
transient Node<K,V>[] table;

在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry<K,V> 类型。从 jdk1.8 之后是 Node<K,V> 类型。只是换了个名字,都实现了一样的接口:Map.Entry<K,V>。负责存储键值对数据的。

2.8 entrySet

用来存放缓存

// 存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

2.9 size(重点)

HashMap 中存放元素的个数

// 存放元素的个数,注意这个不等于数组的长度
 transient int size;

size 为 HashMap 中 K-V 的实时数量,不是数组 table 的长度。

2.10 modCount

用来记录 HashMap 的修改次数

// 每次扩容和更改 map 结构的计数器
 transient int modCount;  

2.11 threshold(重点)

用来调整大小下一个容量的值计算方式为(容量*负载因子)

// 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
int threshold;

2.12 loadFactor(重点)

哈希表的负载因子

// 负载因子
final float loadFactor;// 0.75f

说明

  • loadFactor 是用来衡量 HashMap 满的程度,表示HashMap的疏密程度,影响 hash 操作到同一个数组位置的概率,计算 HashMap 的实时负载因子的方法为:size/capacity,而不是占用桶的数量去除以 capacity。capacity 是桶的数量,也就是 table 的长度 length
  • loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
  • 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap 太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。所以开发中尽量减少扩容的次数,可以通过创建 HashMap 集合对象时指定初始容量来尽量避免。
  • 在 HashMap 的构造器中可以定制 loadFactor。
// 构造方法,构造一个带指定初始容量和负载因子的空HashMap
HashMap(int initialCapacity, float loadFactor);
  • 为什么负载因子loadFactor 设置为0.75,初始化临界值threshold是12

    loadFactor 越趋近于1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于0,数组中存放的数据(entry)也就越少,也就越稀疏。

coding-JDK集合源码之HashMap解析(上)-
如果希望链表尽可能少些,要提前扩容。有的数组空间有可能一直没有存储数据,负载因子尽可能小一些。

举例:

例如:负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
	 负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了,导致查找元素效率低。

所以既兼顾数组利用率又考虑链表不要太多,经过大量测试 0.75 是最佳方案。

  • threshold 计算公式:capacity(数组长度默认16) * loadFactor(负载因子默认0.75)==12。

    这个值是当前已占用数组长度的最大值。当 Size >= threshold(12) 的时候,那么就要考虑对数组的 resize(扩容),也就是说,这个的意思就是 衡量数组是否需要扩增的一个标准扩容后的 HashMap 容量是之前容量的两倍

3.内部类

3.1Node内部类

Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;// hash用来存储key计算得来的hash值
    final K key;// 键
    V value;// 值
    Node<K,V> next;// 下一个node节点
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {// 调用底层c++ 返回Key/Value的哈希码值,如果此对象为null,则返回0
        return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

3.2TreeNode内部类

TreeNode内部类,它继承自LinkedHashMap中的Entry类,关于LInkedHashMap.Entry这个类之后会单独发文章论述,TreeNode是一个典型的树型节点,其中,prev是链表中的节点,用于在删除元素的时候可以快速找到它的前置节点。

// 位于HashMap中,文章接下来会逐步分析
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

// 位于LinkedHashMap中,典型的双向链表节点,这个类之后会单独发文章论述
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

4.HashMap构造方法

HashMap 中重要的构造方法,它们分别如下:

4.1 HashMap()

构造一个空的HashMap,默认初始容量(16)和默认负载因子(0.75)。

public HashMap() {
   // 将默认的负载因子0.75赋值给loadFactor,并没有创建数组
   this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

4.2 HashMap(int initialCapacity)

构造一个具有指定的初始容量和默认负载因子(0.75)HashMap 。

// 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

4.3 HashMap(int initialCapacity,float loadFactor)构造方法

构造一个具有指定的初始容量和负载因子的 HashMap。

/*
	 指定“容量大小”和“负载因子”的构造函数
	 initialCapacity:指定的容量
	 loadFactor:指定的负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    	// 判断初始化容量initialCapacity是否小于0
        if (initialCapacity < 0)
            // 如果小于0,则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            // 如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
            initialCapacity = MAXIMUM_CAPACITY;
    	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            // 如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
     	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
        this.loadFactor = loadFactor;// 一般不建议修改默认的负载因子
        this.threshold = tableSizeFor(initialCapacity);
    }
	// 最后调用了tableSizeFor,来看一下方法实现:
     /*
     	返回比指定cap容量大的最小2的n次幂数:
     	前面第一遍讲述的应该有些小伙伴难以理解,这里我在举例解析一下:
     	-------------------------------------------------------
     	首先假定传入的cap = 10
     	则,n = 10 -1 => 9
     	n |= n >>> 1 就等同于 n = (n | n >>> 1),所以:
     	(位运算不懂的可以去看我的《Java基础提高之位运算》这篇文章)
     	9 => 0b1001    9 >>> 1 => 0b0100 
     	n |= n >>> 1;  ===>  0b1001 | 0b0100 => 0b1101
     	n |= n >>> 2;  ===>  0b1101 | 0b0011 => 0b1111
        n |= n >>> 4;  ===>  0b1111 | 0b0000 => 0b1111
        n |= n >>> 8;  ===>  0b1111 | 0b0000 => 0b1111
        n |= n >>> 16; ===>  0b1111 | 0b0000 => 0b1111
        得到:
        0b1111 => 15
        返回:
        return 15 + 1 => 16
        -------------------------------------------------------
        如果cap 不减去1,即直接使n等于cap的话,int n = cap;
        我们继续用上边返回的cap => 16 传入tableSizeFor(int cap):
        
        cap = 16
        n = 16
        16 => 0b10000  16 >>> 1 => 0b01000
        n |= n >>> 1;  ===>  0b10000 | 0b01000 => 0b11000
        n |= n >>> 2;  ===>  0b11000 | 0b00110 => 0b11110
        n |= n >>> 4;  ===>  0b11110 | 0b00001 => 0b11111
        n |= n >>> 8;  ===>  0b11111 | 0b00000 => 0b11111
        n |= n >>> 16; ===>  0b11111 | 0b00000 => 0b11111
        得到:
        0b11111 => 31
        返回 return 31 +1 => 32
        
        而实际情况是应该传入cap = 16 , n = cap -1 = 15
        15 => 0b1111 
        
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        经过上面运算后得到:还是15
        
        返回结果:
        return 15 + 1 = 16
        所以我们得出结果:
        防止 cap 已经是 2 的幂数情况下。没有这个减 1 操作,
        则执行完几条无符号位移或位运算操作之后,返回的cap(32)将是实际所需cap(16)的 2倍。
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

说明

对于this.threshold = tableSizeFor(initialCapacity); 疑问?

**tableSizeFor(initialCapacity)**判断指定的初始化容量是否是2的n次幂,如果不是那么会变为比指定初始化容量大的最小的2的n次幂。

但是注意,在tableSizeFor方法体内部将计算后的数据返回给调用这里了,并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写:
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)

但是请注意,在jdk8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推迟到了put方法中,在put方法中会对threshold重新计算

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

包含另一个 “Map” 的构造函数

// 构造一个映射关系与指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
    	// 负载因子loadFactor变为默认的负载因子0.75
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);
 }

最后调用了 putMapEntries(),来看一下方法实现:

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //获取参数集合的长度
    int s = m.size();
    if (s > 0) {//判断参数集合的长度是否大于0
        if (table == null) { // 判断table是否已经初始化
                // 未初始化,s为m的实际元素个数
                float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int
            
                // 计算得到的t大于阈值,则初始化阈值,将其变为符合要求的2的n次幂数
                if (t > threshold)
                    threshold = tableSizeFor(t);
        }
        // 如果table已初始化过了,并且m元素个数大于阈值,进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 得到的key 和 value 放入 hashmap
            putVal(hash(key), key, value, false, evict);
        }
    }
}

注意

面试问题float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

(float)s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数(为了效率,应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。

例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,由于8是 2 的n次幂,那么

if (t > threshold) threshold = tableSizeFor(t);执行过后,新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

由于篇幅太长,不易阅读,我分成两篇文章:JDK集合源码之HashMap解析(下)

匿名

发表评论

匿名网友