HashMap是基于hash表的Map接口的实现，Since JDK 1.2。HashMap基本上和Hashtable（Since JDK 1.0）提供的功能差不多，除了是线程不安全以及key和value可以为null。
阅读源码想要解决以下部分问题：
HashMap面试相关思维导图
数据结构：
左边是hash table，若hash相同，则元素会被放入同一个桶中，组成链表，大于一定长度时，基于效率考虑，会变成红黑树。
HashMap 数据结构
本篇文章基于：JDK1.8.0_91
先来看一些常量：
// 没有指定size时，默认的初始大小：16
// 0000 0001 左移4位：0001 0000，即1*2^4=16
static final int DEFAULT_INITIAL_CAPACITY =1 <<4;
// 哈希表最大长度，最大1*2^30
static final int MAXIMUM_CAPACITY =1 <<30;
// 负载因子，调控哈希冲突率的因子，默认=0.75
static final float DEFAULT_LOAD_FACTOR =0.75f;
// 单个桶上的链表元素到达8个时才会被树化：
static final int TREEIFY_THRESHOLD =8;
// 当进行resize，红黑树上的元素小于等于6个时，会变成链表：
static final int UNTREEIFY_THRESHOLD =6;
// 如果全表没有达到容量64，那么链表就不会被转成树，只会执行resize进行扩容：
static final int MIN_TREEIFY_CAPACITY =64;
一些变量：
// Set数组，用于迭代元素
transient Set<Map.Entry<K,V>> entrySet;
// HashMap元素总个数：map.size()
// 注：size是整个map的元素个数，并不是hash table的长度，因为table的单个元素可能还包含链表或红黑树。
// hash table的长度，我们一般用capacity表示：
transient int size;
transient int modCount;
// 进行resize的阈值，当实际大小 > table容量*负载因子：
int threshold;
// ***重要*** 负载因子: 默认0.75F：
final float loadFactor;
内部结构：
// ***重要*** 单个节点的对象：
// next节点很有灵性：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// ***重要*** 哈希表，相当于上图左边的桶状数组：
// 注：是transient，即在序列化的时候这个参数则不会被序列化。
transient Node<K,V>[] table;
// 红黑树:
static final class TreeNode<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
重要方法解析：
- hash(Object key)
- V get(Object key)
- V put(K key, V value)
- Node<K,V>[] resize()
一. 先来看hash(Object key)：
// >>>右移符，右移1位相当于除以2.
// 可以看出hash算法跟对象的hashCode()方法有关，这个方法在object类中就有，当然也可以重写之。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
由此可以看出：
- HashMap可以有null的key，null key的hash统一为0
- map的key，需要的是有一个稳定的hashcode方法，即每次返回的都一样，如要用一个对象，那么在对象set前后的hashcode就不一样啦，这样会导致put进去的值，无法get出来。
二. get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
如果是没有找到Node，则直接返回value = null.
下面详细看方法Node<K,V> getNode(int hash, Object key):
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 根据table的长度-1与hash(key)作&运算，算出目标桶的位置，记为first：
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// case-1：直接检查桶上当前的Node：
// 怎样才算是同一个key: 首先hash要相同，并且k == key也就是同一个对象或者k.equals(key)，如果满足则认为找到了目标Node：
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// case-2：如果桶里的Node是一颗红黑树，那么走树的Get方法：
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 如果是链表，则轮循列表中的Node，找到hash一样的，并且k == key或k.equals(key)，那么就返回匹配的Node.value：
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果table为null或table length==0， 或者计算出位置i后，目标桶Node为空，返回value = null
return null;
}
相当于hashcode是用于定位的（定位到具体的桶），而equals是用来找到正确的Node。
-
红黑树是一种自平衡二叉查找树（BBST家族的一员，Balanced Binary Search Tree），关键词：二叉搜索树、自平衡。
它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找。 - 若为链表，则在链表中通过key.equals(k)查找，O(n)。
介绍红黑树
(1) 红黑树的结构介绍：
首先统一增设外部节点NULL，使之成为真二叉树，再给出定义：
a. 树根是且必须是黑色
b. 外部节点：均为黑色
c. 其余节点：若为红，则只能是黑孩子，即红色的节点孩子和父亲都为黑
d. 外部节点到根：途中黑节点数目相等（黑深度）。
(2) 为什么不一开始就全部使用红黑树，而是在链表元素达到8的时候才树化？
红黑树的插入的复杂度是O(1)，但是如有必要需做双红修正，重染色的过程，复杂度可以会高达O(log n)。虽然红黑树各方面都优于单链，但值得注意的是，红黑树的空间复杂度要比单链高，即需要更多的空间。
链表的实现中，主要的变量有：
-- K key
-- V value
-- Node<K, V> next
而红黑树的主要变量有:
-- TreeNode<K, V> parent;
-- TreeNode<K, V> left;
-- TreeNode<K, V> right;
-- TreeNode<K, V> prev;
-- boolean red;
-- K key
-- V value
-- Node<K, V> next
我想在发生hash冲突时，8个元素以内选用实现更为简单的链表，应该是时间和空间的权衡。
(3) 为什么不使用同为BBST家族的AVL树（即自平衡二叉查找树）呢？
AVL发明于1962年，红黑树发明于1972年（别称：二叉B树）。
从结构出发，红黑树的任何一次动态操作（新增或删除）引发的结构变化量不超过O(1)，而AVL树新增引发的结构变化是O(1)，删除引发的结构变化(需自平衡)是O(Log n).
为什么要自平衡？
我的理解是一棵BST（二叉查找树）在极端情况下可能会退化为一条单链，所以包括AVL、红黑树在内的各种BBST都分别精心地定义了某种适度平衡的准则：当某次操作（新增或删除）使得BBST变成了BST，都会经过一系列巧妙的等价变成，使之重析成为BBST。
(4) 树相关的学习
可以去学堂在线学习清华大学邓俊辉的《数据结构》，计的非常好。
三. put(K, V)，主要是调用以下方法：
put方法有返回值，返回的是被覆盖掉的元素的value：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// case-1: new HashMap的时候并没有初始化table，在这里初始化：
// 用了resize()方法来初始化，resize()方法下面会有详说，这里就是会create一个初始length=16的Node<K,V>[] table:
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// case-2: 根据当前key计算出来的hash值，再计算出要put的table的位置，如果目标桶为null，可以看上图数据结构的桶(0)的情况，那么就直接new Node，传入当前的key, value：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// case-3: 当前桶已经有值了，即遇到了hash值一样的情况了：
// 需要明确 Node<K,V> p是当前桶这个位置上的现在的值（即：treeNode/node list：
// *** 重要 *** 这里有个新的node，叫e，e的妙用就是put方法需要返回的旧值：
Node<K,V> e; K k;
// case 3-1: 当前桶满足被覆盖的条件：当前桶位置p的hash和要插入key的hash相同，并且key就是同一个对象或equals方法相同：
// 目标当然是p需要被覆盖，因为put方法返回原来的value，所以我们用e先存下原来的p的值：
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// case 3-2: 当前桶里的节点是一颗红黑树，那么就把新的节点插入红黑树中，即上图数据结构桶(4)的情况，同样返回的e是有被覆盖情况时的元素（可能为Null,也可能真的有值）：
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// case 3-3：它是一个链表，即上图数据结构桶(2)的情况：
else {
for (int binCount = 0; ; ++binCount) {
// 遍历链表，在if里赋值e = p.next，即使没有满足if条件，也会使赋值生效，这里配合下面的p = e使用，相当于在逐个轮循这个链表：
// case 3-3-a：如果碰到最后一个节点了，那么就往最后一个节点插入新的Node并退出循环：
// 这时候还要判断是否需要树化（树化的条件是算上将要插入的那个元素），链表长度大于等于TREEIFY_THRESHOLD，即8个：
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// case 3-3-b：如果遍历链表的时候遇到元素key的hash值跟我们想要插入的key的hash相等，并且key equals也相等，那么就退出循环，这个时候的e就是匹配到的需要被覆盖的元素：
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 为了轮循链表，配合上述的for循环使用，for循环最终肯定会止步于上述两个break之一：
p = e;
}
}
// 如果e不为空，即原来的元素需要被覆盖，那么会先用oldValue记录下原来的值，再把新的value赋给e，并返回oldValue：
// 因为这种case对size没有造成影响，直接return即可，也就不需要执行下面的resize()：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// size = size + 1：
// *** 重要 *** resize的条件：threshold = capacity * 负载因子(即0.75）：
if (++size > threshold)
resize();
// afterNodeInsertion是一个空方法，如果我们新写一个map，继承HashMap，就可以重写这个方法，这时候afterNodeInsertion就会调用子类（即我们写的那个map），这是一种常见的设计模式，详见HashMap子类LinkedHashMap就有重写哦：
afterNodeInsertion(evict);
return null;
}
put(K, V)方法写了很多，总结起来就是：
- table为空，--> 触发resize()：初始化之（默认capacity = 16）
- 通过hash算法，找到在table中的位置i
- 如果table[i]目标位为null，那么就将新的Node<K, V>插入；
- 如果table[i]目标位已经有Node，则需要判断：
- 如果Node与K的hash相同并且（Node.K == K || Node.K.equals(K))，则覆盖之
- 如果Node是红黑树，则按树的方法插入<K,V>，见方法putTreeVal()
- 如果是多个Node（即组成了链表），则轮询Node，逐一比对K是否一样（这里的一样的条件和#5相同）：
- 如果遇到可以覆盖的Node，覆盖之，并返回旧的value；方法结束；
- 如果没有都不相同，则在链表最后插入<K,V>，并判断是否需要树化treeifyBin() （树化的条件是单链个数>=8；）; 最后还要size = size+1，并判断是否需要resize() （resize的条件是new size > threshold， threshold = table capacity * 负载因子(0.75），比如一个新的HashMap, 我们在put第13个元素的时候，就会触发resize()，扩容一般是原来的一倍。
四. Node<K,V>[] resize()：扩容方法：
根据putVal()方法可知，当table需要初始化或者new size > 阀值(table capacity * 0.75) 时，就会触发扩容方法。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// case-1: 扩容前的table有长度（即不是初始化case）：
if (oldCap > 0) {
// case 1-1: 已经是最大长度了（2的30次方），扩无可扩：
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// case 1-2: 赋值新的capacity = 原来的capacity的两倍(位运算符，左移1位=2倍）
// 如果新的capacity没有到达最大容量值并且达到了最小容量16，那么新的阀值threshold也是原来的2倍：
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// case-2: 如果在new HashMap的时候指定了capacity，那么threshold就不是0，而会通过tableSizeFor(initialCapacity)计算出来，即满足oldThr > 0：
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// case-3: 初始化table，capacity=16，阀值threshold=16*0.75
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//---------------------------------------
// 针对new threshold还没有扩容的情况，new threshold=new capacity * loadFactor:
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//---------------------------------------
// 解决了new capacity和new threshold后，下面开始对table的值进行转移：
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 扩容其实就是生成一个新的table, capacity是原来的两倍：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 轮循table的桶：
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 赋值e=该桶的值，如果不为空：
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// case-i：如果当前桶只有一个node（即e.next为空），那么就重新算位置即可，targe位置i的算法和putVal一样：
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// case-ii：如果当前是颗树，那么走split方法：
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// case-iii：如果当前是多个Node的链表，这里挺有意思的：
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 首先用了do {} while来轮循这个列表，用了一个位运算符，如果e.hash & oldCap == 0，那么就用原来的位置；否则就用新的位置：j + oldCap。我个人理解这里是确保resize后（长度扩两倍），值不至于全在上半段，也要分一部分给扩充的下半段：
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;
}
补充理解链表，假如原来的容易是16，在位置5上有链表：a->b->c->d->e，那么通过&运算，结果可能分为两个链，即链(1) a->c->d; 链(2) b->e
那么，上面的e, next就是e会依次等于a, b, c, d, e：
而Node<K,V> loHead = a, loTail = d;
Node<K,V> hiHead = b, hiTail = e;
新的列表位置5会是：a->c->d
新的列表位置5+16=21会是：b->e
我的理解是扩容为原先的两倍，在分配原先的数据时，用位运算（与）的效率比较高，元素要么落回原来的位置，要么落原来的位置+oldCap，计算起来很简单。（若是扩容是原先的1.5位，那么就很难按上述方法计算了。）
针对树的split(HashMap<K,V> map, Node<K,V>[] newTab, int j, int oldCap)方法，轮循树的元素，算法基本和上述链表一致，需要注意的是如果当前树的元素过少（小于等于 UNTREEIFY_THRESHOLD，即6时)，会使树转为链表：untreeify(map);
关于resize()，在jdk 1.8中改进了不少，最主要的是之前的版本如果多线程来访问会造成死锁。详细戳：https://www.cnblogs.com/wang-meng/p/7582532.html
总结了下上述提到的方法：
方法关系图
参考：哈希表：百度百科
红黑树：https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91/2413209?fr=aladdin
HashMap面试相关，戳：https://www.cnblogs.com/flyuz/p/11378491.html
网友评论