HashMap
HashMap
什么是HashMap
HashMap 是一种快速的查找并且插入、删除性能都良好的一种 K/V键值对的数据结构，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。
HashMap的底层在JDK1.8之前采用数组+链表组成，用(n - 1) & hash找到数组索引位置，如果冲突则使用拉链法解决。在JDK1.8之后的HashMap初始数据结构仍采用数组+链表，当某个桶链表的长度大于**8时，会先调用treeifyBin()方法，这个方法会判断数组长度是否小于64**，如果大于或等于则执行转换红黑树操作，以减少搜索时间；反之则调用resize()进行扩容。
HashMap的底层数据结构
JDK1.8 之前
底层采用数组+链表，用(n - 1) & hash找到数组索引位置，若冲突则用拉链法解决冲突。
拉链法 简单来说就是将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
JDK1.8 之后
底层初始数据结构仍采用数组+链表，当某个桶链表的长度大于**8时，会先调用treeifyBin()方法，这个方法会判断数组长度是否小于64**，如果大于或等于则执行转换红黑树操作，以减少搜索时间；反之则调用resize()进行扩容。
JDK1.8的数据结构示意图如下：
其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。
- 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
- 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
- 如果链表长度>8&数组大小>=64，链表转为红黑树
- 如果红黑树节点个数<6 ，转为链表
解决哈希冲突有哪些方法呢
- 链式地址法：把存在Hash冲突的key，以单向链表来进行存储。
- 开放定址法：开放定址法也称线性探测法，就是从冲突的位置再接着往下找，给冲突元素找个空位
- 再哈希法：换种哈希函数对key进行Hash，一直运算，直到不再产生冲突为止。
- 建立公共溢出区：再建一个数组，把冲突的元素放进去。
HashMap是如何解决哈希冲突的
在JDK8之 前HashMap采用的是链式寻址法解决哈希冲突的，而JDK8之后则是通过链式寻址法以及红黑树来解决Hash冲突。
HashMap为什么在JDK1.8中多了红黑树呢？
每次遍历一个链表，平均查询的时间复杂度为O(n)，而红黑树有自平衡的特点，可以防止不平衡情况的发生，保证插入和查询的时间复杂度控制在O(logn)，并且红黑树是弱平衡树，相较于AVL树不会进行频繁的旋转保证平衡的操作，所以性能较高。
HashMap中put方法的整体流程知道吗？
先上个图看看
- 首先通过
hash方法获取哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) - 判断table是否为空或者长度为0，如果是则调用
resize()方法扩容。 - 根据哈希值计算确定元素存放在哪个桶中，如果桶为空，则直接插入桶中，否则覆盖。
- 判断tab[i]是否为树节点，是则在树中插入节点，否则在链表中插入节点。
- 如果链表插入节点时阈值大于等于8，则需要将链表转为红黑树。
- 所有元素处理完后，判断是否超过阈值;
++size > threshold，超过则扩容。
HashMap的put方法源码和注解都在下方，读者可自行debug调试理解下。
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未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素（处理hash冲突）
else {
Node<K,V> e; K k;
// 判断table[i]中的元素是否与插入的key一样，若相同那就直接使用插入的值p替换掉旧的值e。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断插入的是否是红黑树节点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 不是红黑树节点则说明为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
// 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
// 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是对数组扩容。
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;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
get方法的流程了解吗？
老样子，先看流程图：
public V get(Object key) {
Node<K,V> e;
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 数组元素相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一个节点
if ((e = first.next) != null) {
// 若是红黑树，则走红黑树的遍历逻辑
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 反之说明这是一个链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
为什么HashMap的容量是2的幂次方
为了HashMap 存取高效，尽量减少碰撞，数据分配均匀，hash值能够充分的散列。hash值范围很大（-2147483648 到 2147483647），只要哈希函数映射的比较松散，一般很难出现碰撞。但直接使用哈希值内存放不下，那么能直接想到的是使用hash值%数组大小定位位置，而HashMap使用hash值和（数组大小 - 1）做位与运算，计算元素在数组中的索引（与前面算法效果一致，但效率高）。 与运算(&)的用途：清零，即两个二进制数，有一位是0，那么得到的数就是0。hash值是不固定的，它的二进制数有0有1，想尽量减少碰撞，那么需要保证与运算(&)的值全为1，这样能保证最后运算结果完全取决于hash值，一个（2^n）-1的数得到的二进制数就都是1，例如（16-1）的二进制是1111。
HashMap的扩容了解吗？
HashMap是基于数组+链表和红黑树实现的，但是初始化容量是固定的，默认为16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
但是随着数据得不断新增以及负载因子的作用下，内存空间就需要扩容才能存放更多的数据。并且在JDK1.8中已经优化，可以不再需要重新计算哈希值。
那么什么时候扩容呢？
为了减少哈希膨胀，当HashMap达到一个临界值时，就会触发扩容，这个临界值就是负载因子和当前容量的容量大小来决定的，我们来看看HashMap默认方法：
那就是大于16x0.75=12时，就会触发扩容操作。
为什么负载因子是0.75？
先看看下HashMap中的一段注解：
其实就是对空间和时间的成本之间做权衡，当元素多时，空间比较少的时候才扩容，这样容易出现哈希碰撞，查找时间成本也增加了；当元素少时，空间还很多时扩容，虽然查找时间成本降低了，但空间成本增加了。
那么具体的扩容方法其实就是数组迁移，因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以，元素，要么在原位置，要么在原位置再移动2的次幂，如下图所示：
扩容的主要逻辑源码，注释都在下方：
HashMap多线程可能导致的问题
首先HashMap不是线程安全的，可能会发生几种问题：
- 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
- 多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
- put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。