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

2022-10-31 15:43:52

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

先了解一下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源码分析——基本概念

码农公寓

相关文章