HashMap实现了Map接口，提供对key-value的键值对操作，允许null值和null key。HashMap类大致相当于Hashtable。不保证任何有序性。如果hash函数能把key均匀的分布到bucket中，那么get()和put()方法都是O(1)的时间复杂度。
基本属性
// 默认的capacity是16，必须是2的整数次幂， 为什么下面会聊
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 允许的最大的capacity，如果在构造函数中传入的自定义capacity值大于这个值，就被会修改成这个值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当链表长度为8的时候就转化成红黑树(如果链表长度为8的时候，是红黑树还是链表)
static final int TREEIFY_THRESHOLD = 8;
// 当红黑树节点少于6个的时候，就转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 此处需注意，java8之前是当Node节点数超过HashMap实际容量(即数组容量*加载因子)时扩容，
// 而在java8中，当数组容量还没达到下面这个值时，只要链表长度达到树化阀值也就是8即扩容
// ------------ 这个字段的真实作用到底是什么 ------------
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储hashMap数组的哈希桶
transient Node<K,V>[] table;
// 保存map中所有key的一个集合
transient Set<Map.Entry<K,V>> entrySet;
// map中真实存在的key-value键值对的数量
transient int size;
// 记录HashMap中键值对数量的改变或者hashMap结构的改变次数, 用于在遍历集合的时候快速失败
transient int modCount;
// 所能容纳的key-value对极限, 超过这个值将会扩容
// 如果使用的是带两个参数的构造函数，在向map中put第一个键值对之前
// 这个值表示的是大于等于参数指定capacity的第一个2^n的数
// 在第一次resize()过程中，这个字段将会被更新为 catacity * loadFactor
// 这个值的最大值为Integer.MAX_VALUE
int threshold;
// 真实的负载因子
final float loadFactor;
hash()函数源码
// 计算key的hash值，如果key是null, hash值是0
static final int hash(Object key) {
int h; // int类型，32个bit
if (key == null) {
return 0;
}
h = key.hashCode() // 获取hashcode值
// ^(异或运算符): 两个位相同为0，否则为1
// 1. 先把key的hashcode()值右移动16位，因为是无符号右移动，所以得到的二进制结果，左边16bit都是0
// 2. 将key的hashcode()值和右移的结果进行异或运算
return h ^ (h >>> 16);
}
举个例子，假设某个key的hashcode()返回值为: 488970385
00011101 00100101 00011000 10010001 // 488970385的二进制
00000000 00000000 00011101 00100101 // >>> 16之后的结果左边16位都是0
上面两串数字进行^运算，得到的结果就是hash()方法的返回值。是一个32bit的int类型的值，取值范围是 -2147483648~2147483647，也就是说我们根据key计算出来的hash值大部分概率是一个很大的值。而我们hashmap的table数组的长度一般不会很大，默认的才16。
现在我们来思考两个问题
- 为什么java设计者在计算key的hash值时要像上面那样做？
- 为什么hashmap的capacity需要是2的整数次幂？
我个人觉得这两个问题需要放在一起回答，在总结答案之前，看一下hashmap根据key的hash值是怎么确定在table数组中的index的。
h = table.length // table.length就是capacity
index = (h - 1) & hash // &运算，对比的两个位上都是1，结果才是1
如果h是2的整数次幂，h-1的二进制表示永远都是00000000011111111这种前面n个0，后面m个1的二进制数字。
当capacity是16的时候: index = 1111 & hash， 则index的最小值是0，最大值是15，刚好在capacity的范围内。
当capacity是32的时候: index = 11111 & hash， 则index的最小值是0，最大值是31，刚好在capacity的范围内。
从上面可以看到，利用hash值计算index的过程是准确而且高效的，因为为算法比取模要快速的多。现在快速计算index的问题解决了，剩下的问题如果hash()的返回值随机性比较差的话，那么hash冲突的可能性就会很大，hashmap的性能就会下降。所以hash()函数内部h ^ (h >>> 16) 是为了把hashcode()的返回值的高16位也参与到计算key的hash值过程中来，使的hash()返回值的低16位的随机性更好。我们在计算index的过程中，一般只会用到hahs()返回值的低几位。
put()源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table数组还没有没有初始化，就进行初始化
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
// 计算出idnex，并且key之前不存在，且没有hash冲突，直接放到tab[i]中
// 把table[index]赋值给变量p
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
Node<K,V> e; K k;
// key已经存在，直接覆盖
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
// 此时e表示替换之前table[index]上的元素
e = p;
// 表示p是一个红黑树的节点，把key-value放到树中
} else if (p instanceof TreeNode) {
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 执行到下面代码块，说明table[index]位置上是一个链表
} else {
for (int binCount = 0; ; ++binCount) {
// p.next == null，说明是最后一个节点了
if ((e = p.next) == null) {
// 把key-value放到链表的结尾
p.next = newNode(hash, key, value, null);
// 如果链表长度 > 8的时候就转为红黑树， 注意这里不是 >= 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果key已经存在链表中，则直接覆盖
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
// 如果key是已经存在的，则进行替换/或者不替换，然后返回已经存在的值
if (e != null) {
V oldValue = e.value;
// onlyIfAbsent如果等于true, 则表示相同的key，不替换，而是直接忽略
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// HashMap这个方法什么都没做，留给LinkedHashMap扩展用的
afterNodeAccess(e);
return oldValue;
}
}
// 更新modCount，表示结构被修改了一次
++modCount;
// 进行扩容判断
if (++size > threshold)
resize();
// HashMap这个方法什么都没做，留给LinkedHashMap扩展用的
afterNodeInsertion(evict);
return null;
}
resize()源码
// 扩容操作
final Node<K,V>[] resize() {
// 保存扩容之前的table数组
Node<K,V>[] oldTab = table;
// 扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// -------这个玩意到底是啥------
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 表示不是第一次初始化
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果扩容之前的capacity已经达到最大值了，就不会对table数组进行扩容
threshold = Integer.MAX_VALUE;
return oldTab;
// 这里需要稍微注意一下，不管下面的逻辑成不成立，newCap的值都已经改成oldCap * 2了
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {
// 如果扩容之前的capacity >= DEFAULT_INITIAL_CAPACITY
// 并且扩容之前的capacity * 2 < MAXIMUM_CAPACITY
newThr = oldThr << 1; // newThr = oldThr * 2
}
// 下面的if分支都是第一次初始化才会执行
} else if (oldThr > 0) { // 使用两个参数的带参构造创建的map, oldThr一般都是大于0的
// 使用oldThr也就是threshold作为map初始化时候的capacity
newCap = oldThr;
} else { // 使用普通构造函数创建的map初始化会执行到这里
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 对newThr的值进行限制
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 设置threshold为 newCap * loadFactor
threshold = newThr;
// 根据newCap创建一个新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 这个代码块执行的是扩容的逻辑，初始化不需要走这个逻辑
if (oldTab != null) {
// 遍历oldTable
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果oldTable[j]这个位置上保存了内容
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) {
// 执行到这里说明在odTable[j]这个位置上没有发生hash冲突，只存储了一个元素
// 根据节点的hash值计算在新的table中的索引
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode)
// oldTab[j]位置上是一颗红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// oldTab[j]位置上是一个链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 获取当前节点的下一个节点
next = e.next;
// 这个地方有意思了，我们知道oldCap肯定是一个2^n的数字，二进制表示就是
// 0000010000 这种形式，只有一个1，前后都是0
// 我们假设oldCap = 16, 那么16的二进制位10000，如果 e.hash & 10000 = 0
// 则说明e.hash的二进制表示倒数第5位是数字0，而不是1。 这意味着什么呢?
// 当capacity从16扩到32的时候，我们来分析一下对一个key的hash值进行计算index的过程
// capacity=16的情况: index = hash() & (cap -1) ====> hash() & 00000000 00000000 00000000 00001111
// capacity=32的情况: index = hash() & (cap -1) ====> hash() & 00000000 00000000 00000000 00011111
// 仔细观察可以发现，影响index值的范围从cap-1的倒数4位变成了倒数5位
// 再进一步，我们假设某个key的hash()返回值为: 11101001001010001100010000011， 那么下面两个计算的结果是一样的
// 11101001001010001100010000011 & 00001111 = 3
// 11101001001010001100010000011 & 00011111 = 3
// 也就是说扩容前后，这个key在table中的index是不变的
// 看另外一种情况
// 11101001001010001100010010011 & 00001111 = 3
// 11101001001010001100010010011 & 00011111 = 3 + 16 = 19
// 总结一下，对于一个key，它的hash()返回值是不会变的，当扩容一倍之后，这个key对于在table中的index要么不变，要么就是扩容之前的 index + 扩容的数量
// 这样，就不用和jdk1.7一样，每次使用 (capacity - 1) & hash 去计算index了。在效率上还是有提高
if ((e.hash & oldCap) == 0) { // 扩容之后位置不变的
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 扩容之后index=index+oldCap的
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 把oldCap上一个链表中的数据，经过处理，放到新的table中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
思考
HashMap负载因子的大小对效率的影响
在capacity不变的前提下，复杂因子越大，说明hash冲突比如会变多，链表甚至树化的情况也会变多，二链表和黑红数的遍历熟读都是没有数组快的。所以负载因子越大，hahsmap迭代的效率就越低。
什么是fail-fast，hashmap怎么实现的
fail-fast个人理解就是当检测到程序出现错误的时候，立马进行反馈并且停止正常操作。jdk并不保证快速失败一定有效(可能无法检测错误)。
hash()方法的实现是怎样的?
- 获取key的hashcode()值h
- h & (h >>> 16)
hash()方法为什么这么设计？
- 提高了key的hash值的低16位的随机性，降低了hash冲突
为什么capacity要求是2的整数次幂?
- 一个2的n次幂的整数减去1之后的2进制数据前面的n位都是0，后面m位都是1，hash() & (capacity - 1)就能够快速的计算出key对应的hashcode在table数组中的下表
- 经过观察可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，扩容之后，元素的位置要么是在原位置，要么是在(原位置+旧容量大小)的位置上，因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
网友评论