1、继承体系
HashMap实现了Map接口，以KEY-VALUE的形式存储键值。JDK8中，HashMap采用的是数组+链表+红黑树的数据结构
2、底层结构
1、基本变量
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//默认数组的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子，与扩容有关系
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表结构转换成红黑树结构的阈值，链表中的节点必须大于8个
//如果链表中节点个数大于8个但数组大小不超过64，会触发数组扩容，而不是链表转红黑树
static final int TREEIFY_THRESHOLD = 8;
//红黑树转换成链表的阈值，红黑树中节点个数要小于等于6个才会转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
//转换成红黑树时数组大小必须大于64
static final int MIN_TREEIFY_CAPACITY = 64;
//实际存放元素的数组
transient Node<K,V>[] table;
//集合中元素的数量
transient int size;
//集合的修改次数
transient int modCount;
//阈值，扩容时使用
int threshold;
//负载因子，和当前数组的大小结合，计算出阈值的大小
final float loadFactor;
}
HashMap中的成员变量比较多，需要重点关注的是当前数组的大小以及负载因子loadFactor，这两个因素左右着是否进行扩容
在HashMap中，如果 当前数组的大小 * loadFactor < size 时，或者第一次添加元素时，都会进行扩容操作
2、Node
static class Node<K,V> implements Map.Entry<K,V> {
//当前node的hash值
final int hash;
final K key;
V value;
//下一节点
Node<K,V> next;
}
该结构由链表组成，HashMap底层有一个Node数组，当发生hash冲突时，会将元素通过尾插法插入链表中。从上面成员变量可以看出Node是一个单向链表
3、TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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;
]
TreeNode是红黑树节点，它直接继承了LinkedHashMap.Entry，而LinkedHashMap.Entry继承自HashMap.Node，
LinkedHashMap.Entry扩充了before、after节点，是一个双向链表
3、构造函数
//空构造函数，负载因子为默认的0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定初始化容量的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指定初始化容量和负载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//若初始化的容量大于MAXIMUM_CAPACITY（1 << 30），直接使用MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置阈值，根据传入的容量大小转换成最近的2的幂次方，同时也是数组的初始化容量大小，在下面的resize方法
//的分析中可以看到
this.threshold = tableSizeFor(initialCapacity);
}
HashMap构造方法中，容量和负载因子是很重要的两个参数，这两个值与HashMap是否扩容息息相关。在这里总结一下面试常问的几个问题
1、默认的负载因子为什么是0.75？
- 首先threshold = 数组大小 * 负载因子，而当前集合中元素个数大于threshold时，HashMap就会进行扩容
- 因此，负载因子太大，HashMap扩容的频率就会降低，产生Hash碰撞的频率就会增大，查询效率就会降低；负载因子太小，HashMap就会频繁扩容，插入的效率就会降低。
- 所以，需要合适的负载因子，来对查询和插入进行平衡，而0.75则是在时间和空间上的进行平衡取得的结果
2、HashMap中为什么数组大小总是2的幂次方？
- 简单来说，就是为了提升效率
- 通常，计算元素在数组中的下标时，采用取模的方式，即hash(key)%数组大小计算数组下标，而当数组大小始终保持在2的幂次方时，可以采用位运算的方式，提高效率
- HashMap中使用的方式是
(n - 1) & hash方式计算下标，即数组大小 - 1再与key的hash值取模，n-1可以使值的二进制都为1，比如n为16的话，n-1后的二进制则为1111，再进行&运算的话，由于每一位都是1，那么结果只和key的hash值有关。这样，只要hash函数设计的好的话，产生碰撞的概率就会大大降低，同时位运算比取模运算要快
4、添加元素
平常使用HashMap添加元素时，大都以put方法以起点
public V put(K key, V value)
return putVal(hash(key), key, value, false, true);
}
put方法实际调用了内部的putVal方法，这里会先对key进行hash运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 当key为null时，直接返回0
- 当key不为null时，计算key的hashcode值，并同时与h的高16位进行
^操作
为什么是key的高16位进行^操作呢？
- 高16位进行异或操作，可以同时让高16位和低16位参与运算，计算出的hash值更加可靠，发生碰撞的概率更小
putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab指向当前数组的引用；n是数组的大小，i是数组索引下标，p是数组索引下标为i的node节点值
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab为null或者长度为0，说明是第一次添加元素，需要进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算出的下标i位置为null，说明该位置还没有元素，则可以直接在该位置上创建Node节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//p的值不为null，说明发生hash碰撞
Node<K,V> e; K k;
//如果说hash相同并且key相同，说明key是相同的，这时只要用新值覆盖旧值就可以了
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) {
//e为null，说明到了链表的尾部，且没有相同的key
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//链表节点个数大于等于8个时，尝试转换为红黑树节点
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;//break说明当前节点的k和传入的key相同，新值覆盖旧值即可
p = e;
}
}
if (e != null) {
//e不为null说明存在相同的key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//集合修改次数加一
++modCount;
if (++size > threshold)
//元素个数大于阈值，需要扩容
resize();
//LinkedHashMap使用了该方法
afterNodeInsertion(evict);
return null;
}
putVal方法是真正核心方法，大致的过程如下
- 第一次添加元素，首先进行初始化，即扩容
- 计算数组下标，获取数组值，如果为null，说明第一次在该位置添加元素，直接创建新的
Node节点。 不为null，说明发生了哈希碰撞，需要根据节点类型进行不同操作 - 头结点的k与传入的key相同，直接用新值覆盖旧值，并返回旧值
- 如果当前节点是链表节点，并且没有链表中没有相同的key，使用尾插法添加新元素，并且链表元素个数大于等于8个后，会转换为红黑树节点；如果链表中有相同的key，直接用新值覆盖旧值，并返回旧值
- 如果当前节点是红黑树节点，使用红黑树的方法新增节点
- 判断是否需要扩容，元素总个数超过阈值，进行扩容
红黑树添加节点值
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//找红黑树根节点，从根节点开始进行插入值操作
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
//dir表示向左节点查找还是右节点查找；ph代表当前红黑树节点的哈希值；pk表示当前红黑树节点key值
int dir, ph; K pk;
if ((ph = p.hash) > h)
//ph>h，说明要插入的节点hash值比当前红黑树hash值小，因此继续向左子节点查询
dir = -1;
else if (ph < h)
//向右子节点查询
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//节点k和插入k相同，直接返回当前红黑树节点的引用
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//若是实现了Comparable接口，则用自定义的方法进行比较
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
//先保存p节点的引用，添加新节点时会用到
TreeNode<K,V> xp = p;
//根据dir的值决定是左子节还是右子节点
//注意，如果左子节点和右子节点都不为null，则会继续进行for循环查找
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//进入if说明左子节点或者右子节点为null，找到了可以插入新节点的地方
//xp的next节点
Node<K,V> xpn = xp.next;
//构造新的节点，同时使x的next引用指向xpn
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
//小于等于0，说明左子节点为null，则将xp的左子节点引用指向x
xp.left = x;
else
//否则，则将xp的右子节点引用指向x
xp.right = x;
//xp的next节点指向x
xp.next = x;
//x的父节点和prev节点均指向xp
x.parent = x.prev = xp;
if (xpn != null)
//将xpn的prev节点指向x，prev和next主要是维护链表结构
((TreeNode<K,V>)xpn).prev = x;
//插入后可能需要旋转变色重新平衡红黑树，旋转后根节点可能变化，所以调整节点到最前面
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
只要理解二叉搜索树的查找，红黑树的查找也就很容易理解。要了解的是，TreeNode节点不仅维护红黑树，还维护着双向链表，所以才会有最后next节点和prev节点的操作。总结一下整个流程的话
- 不断在红黑树中查找，若节点已经存在于红黑树中，直接返回当前节点的引用。否则，找到需要插入的具体位置
- 创建新节点，并建立父子关系。同时维护双向链表的关系
- 旋转、变色，并将新的根节点转移到最前面
旋转变色就不分析了，具体可以去谷歌搜索具体的分析文章。
再看下moveRootToFront方法
//root参数是旋转后新的根节点
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//计算新的root节点的下标
int index = (n - 1) & root.hash;
//取出当前下标处的节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
//不相同，说明根节点需要改变
//rn节点代表根节点的next节点，rp代表根节点的prev节点，取出来是为了将root节点放在
//链表的最开头，并让rp和rn相互引用重新构建链表关系
Node<K,V> rn;
//将新的root节点放在数组上
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
//让rn的prev节点指向rp
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
//rp的next节点指向rn
rp.next = rn;
if (first != null)
//将first也就是当前链表头节点的prev指向root，这样first就不再是链表头结点
first.prev = root;
//root的next指向first
root.next = first;
//root的prev为null，链表头节点构造完毕
root.prev = null;
}
assert checkInvariants(root);
}
}
这个方法做了两件事情
- 将新的root节点放在数组上
- 重新构建链表的关系
链表树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// !!!当数组为null或者数组大小 < 64时，进行扩容。并非链表节点个数大于8就一定会转换为红黑树
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//转换红黑树前，依旧保持链表的结构。hd表示链表头节点，tl表示链表尾结点
TreeNode<K,V> hd = null, tl = null;
do {
//创建TreeNode节点
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);
if ((tab[index] = hd) != null)
//构造红黑树关系
hd.treeify(tab);
}
}
//treeify本质上和putTreeVal方法的思想是相同的，不再细展开，仅贴出来一下
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
链表转换成红黑树的过程中，有一点需要注意，只有当链表个数大于8且数组大小大于64时，才会有红黑树的转换。
为什么链表转红黑树的阈值是8呢？
- 链表的查询时间复杂度是O(n)，红黑树的查询时间复杂度为O(log n)，当链表个数很小时，红黑树和链表实际相差无几。红黑树的空间占用是链表的2倍，只有数据较多时，使用红黑树才合理。而8这个值，参照了泊松分布，链表各长度实际命中率
- 0: 0.60653066
- 1: 0.30326533
- 2: 0.07581633
- 3: 0.01263606
- 4: 0.00157952
- 5: 0.00015795
- 6: 0.00001316
- 7: 0.00000094
- 8: 0.00000006
- 当链表长度达到8时，出现的概率为千万分之一。目的就是尽量不出现红黑树结构，若是出现了，也能保持较低的查询时间复杂度。正常来说，几乎不太可能看到hashmap中红黑树的结构。若是出现了，说明hash函数设计的有点糟糕。
5、扩容
HashMap的扩容分为2种，一种是初始化数组，另一种是扩容
final Node<K,V>[] resize() {
//获取旧数组
Node<K,V>[] oldTab = table;
//旧容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧阈值
int oldThr = threshold;
//新容量、新阈值都设置为0
int newCap, newThr = 0;
if (oldCap > 0) {
//oldCap>0说明非初始化数组，真正需要扩容
if (oldCap >= MAXIMUM_CAPACITY) {
//容量已达上限，无法再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
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
table = newTab;
//若是初始化，oldTab就是null，直接结束，返回新数组
if (oldTab != null) {
//扩容
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//当前数组槽点下有值，赋给e
if ((e = oldTab[j]) != null) {
//原数组位置置为null，帮助GC
oldTab[j] = null;
if (e.next == null)
//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
//走到这，说明是链表
//链表扩容，会将原链表分割成两个新链表，其中一个赋值新数组下标j处，另一个赋值到新数组j + oldCap处
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//如果e的hash值和原数组大小&后为0，加入到lo链表中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//加入到hi链表中
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//将lo链表赋值到新数组的下标j处
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将hi链表赋值到新数组的下标j + oldCap处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
整体分为两大步骤
- 计算新的数组容量和扩容阈值
- 初始化
- 指定容量，newCap=指定容量
- 未指定容量，newCap=16
- 扩容
- newCap=oldCap*2
- 初始化
- 扩容，遍历数组上的每个节点，分情况扩容
- 当前槽只有一个节点，直接根据新容量计算新下标
e.hash & (newCap - 1)，将节点赋值到新数组上 - 当前节点是红黑树节点，使用红黑树的方式扩容
- 当前节点是链表，将链表分割成两个新链表，分别赋值到新数组上
- 当前槽只有一个节点，直接根据新容量计算新下标
为什么链表扩容会分割成两个链表？
因为HashMap的容量始终是2的幂次方倍。举个例子
- 假设数组原大小为16，那么
oldCap=tab.length-1=15，转换为二进制为1111，那么扩容后新数组的容量大小的二进制为0001 1111 - 假设某个节点的计算hash后的值的二进制为
0101 0101，与1111进行&后值为0000 0101，与0001 1111进行&后值为0001 0101，正好差一个数组原大小即16 - 假设某个节点的计算hash后的值的二进制为
0100 0101，与1111进行&后值为0000 0101，与0001 1111进行&后值为0000 0101，新位置和旧位置相同 - 这里计算的结果的不同只与
tab.length-1的结果的二进制中的第5位（从右往左，从一开始计数）是否为1相关，而
0001 0000为16，正好是数组的原大小。所以，无论怎么计算，最终只会有两个不同的下标
6、查询
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
首先根据key计算hash，然后从getNode方法中查找数据。存在的话返回e的value值，不存在返回null
final Node<K,V> getNode(int hash, Object key) {
//tab数组，first当前槽的第一个节点，n数组大小
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))))
//hash相同并且key相同，说明是同一对象，返回节点
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;
}
查询较容易理解
- 当前槽的第一个节点就是要查询的节点，直接返回节点引用
- 当前节点是红黑树，使用红黑树的方法查找
- 当前节点是链表，从头到尾遍历，查询到就返回
- 没有查询到节点，返回null
红黑树查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
//向左查找
p = pl;
else if (ph < h)
//向右查找
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//k相同，说明是要查询的节点，返回
return p;
//走到这，说明当前节点的key的hash值和要查询的key的hash值相同，但却不是
else if (pl == null)
//pl为null，直接指定向右查找
p = pr;
else if (pr == null)
//pr为null，直接指定向左查找
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
//若是实现了Comparable接口，用自定义的方式比较大小，判断向左查询还是向右查询
p = (dir < 0) ? pl : pr;
//左右子节点都不空
else if ((q = pr.find(h, k, kc)) != null)
//直接向右递归查找，找的话返回q
return q;
else
//向左查询
p = pl;
} while (p != null);
return null;
}
红黑树查询就是比较要查询的key与当前节点key的hash以及key是否相同，不相同的话根据情况来决定向左还是向右，其中遇到hash相同但key不同的情况，会直接指定方向查询