【Java】HashMap源码分析——基本概念

时间:2023-03-09 06:42:58
【Java】HashMap源码分析——基本概念

在JDK1.8后,对HashMap源码进行了更改,引入了红黑树。
在这之前,HashMap实际上就是就是数组+链表的结构,由于HashMap是一张哈希表,其会产生哈希冲突,为了解决哈希冲突,HashMap采用了开链法,即对于用对象hashCode值计算哈希表数组下表时,当出现相同情况时,会在相同的地方追加形成链表的形式。对于分布均匀的情况下,仅仅是一个一维数组,查询时时间复杂度为O(1),当分布不均匀的时候,在有的地方会形成链表,极端情况下完全退化成一个链表,查询时就需要遍历整个链表,时间复杂度就为O(n),极为耗时。
在引入红黑树后,当满足一定条件时,链表就会转换成一棵红黑树。红黑树是一种AVL树(自平衡查找二叉树),相比于链表,其查找时的时间复杂度还是很优秀的(O(logn))!

先了解一下HashMap的模型:

【Java】HashMap源码分析——基本概念

其中的Node结点存放我们的键值对<K, V>;
首先,我们先了解HashMap给出的几个重要指标:

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 默认的初始化容量大小为16
static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量1G
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子值0.75,用于扩容时的计算
static final int TREEIFY_THRESHOLD = 8; // 树的阈值,当链表长度大于等于8时,由链表转换成红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 链表的阈值,暂时不清楚
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树容量64

以上就是几个基本指标,其规定了在以后操作中的界限!
其中Node<K, V>是一个内部类,封装了这个结点的所有信息,有如下几个成员

 final int hash;
final K key;
V value;
Node<K,V> next;

key和value不必多说,其中的hash是利用key对象的hashCode计算得到的,具有唯一性:

  static final int hash(Object key) {
int h;
// 可以看到hash是根据对象的hashCode值来计算
// hashCode是一个int值,有32位
// 最后改变的是其低16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

其中的next就是为了解决哈希冲突,当产生哈希冲突时,next就可以指向一张链表,或者一棵黑树!

接下来是几个重要的成员:

  transient Node<K,V>[] table; // 这就是真正的HashMap,一张哈希表,实际上就是由Node结点组成的一维数组
transient int size; // 记录table中真正有效的结点个数,也就是键值对的个数
int threshold; // 用来记录当前容量下,最适合存放多少键值对(容量*负载因子)
final float loadFactor; // 负载因子,若在构造方法没有特别设置,都是默认0.75
transient int modCount; // 用来记录操作数

看到这,我们先不急着往下进行,先仔细分析下这些成员之间的关系:
table:真正开辟的空间,其length就是真正的容量大小
size: 真正使用的空间,总的键值对的个数
threshold:这个就比较有意思,其决定了是否需要进行扩容的操作,是一个阈值!
比如说,在初始化时,默认的容量是16,那么table的length就是16,其threshold=容量×负载因子=16×0.75=12,这就代表着,当size大于12时,就会进行扩容(容量会×2,threshold会根据新容量重新计算)的操作!
这样做的目的很明确,就是为了减少哈希冲突!有效元素的个数少于哈希表的总大小时,其产生哈希冲突的可能性一定是小于相等情况的!
综上可知,在非极限情况下(容量=threshold=MAXIMUM_CAPACITY=2^30)时,threshold总是小于容量,size总是不大于threshold!
这一切的做法,都是为了能够减少哈希冲突产生的可能性!

说到这里还是不能往下进行,我们需要知道Node中的hash成员是如何与table中的下标产生对应关系的,以及哈希冲突是如何产生的:

首先是关于hash值和table下标的映射:

 index =   hash  & (table.length - 1)

这是一个非常巧妙的运算,当table.length满足二的整数幂时,就满足:
hash & (table.length - 1) == hash % table.length
例如:2%8 = 2 即:
0000 0010 2
&
0000 0111 (8 - 1)
0000 0010
二的整数幂减一得到的二进制数,其有效位全是1,通过&可以直接得到符合条件的有效位的值!
其实就是取余,用余数作为table的下标,而位运算的速度是比其余快的多,所以采用了这种方式!
所以这就是为什么table的大小必须是二的整数幂,以及扩容时都是乘2!

哈希冲突的产生:
以初始table.length = 16为例
对于hash = 1, 和 hash = 17来说,其对于16取余的结果都是1,那么这两个不同的hash值对应了同一个table的下标,这就产生了哈希冲突!

先将HashMap简单介绍到这,后续我会继续分析HashMap,若有错误或不足之处,还请指出!

我在CSDN也放了一篇【Java】HashMap源码分析——基本概念