概述
HashMap是Java集合框架中使用非常多的一种数据结构。它有以下特点：
- HashMap是基于哈希表Map的实现，允许key和value的值为null，保证不了存入数据的顺序；
- HahMap有两个参数影响它的性能：初始容量和负载因子；
- 默认的负载因子之所以是0.75，是为了时间和空间成本的一种平衡；
- HashMap不是线程安全的，没有实现同步；
HashMap是一种散列表，在JDK1.8中是通过：数组 + 链表+红黑树来实现的。
红黑树
红黑树是一种能自动平衡的二叉查找树，一般的二叉查找树的时间复杂度为O(logn)，当一般的二叉查找树退化之后会变成一个线性的列表，这个时候它的时间复杂度就变为了O(n)。但是由于红黑树本身的红黑着色和自平衡，使得它的时间复杂度最坏为O(logn)，而不是O(n)，所以JDK1.8才引入了红黑树。
属性
// 创建 HashMap 时未指定初始容量情况下的默认容量，默认16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// hashmap的最大容量，2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// hashmap默认的负载因子是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// hashmap中关于红黑树的三个参数
// 1.用来确定何时将链表转换为树
static final int TREEIFY_THRESHOLD = 8;
// 2.用来确定何时将树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3.当链表转换为树时，需要判断下数组的容量，当数组的容量大于这个值时，才树形化该链表；
// 否则会认为链表太长(即冲突太多)是由于数组的容量太小导致的，则不将链表转换为树，而是对数组进行扩容；
static final int MIN_TREEIFY_CAPACITY = 64;
// 用来实现数组中链接的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 每个节点的hash值
final K key; // 每个节点的key值
V value; // 每个节点的value
HashMap.Node<K, V> next; // 链表中当前节点的下一个节点
Node(int hash, K key, V value, HashMap.Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
// 用来实现红黑树的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
HashMap.TreeNode<K, V> parent; // 存储当前节点的父节点
HashMap.TreeNode<K, V> left; // 存储当前节点的左孩子
HashMap.TreeNode<K, V> right; // 存储当前节点的右孩子
HashMap.TreeNode<K, V> prev; // 存储当前节点的前一个节点
boolean red; // 存储红黑树当前节点的颜色(红，黑)
TreeNode(int hash, K key, V val, HashMap.Node<K, V> next) {
super(hash, key, val, next);
}
}
方法
我们通过学习HashMap最重要的三个方法来理解HashMap的使用。
1. put方法实现
put方法的大致流程如下：
- 对key的hashCode()做hash，然后计算出要保存到数组的index；
- 如果没有发生index冲突，直接放到数组里；
- 如果发生冲突了，以链表的形式保存在数组里，从链表尾部插入；
- 如果冲突导致该链表过长(超过了默认的TREEIFY_THRESHOLD)，将进行扩容或者将该链表转换为红黑树；
- 保存的时候，如果节点存在，就替换旧的key值；
- 如果数组满了，就扩充为原来的两倍；
其中源代码分析如下：
// put方法的主逻辑
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.1 根据hash值计算出节点在数组中的插入位置，如果该index处没有元素，则进行插入（(n-1) & hash 计算下标）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 2.2 如果该位置已经有元素存在
Node<K,V> e; K k;
// 3.1 比较原有元素和待插入元素的hash值和key值，如果都相等，则覆盖掉原来的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 3.2 如果原节点是红黑树结构，则调用红黑树的putTreeVal方法进行判断处理
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 3.3 如果原节点是链表的头节点，从这个节点向后查找插入位置
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 4.1 找到位置，插入数据
p.next = newNode(hash, key, value, null);
// 4.2 链表长度超过8，调用树形化方法进行扩容或转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 4.3 在该链表中找到已存在元素，替换掉旧的value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 5.1 待插入元素在hashmap中已经存在
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 6.1 是否需要扩容，threshold据说该字段叫做阈值(yu zhi)
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
其中树形化方法treeifyBin源代码分析如下：
// 链表的树形化方法：如果链表的长度超过了8，则调用该方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 1. 如果数组为空 或这 数组的长度小于 进行树形化的阈值(默认64) 就扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 2. 如果数组中的元素个数超过了阈值，进行树形化，转为红黑树(hd tl 红黑树头尾节点)
TreeNode<K,V> hd = null, tl = null;
do {
// 3. 从链表的第一个节点开始构建树，e是链表的第一个节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 4. 让数组的第一个元素指向红黑树的头节点，以后这个数组里的元素就是红黑树，而不是链表了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
2.get方法实现
get方法的大致流程如下：
- 首先hashMap的数组不为空，否则返回null;
- 直接定位到该节点，比较该节点的第一个元素，如果相等直接返回；
- 如果该节点是红黑树，调用红黑树的getTreeNode方法返回；
- 如果该节点是链表，挨个查询，匹配完成返回；
其中get方法的源代码如下：
public V get(Object key) {
Node<K,V> e;
// 通过key计算出hash，然后通过hash和key 调用getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 数组不为空，通过下标定位到节点，如果该节点的第一个元素不为空((n-1)&hash 计算下标)
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2. 定位到的节点的第一个元素匹配上，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 3. 如果该节点是红黑树，则调用红黑树的getTreeNode方法来返回
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 4. 如果该节点是链表，挨个匹配，匹配完成返回；
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize方法
HashMap的resize方法一般在以下两种情况下被调用：
- 当HashMap为null，即HashMap中的table数组为null，进行初始化时，会调用；
- 当HashMap的数组或者说bucket的容量已经超过了数组的阈值threshold(负载因子*容量)的时候，就会触发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)
// 新的阈值也扩为2倍
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);
}
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) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果数组元素唯一，没有next
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
// 将原链表拆分为两个链表，low为当前位置链表，high为高位的链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历当前链表，通过计算当前节点的hash&oldCap来判断该元素是放在哪个链表上
do {
next = e.next;
// 如果当前节点的hash&oldCap = 0 ，将该节点仍放置在当前low链表上
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 否则，放置在高位的high链表上
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 把刚才的链表赋值到数组对应的index上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
其中拆分为两个链表的时候，是根据e.hash & oldCap是否为0来划分的，这里大致说下：
- 首先，我们大部分对HashMap进行计算的时候，大部分都是2的幂次方来处理的，而2的幂次方又有以下规律：
取余(%)操作中如果除数是2的幂次方，则等同于与其除数减一的与(&)操作
所以说，在源码中经常有类似的(n - 1) & hash，其实这些操作与使用取余操作符(%)是可以互换的，但大家都知道，Java中位运算的效率是很高的，所以现在能用位运算的一般都不取余了；- 其次，我们要知道同一个链表中的节点，index是相同的，而index是根据(n - 1) & hash来计算的，n其实就是oldCap，就是原先数组的容量(默认16)。而扩容后，数组的容量会翻倍，在二进制上也就是高位多1位。因为扩容前后没有改变hash，并且"index=(n-1)&hash"，所以说index的计算就等同于(n-1)& 二进制最高位对应的hash位上是1还是0，由于oldCap等价于newTab的(n-1)的最高位，所以也就等价于e.hash & oldCap。
这样的好处：
- 省去了重新计算hash的时间；
- 由于e.hash & oldCap的结果可以理解为随机的，要么1要么0，这是由高一位决定的，所以这样就均匀的把有冲突的节点分散开来了；
链表扩容.png
问题
1. 存取时如何确定key在数组中的index？
对该节点的key获取hashCode值，然后高位运算计算hash，然后取模运算，计算出index；
在get和put的过程中，计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：
计算下标.png
计算hash方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。
在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用&位操作，而非%求余)，设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。
因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
如果还是产生了频繁的碰撞，会发生什么问题呢？作者注释说，他们使用树来处理频繁的碰撞(we use trees to handle large sets of collisions in bins)，在JEP-180中，描述了这个问题：
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
之前已经提过，在获取HashMap的元素时，基本分两步：
- 首先根据hashCode()做hash，然后确定bucket的index；
- 如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。
在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题。
2. 为什么负载因子的默认值是0.75？
该参数是泊松分布的参数，按照泊松分布的方式计算得出，在0.75处发生碰撞几率最小；
如果要查看HashMap具体的树化流程，可以参考：
HashMap的扩容及树化过程
