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

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

先了解一下hashmap的模型：

其中的node结点存放我们的键值对<k, v>;
首先，我们先了解hashmap给出的几个重要指标：

1 static final int default_initial_capacity = 1 << 4;  // 默认的初始化容量大小为16
2 static final int maximum_capacity = 1 << 30; // hashmap最大容量1g
3 static final float default_load_factor = 0.75f; // 默认负载因子值0.75，用于扩容时的计算
4 static final int treeify_threshold = 8; // 树的阈值，当链表长度大于等于8时，由链表转换成红黑树
5 static final int untreeify_threshold = 6; // 链表的阈值，暂时不清楚
6 static final int min_treeify_capacity = 64; // 最小树容量64

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

1 final int hash;   
2 final k key;      
3 v value;       
4 node<k,v> next;

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

1  static final int hash(object key) {
2         int h;
3         // 可以看到hash是根据对象的hashcode值来计算
4         // hashcode是一个int值，有32位
5         // 最后改变的是其低16位
6         return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
7  }

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

 

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

1  transient node<k,v>[] table; // 这就是真正的hashmap，一张哈希表，实际上就是由node结点组成的一维数组
2  transient int size; // 记录table中真正有效的结点个数，也就是键值对的个数
3  int threshold;  // 用来记录当前容量下，最适合存放多少键值对(容量*负载因子)
4  final float loadfactor; // 负载因子，若在构造方法没有特别设置，都是默认0.75
5  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下标的映射：

1 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源码分析——基本概念