一、Map概述
首先，在Java集合中，Map是一种以key-value键值对形式保存存储数据的特殊集合类。而HashMap是基于哈希表的Map接口的实现，再分析HashMap源码之前，有必要了解其底层的数据结构，这是源码设计的基础原则。
-
HashMap的数据结构
JDK1.8中，HashMap采用数组+链表+红黑树的数据结构实现，当链表长度超过阈值（8）时，将链表转换为红黑树，从而减少查找的时间。如下图所示Node<K，V> [] table 数组的每个元素Node都是一个单链表的头节点，链表主要是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。同时Node节点中维护了四个元素：key的hash值、key、value、已及对下一个节点的引用。
HahsMap结构图.png
二、HashMap相关属性、方法及源码分析
-
HashMap类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
-
HashMap方法及源码分析
1. put(K key, V value):
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里我们先从其put方法开始作为突破口，put之前先对key求了hash值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里求hash值的算法很简单，将key的hashcode值与其高16位进行异或运算。至于为什么要让高16位异或上低16位，后续会讲解到。接下来看put方法中的putVal()方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤(1)：tab为空则创建
// table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤(2)：计算index，并对null做处理
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 步骤(3)：节点key存在，直接覆盖value
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// 步骤(4)：判断该链为红黑树
// hash值不相等，即key不相等；为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤(5)：该链为链表
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 结点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 步骤(6)：超过最大容量 就扩容
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
从p = tab[i = (n - 1) & hash]代码中我们可以看出 Node节点的位置由数组长度减1 & key的hash值。首先我们先解释一下相关的运算符概念：
| 运算符 | 描述 |
|---|---|
| & | 按位与，任何二进制位和0进行 & 运算，结果都是0；和1进行 & 运算结果是原值。例：0 & 0 = 0 ， 0 & 1 = 0 ，1 & 1 = 1,1 & 0 =0 |
| l | 按位或，任何二进制位和0进行 l 运算，结果是原值；和1进行 l 运算结果都是1。 例：0 l 0 = 0 ， 0 l 1 = 1 ，1 l 1 = 1 ，1 l 0 =1 |
| ^ | 按位异或，任何相同二进制位进行 ^ 运算，结果是0；不同二进制位 ^ 运算结果是1。 例：0 ^ 0 = 0 ， 0 ^ 1 = 1 ，1 ^ 1 = 0 ，1 ^ 0 =0 |
| << | 左移，空位补0，被移除的高位丢弃 |
| >> | 带符号右移，被移位的二进制数如果最高位是0，右移后，空缺位补0；若最高位是1，最高位补1 |
| >>> | 无符号右移，被移位的二进制数无论最高位是0还是1，空缺位都补0 |
接下来分析为什么要以数组长度-1 & key的hash 作为Node节点存放的位置。首先从HashMap的属性我们可以得知，数组的长度永远是2的次幂，换成二进制就如下所示：
| key的hash值为0011 0110 | key的hash值为0011 0111 | |
|---|---|---|
| n = 16： 0001 0000 | n & hash = 0001 0000 | n & hash =0001 0000 |
| n = 32： 0010 0000 | n & hash =0010 0000 | n & hash =0010 0000 |
| n-1= 15 ： 0000 1111 | n & hash =0000 0110 | n & hash =0000 0111 |
| n-1= 31 ： 0001 1111 | n & hash =0001 0110 | n & hash =0011 0111 |
接下来，就可以很明显的看出如果使用数组长度n与key的hash值做&运算的话，只有n的二进制位为0的话，不管hash值的二进制位为0还是1其结果都是0，这样就增大了hash碰撞的概率,因此采用（n-1）& hash(key) 就能够减少hash碰撞。
假设如果数组长度n-1的二进制位在小于等于16位的情况下，即n<= 32768时 ，此时 n -1 的二进制位为 ： 0111 1111 1111 1111。这种情况下，我们可以发现key的hash值的高16位无论其是0还是1，对最终的运算结果并不能产生影响，就是说key的hash值的高16位并不影响Node节点位置的走向，这是又会增加hash碰撞的概率。为了减少hash冲突的概率，所以使用key的hashcode值与其高16位进行异或运算的结果作为最终hash值结果。
至于为什么在求key的hash值时采取异或运算，看下面这张图就能够明白了。
通过图中示例可以得知，只有异或操作才能够保证二进制位运算结果为0和1的概率保持一致，因此可以得知HashMap在源码设计时为了避免hash冲突是做了很大努力的。至此有关HashMap的hash值相关的问题可以告一段落了,最后附上一张hash值计算过程图。
hash计算.png
现在返回putVal方法来看看其中具体的操作：
-
①.判断键值对数组table[i]是否为空或为null，如果为空则调用resize()进行创建并初始化；
-
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
-
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
-
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
-
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
-
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
pulVal流程图.png
2. resize():
当数组长度大于阀值（DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR）或者进行初始化时调用resize()方法，每次数组扩容都是原来的两倍，同时扩容后的Node节点位置要么在其原来的位置，要么在原位置加上原容量的位置。具体源码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
threshold = Integer.MAX_VALUE;
return oldTab;//返回
}//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
table = newTab;//将新数组的值复制给旧的hash桶数组
if (oldTab != null) {//进行扩容操作，复制Node对象值到新的hash桶数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给e
oldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gc
if (e.next == null)//如果e后面没有Node结点
newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得存储位置
else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//将Node结点的next赋值给next
if ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0
if (loTail == null)//如果loTail为null
loHead = e;//将e结点赋值给loHead
else
loTail.next = e;//否则将e赋值给loTail.next
loTail = e;//然后将e复制给loTail
}
else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0
if (hiTail == null)//如果hiTail为null
hiHead = e;//将e赋值给hiHead
else
hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next
hiTail = e;//将e复制个hiTail
}
} while ((e = next) != null);//直到e为空
if (loTail != null) {//如果loTail不为空
loTail.next = null;//将loTail.next设置为空
newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处
}
if (hiTail != null) {//如果hiTail不为空
hiTail.next = null;//将hiTail.next赋值为空
newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度]
}
}
}
}
}
return newTab;
}
最后有个疑惑，当在移动链表时为什么要判断 e.hash & oldCap == 0
网友评论