在揭开 HashMap 的神秘面纱之前，先来一波常见 HashMap 面试题的连环炮！（特别说明：以下所有涉及 HashMap 的描述都是基于JDK1.8）
1.HashMap 底层的数据结构是什么?
2.HashMap 的存取原理？
3.使用 HashMap 在高并发情况下会有问题吗？
4.HashMap 为什么会线程不安全？
5.有什么线程安全的类代替么?
6.HashMap 中的 hash 算法和寻址算法是如何优化的？
7.HashMap 是如何解决 hash 碰撞问题?
8.HashMap 是如何进行扩容?
针对上面的面试题，我会通过源码尽可能的解释 HashMap 的原理，不过在看源码之前，先简单的回答上面的问题吧！
1.HashMap 底层的数据结构主要是由数组+单向链表实现的，当链表的长度超过 8 且数组节点数量大于 64 的时候，链表就会转变为红黑树结构。
2.HashMap 添加数据之前都会调用 hash 算法计算出 key 的 hash 值，如果 hash 值对应数组下标没有链表节点，则直接将节点赋值到数组上；否则将会在链表尾部添加节点，如果链表长度超过 8 且数组节点数量大于 64 则会转变为红黑树结构。HashMap 获取数据之前同样会调用 hash 算法计算出 key 的 hash 值，如果 hash 值对应数组下标有链表的节点，再判断节点的 key 与 get 方法传入的参数 key 是否值相同，如果一样则直接返回节点的 value；否则判断节点是否有下一个节点，如果有则遍历链表或者红黑树查找，如果节点的key与get方法传入的参数key值相同则返回对应的value，否则返回null。
3.由于 HashMap 不是线程安全，所以在高并发场景下会造成数据丢失、数据覆盖这些问题。（JDK1.8 之前还有可能出现死循环，这和实现方式有关，JDK1.8 之前数组链表是通过头插入的方式，JDK1.8 的数组链表是尾插入）
4.因为 HashMap 的实现没有使用到任何线程安全的类或关键字（简单粗暴的回答）
5.有三种方法，第一种是使用 ConcurrentHashMap 类代替；第二种是使用 Collections.synchronizedMap(Map<K,V> m)将 HashMap 对象转为线程安全（实际上就是在方法前面使用 synchronized 关键字保证线程安全）；第三种就是使用 Hashtable，不过效率相对其它方法就比较低。
6.hash 算法的优化：调用对象的 hashCode() 方法，然后将 hashCode 值的高16位和低16位进行异或运算，这样可以尽量避免一些 hash 值出现冲突；寻址算法的优化：计算机的与运算比取模运算效率高，所以 HashMap 的寻址算法用与运算替代取模运算，提升性能。
7.用链表和红黑树处理 hash 碰撞。HashMap 在 hash 碰撞的时候会形成链表，当链表长度超过 8，并且当前数组节点数量大于 64 的时候才会转化为红黑树结构。这样做的原因是红黑树的查询复杂度是 O(logn)，而链表的复杂度是O(n)。而当 HashMap 的红黑树的节点小于 6 时重新转化为链表结构。
8.有两种情况会触发扩容机制：a.初始化 HashMap 后第一次 put 节点的时候；b.添加节点后，数组长度超过临界值。默认扩容方式为容量 * 2、阈值 * 2，添加节点时当链表长度大于 8 且数组总数量大于 64 时会转换为红黑树提高查找效率；扩容时当红黑树中节点小于等于 6 时会转回链表。如果节点没有下一个节点连接，则扩容后节点的下标是使用旧数组的hash，这样可以避免重新计算hash，优化性能。
接下来，让我们进入正文，看下 HashMap 类的一些核心源码和常用的方法。（看源码需要耐心，不能被几十几百行的代码吓到。一开始看源码需要抓住重点，有些方法或者变量看不懂的话，可以先放一放，过于深入不利于你学习源码的。先通读一遍核心源码，然后一行一行的细品...）
HashMap 类源码剖析
看 HashMap 类源码之前，先看下 HashMap 究竟长什么样子吧~
HashMap 基本数据结构为数组，当有碰撞的时候会在同一个 hash 位置上形成一个链表，当链表长度大于 8 且数组节点数量大于 64 则将链表转化为红黑树。
普通节点和红黑树节点
/**
* 基础节点Node
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
// 下面还有一坨，先省略
}
/**
* 红黑树节点
*/
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;
// 下面还有一坨，先省略
}
类常用的变量
// 默认数组容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 数组容量最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认链表转为红黑树的界限为8
static final int TREEIFY_THRESHOLD = 8;
// 默认小于等于6为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 数组节点数量大于64时才允许转换为树。
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储节点的数组，transient关键字表示该属性不能被序列化
transient Node<K, V>[] table;
// 将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient Set<Map.Entry<K, V>> entrySet;
// 节点数量
transient int size;
// 统计该map修改的次数
transient int modCount;
//临界值，也就是节点数量达到临界值时，会进行扩容。
int threshold;
// 加载因子
final float loadFactor;
构造函数
HashMap 可以通过下面四个构造函数创建对象，如果没有指定initialCapacity和loadFactor就会使用默认的值。值得注意的是，第四个构造函数可以传入一个 Map 对象，可以将参数的 Map 对象加入到 HashMap 对象里面去。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
putMapEntries方法
/**
* 将参数m中的所有节点添加至 HashMap 中
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取需要添加的 map 的长度
int s = m.size();
if (s > 0) {
if (table == null) { // 如果 table为空则初始化数组
float ft = ((float) s / loadFactor) + 1.0F;
int t = ((ft < (float) MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold) // 如果需要添加map的长度大于table数组的临界值则扩容
resize();
// 将需要添加map转化为set，便于遍历。将遍历的结果塞进hashmap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
hash方法
/**
* 获取hash值
* hashCode值的高16位和低16位进行异或运算，这样可以尽量避免一些hash值出现冲突
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通过上面的一些源码铺垫，接下来看 HashMap 的核心方法就容易多啦！
添加节点 put(K key, V value)
// 添加节点
public V put(K key, V value) {
// 添加节点实际是调用 putVal() 方法
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;
//要插入位置上没有节点，则直接将节点赋值到数组上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 执行到这一步代表要插入的位置上已经有节点
Node<K, V> e;
K k;
// 如果哈希值相等，key也相等，则是覆盖value操作
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 ，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 循环链表节点，哈希值相等，key也相等，则是覆盖value操作
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e不是null，说明有需要覆盖的节点
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 这是一个空实现的函数，用作LinkedHashMap重写使用
afterNodeAccess(e);
return oldValue;
}
}
//如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null
//检查是否应该扩容
++modCount;
//判断size是否超过阈值
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
当执行 map.put() 的时候，实际上是调用 putVal() 方法，源码中好多 if...else 呀，画了张流程图更有利于理解源码！
简单来说，就是在插入数据的时候判断数组是否已存在 key 对应的 hash 值，如果没有的话直接插入数据，否则就判断 hash 值对应的链表或者红黑树是否存在 key，有的话就覆盖原来的 value，没有的话就插入链表或红黑树。
获取节点 get(Object key)
// 根据 key 获取节点
public V get(Object key) {
Node<K, V> e;
// 调用 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; // first 是头节点
int n;
K k;
// table节点数组不为空（证明数组已被初始化） && 节点数组长度大于0（证明数组有节点）&& hash值对应数组下标有节点
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 判断头节点的hash值是否与参数的hash相同，或者当参数key不为null的情况下，头节点的key是否与参数key相同
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
// 符合以上条件则证明头节点就是要获取的key值
return first;
// 如果头节点有下一个node节点，则证明同一个hash值上有多个node节点
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);
}
}
// 返回null。有可能的是因为table节点数组没有被初始化，或节点数组没有值，或table数组下标没有key对应hash值
return null;
}
简单来说，通过 HashMap 的 hash 算法判断数组是否存在节点与参数 key 的 hash 值相同，如果相同再判断节点的 key 与参数 key 是否一样，不一样的话再进一步判断节点是否在链表或红黑树结构，再采取相应的措施查找是否存在节点的 key 与参数 key 一样，有的话就直接返回节点 value，否则就返回 null。
扩容 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;
// 如果table节点数组不为空
if (oldCap > 0) {
// 如果当前容量已经到达上限
if (oldCap >= MAXIMUM_CAPACITY) {
// 设置阈值是2的31次方-1
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新数组的容量为旧数组的容量两倍。
newThr = oldThr << 1;
} else if (oldThr > 0) // table节点数组未被初始化，但有阀值，代表new HashMap()时指定了容量
newCap = oldThr; // 新数组的容量就等于旧的阈值
else { // 执行到这里就代表上面的判断都没有执行，newCap没有被赋值，所以设置新数组的容量和阀值为默认大小
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 执行到这里就代表执行了上面判断的else if (oldThr > 0) 语段，则为新数组计算阀值
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;
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 { // 如果该节点是链表结构则循环链表判断是否需要迁移节点到新索引上
// 低位的头和尾
Node<K, V> loHead = null, loTail = null;
// 高位的头和尾
Node<K, V> hiHead = null, hiTail = null;
// 下一个节点
Node<K, V> next;
// 循环链表，大概的思路为：节点的 hash 值与旧的容量与运算等于 0 则代表扩容前和扩容后的索引一样，不用重新计算索引值（JDK1.8后的优化）
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 如果低位链表不为空，证明扩容前和扩容后的索引一样，直接添加到原始下标
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 如果高位链表不为空，证明扩容前和扩容后的索引不一样，添加到原始下标+旧的容量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容的代码虽然看起来好长好复杂，其实可以简单的理解为两部分：先计算扩容后的数组容量和阀值并赋值给新数组，再将就数组的节点迁移到新数组。
先将 resize() 方法拆成两部分，第一部分是 5~35 行，看注解基本知道是如何计算数组容量和阀值，重点看第二部分 36~84 行，将旧数组的节点迁移到新数组！（注意：JDK1.7 和 JDK1.8 的扩容代码有区别，JDK1.8 在迁移到新数组的代码部分做了优化，就是判断旧数组中的节点是否需要重新计算数组索引位置，如果扩容前后数组索引位置一样则直接迁移到新数组相同的索引位置，省去了重新计算 hash 值的时间）
我认为第二部分中最核心的一行就是第 57 行 if ((e.hash & oldCap) == 0)，就是这一行判断旧数组的节点在扩容前后的数组索引位置是否一致。emmmm...看起来还是挺抽象的，还是通过写代码debug和画图理解原理吧！
需要强调的一点是，HashMap 的数组容量一定是 2^n ，具体代码参考 HashMap 类的 tableSizeFor 方法。
示例：
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap(8);
for (int i = 1; i < 6; i++) {
map.put(i,i);
}
map.put(13, 13);
// 执行以下代码就会使 HashMap 扩容，因为已经超出容量为 8 的数组
for (int j = 0; j < 5; j++) {
map.put(j*10,j*10);
}
}
先来看下扩容前（示例代码中执行到第六行），数组节点的分布情况：
为什么key为 5 和 13 会形成一个链表呢？回顾一下 HashMap.put() 方法，计算索引值的公式为：(n - 1) & hash ，其中 n 代表数组容量。(示例中数组容量为 8 ，key为 5 的 hash 为 5，key为 13 的 hash 为 13)
如果两个 key 的 hash 值和数组容量-1 与运算结果一样的话就会放到同一索引上形成链表。
然后执行到 8~10 行时，发现数组容量超过阀值，就会执行 resize() 方法！
此时咱们看 resize() 的源码，循环 HashMap 旧数组的时候，执行到 41 行的时候发现索引值为 5 位置上有节点，然后会执行 47~81 行循环链表；通过执行 (e.hash & oldCap) == 0判断链表上的节点是否需要重新计算迁移到新的索引上。
当发生扩容的时候，key 为 13 和旧数组容量与运算并不等于 0，就会重算计算 key 为 13 在新数组中的索引位置。这样就会之前的冲突的节点均匀的分散到新的数组上，除了使用与运算比较冲突节点的操作之外，更加巧妙的是，将冲突的节点分散到新数组的索引为旧数组索引加上旧数组的容量，也就是对应第 79 行 newTab[j + oldCap] = hiHead ，譬如示例中 key 为 13 的节点被分散到新数组的索引值为 13 ，也就是旧数组索引值(5) + 旧数组容量(8)
删除节点 remove(Object key)
// 删除key对应的value
public V remove(Object key) {
Node<K, V> e;
// 实际上是调用removeNode()方法删除数组上的节点
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
// 如果数组没被初始化 或 数组没数据 或 参数hash在数组中没有对应的节点则会直接返回null
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K, V> node = null, e;
K k;
V v;
// 如果节点的hash和key都和方法参数一样则
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果是红黑树结构
if (p instanceof TreeNode)
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else { // 链表结构则循环链表，直到找到对应的节点才跳出节点或循环结束
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 删除节点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是红黑树结构则通过红黑树的算法删除节点
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
// HashMap 节点数量减一
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
总结：
以上通过多个流程图或结构图分析了常用的增删查三个方法，还重点讲了 HashMap 扩容机制。但是我写这篇博客的目的是了解 HashMap 的核心方法和原理，一开始不必要过多陷入细节，譬如红黑树，各种位运算的优化（难道我会告诉你，我不熟悉红黑树吗，hhhh，不过之后看懂的话我一定会补充回来）。
对 HashMap 中红黑树的实现有兴趣的朋友，可以参考以下我认为不错的博客，或者另行查阅~
参考资料：
https://blog.csdn.net/v_july_v/article/details/6105630
https://www.cnblogs.com/mfrank/p/9227097.html
网友评论