HashMap的结构
Map集合即Key-Value的集合，前面加个Hash，即散列，无序的。所以HashMap是一个用于存储Key-Value键值对的无序集合，每一个键值对也叫做Entry。
在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值查找要遍历链表，时间复杂度为O(N)，效率较低。因此JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，时间复杂度为O(logN)，这样大大减少了查找时间。
图1 JDK1.8之前的HashMap
图2 JDK1.8的HashMap
1、链表
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。来看图和具体代码：
image
//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> { final int hash;//哈希值 final K key;//key值
V value;//value值
Node<k,v> next;//链表中下一个节点
}
2、红黑树
//红黑树
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
TreeNode<k,v> parent; //父节点
TreeNode<k,v> left; //左子树
TreeNode<k,v> right;//右子树
TreeNode<k,v> prev; //上一个同级节点
boolean red; //颜色属性
}
3、位桶
transient Node<k,v>[] table;//存储（位桶）的数组
HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。
HashMap的基本数据结构是数组加链表。HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表尾部即可。当链表长度大于8时，链表转为红黑树，以此提高查找效率。
HashMap数组每一个元素的初始值都是Null。
HashMap的重要操作
如何由 key 确定键值对在数组中的索引
- 调用 key 对象自身的 hashCode 函数，得到 key 的哈希值。
- 进一步哈希，借助移位和异或运算，使得哈希值的高位也可以参与运算。
- 对进一步得到的哈希值进行取模运算
方法一：取 key 的哈希值，并进一步哈希，得到计算数组索引所用的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：jdk1.7的源码，jdk1.8没有这个方法，jdk1.8把这段代码融到具体需要算数组下标的时候去了，原理不变
static int indexFor(int h, int length) {
return h & (length-1);//由于length是2的幂，此时相当于取模运算
}
由于源码都是很优化的代码，所以能使用位运算的地方都尽量使用位运算。例如上面的代码使用位运算代替取模运算，大大提高了运算效率。而能够让位运算代替取模运算的条件是数组的长度为2的幂。因为数组的初始长度为 16，以后每次 reszie 的时候都是乘 2（左移一位），所以数组的长度总是2的幂。体现在源代码里面，就是：
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
即第 6 行的这句newCap = oldCap << 1，使得新数组长度永远是旧数组长度的 2 倍。
看到这里相信有很多人会有两个疑问，
(1) 为什么数组长度为 2 的幂时，取模运算可以使用代码里的位运算代替？
(2) 为什么通过 key 对象的 hashCode 方法得到的哈希值，需要进一步哈希，使得原始哈希值的高位也参与运算？
请带着这两个问题看下面这幅图，这幅图表示的就是从原始哈希值计算得到数组索引的整个过程，n 为数组的长度：
image
解答问题(1)：因为当 n 为 2 的幂时，n-1 的二进制表示就是若干个连续的二进制 1 组成的，此时做与运算就相当于取模运算。
解答问题(2)：正因为取模运算，取的仅仅是二进制数据的低位部分，如果不对高位数据进行处理，那么高位数据将完全没用上，换句话说就是哈希的效果不好。
HashMap 的 put 方法（get 方法类似）
put 方法的作用是添加新的键值对或根据键去更新值，其大致流程如下：
- 判断数组 table 是否为 null 或长度为 0，如果是则执行 resize() 进行扩容。
- 计算键值 key 对应的数组下标 i，如果 table[i]==null，则直接新建节点添加，转向步骤 6。
- 如果table[i] 不为空，判断 key 是否就在 table[i] 的首个元素，如果是则直接对 value 进行赋值，并返回旧的 value，算法结束。
- 如果不是，判断 table[i] 是否为红黑树，如果是红黑树，则转入对红黑树的操作（这一块不展开讲解）。
- 如果不是红黑树，遍历 table[i]，如果遍历过程中发现 key 已存在，则直接对 value 赋值，并返回旧的 value，算法结束。否则，将键值对插入链表尾部，然后判断插入后链表长度是否大于 8，如果是，就把链表转换为红黑树。
- 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。
put 方法实际上就是直接调用 putVal 函数，下面我们主要看 putVal 方法即可：
public V put(K key, V value) {
//put 方法在调用 putVal 方法之前，先计算好了 key 的哈希值。
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;
//步骤1，判断数组是否未初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//步骤2，根据 key 的哈希值，计算数组下标
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//步骤3，首先判断 key 是否就在首个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//步骤4，判断是否为红黑树
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);
//链表长度大于 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 存在，则直接覆盖 value，并返回旧的 value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//进行了一次插入操作，HashMap 的结构变化了一次，所以自加 1
//步骤6，超过了容量限定，就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize 方法（数组扩容）
扩容并不是简单的 new 一个容量更大的数组，然后把原来数组里的键值对拷贝到新数组里就行了的。还要对所有元素进行重哈希的操作，因为数组的 length 变为原来的 2 倍，原来 key 对应的 哈希值，经过取模运算后，得到的数组索引可能已经发生了变化。
看了下图就可以明白上面这段话的意思，n 为 table 的长度，图 (a) 表示扩容前的 key1 和 key2 两个 key 确定索引位置的示例，图 (b) 表示扩容后 key1 和 key2 两个 key 确定索引位置的示例。
image
元素在重哈希之后，因为 n 变为了原来的 2 倍，那么 n-1 的 mask 范围在高位会比原来多出 1 个比特。如果多出来的这个比特是 1，那么数组索引会发生如下图所示的变化：
image
因此，我们在扩容的时候，只需要对着原本的 hash 值，看新增的那个 bit 是 1 还是 0 就好了，如果是 0 的话索引不变，是 1 的话索引变为 “原索引 + oldCap”，可以参考下面 16 扩充为 32 的 resize 示意图：
image
resize 方法源代码，加上注释如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double 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);
}
// 计算新的resize上限
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];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((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;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到 bucket 里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 + oldCap 放到 bucket 里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
面试常考
为什么java8以后链表数据超过8以后，就改成红黑树存储？
这就涉及到拒接服务攻击了，比如某些人通过找到你的hash碰撞值，来让你的HashMap不断地产生碰撞，那么相同key位置的链表就会不断增长，当你需要对这个HashMap的相应位置进行查询的时候，就会去循环遍历这个超级大的链表，性能及其地下。java8使用红黑树来替代超过8个节点数的链表后，查询方式性能得到了很好的提升，从原来的是O(n)到O(logn)。
为什么Hashmap是线程不安全的？
HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。
网友评论