一、前言
在jdk1.8以前，HashMap采用数组+链表实现，采用拉链法来解决hash冲突，即创建一个链表数组，数组中每一格就是一个链表，遇到hash冲突直接将冲突的值塞进链表里即可，这样同一hash值的都存储在一个链表里。
这么做有个缺点就是如果同一hash值元素较多时，查找效率低下。在jdk1.8中为了解决hash冲突频繁的问题，HashMap采用了数组+链表+红黑树实现，当链表的长度超过阈值（8）时，将链表（查询复杂度ON）转换为红黑树（OlogN），极大地提升了查询效率。
jdk1.8还解决了多线程死循环的问题。不过HashMap仍然是非线程安全的，多线程可能会造成数据丢失问题。
二、对比jdk1.7与jdk1.8的HashMap
| jdk1.7 | jdk1.8以后 | |
|---|---|---|
| 存储结构 | 数组+链表 | 数组 + 链表 + 红黑树 |
| 初始化方式 | 是一个单独函数：inflateTable() | 直接集成到了扩容函数resize()中 |
| hash值计算方式 | 9次hash方法处理：4次位运算 + 5次异或运算 | 2次hash方法处理：1次位运算 + 1次异或运算 |
| 存放数据规则 | 无冲突时，存放数组；冲突时，转换为链表 | 无冲突时，存放数组；冲突且链表长度 < 8时，存放单链表；冲突且链表长度 > 8：树化并存放红黑树 |
| 插入数据方式 | 头插法，先将原位置的数据移到后1位，再插入数据到该位置 | 尾插法（直接插入到链表尾部/红黑树） |
| 扩容后存储位置的计算方式 | 全部进行hash方法处理 | 按照扩容后的规律计算（扩容后的位置=原位置 or 原位置 + 旧容量） |
三、源码阅读部分
1.声明
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
//Cloneable、Serializable为空接口，只是表明HashMap是支持克隆和序列化的
2.成员变量
//默认初始化数组容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大的数组容量，2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子0.75，即一旦过了容量0.75倍就开始扩容
//使用0.75的原因是空间利用率比较高，避免了相当多的hash冲突，使得底层的链表或者红黑树的高度比较低，提升了空间效率
//如果使用1，则意味着只有table填满才进行扩容，这样就会有大量的hash冲突，导致底层红黑树变得十分复杂，降低了查询效率。就是牺牲时间来换空间
//如果使用0.5，则是table里元素到达一半就扩容，这样底层的链表长度或者红黑树高度就会减小，查询效率增加。可是这样空间利用率就降低了，牺牲空间换时间
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//由链表转红黑树的临界值
//至于为什么是8这个值，源码也说了，大概意思就是根据概率学泊松分布，当链表的长度等于8的概率已经特别特别小了，所以就以8为基准。
static final int TREEIFY_THRESHOLD = 8;
//由红黑树转链表的临界值
static final int UNTREEIFY_THRESHOLD = 6;
//table转换为树形结构的最小容量，如果table小于这个值，是不会出现红黑树的
static final int MIN_TREEIFY_CAPACITY = 64;
//表数据，即Node键值对数组，Node是单向链表，实现了Map.Entry接口，是2的幂次倍
transient Node<K,V>[] table;
//存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;
//map中包含键值对的数量
transient int size;
//HashMap结构修改的次数
transient int modCount;
//Node数组的下一次扩容的临界值，第一次为16*0.75=12
//The next size value at which to resize (capacity * load factor) 0.75 * 最大容量 即阈值
int threshold;
//加载因子
final float loadFactor;
3.静态类
前面提到的Node<K, V>，是HashMap的内部类，实现了Map.Entry<K, V>接口。HashMap的table数组中存放的键值对对象就是Node<K, V>
static class Node<K,V> implements Map.Entry<K,V> {
//hash值，根据该值确定记录位置
final int hash;
//node的key
final K key;
//node的value
V value;
//指向链表中的下一个元素，当链表中的元素超过TREEIFY_THRESHOLD（默认是8）时，将链表转换为红黑树。
//此时该下标的元素将成为TreeNode<K, V>（红黑树结点）
//该结点继承与LinkedHashMap.Entry<K, V>，而LinkedHashMap.Entry<K, V>又是Node<K, V>的子类。
//综上HashMap底层数组元素的类型是Node<K, V>
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//返回node里的键
public final K getKey() { return key; }
//返回node里的值
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//计算hashCode的方法，是key的hashCode与value的hashCode方法进行异或运算
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断两个entry是否相等，必须key和value相等才返回true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
//双重判断
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
前面提到的TreeNode<K, V> 的部分源码：
//红黑树的实现类，继承自LinkedHashMap.Entry<K,V>
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(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回当前结点的根结点
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
4.核心方法
hash()算法：
//先取出对象的hashCode值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode进行异或运算，返回结果。
//如果key为null直接返回0
//通过key的hashCode的高16位异或或者低16位来实现的(h = key.hashCode()) ^ (h >>> 16)
//这么做的好处就是在table数组的length比较小的时候也能保证考虑到高低bit都参与到Hash的计算中，同时减少开销
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在这里讲一下计算下标，在putVal方法有这么一段代码：
if ((p = tab[i = (n - 1) & hash]) == null) //获取位置
tab[i] = newNode(hash, key, value, null);
tab就是table数组，n就是table数组的容量，始终为2的幂次，hash是上面方法的返回值。通过(n – 1) & hash来获取该对象的key在table的位置。为了效率，HashMap采用了(n – 1) & hash，它与hash % n等价，而与运算的效率是大于求模运算的。
计算下标的过程如下：
假设n是16
假入h = hashCode() ： 1111 1111 1111 1111 1111 0000 1110 1010
即 h ： 1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16 ： 0000 0000 0000 0000 1111 1111 1111 1111
hash = h ^ (h >>> 16) ：1111 1111 1111 1111 0000 1111 0001 0101
(n - 1) & hash ： 0000 0000 0000 0000 0000 0000 0000 1111
1111 1111 1111 1111 0000 1111 0001 0101
0000 0000 0000 0000 0000 0000 0000 0101
得出下标为0101 也就是5
总结：
- 1.HashMap采用了链地址法来链接拥有相同hash值的数据
- 2.使用了2次hash函数来降低hash冲突的概率，使得数据分布的更平均
引申问题：为什么不直接使用hashCode处理后的值作为table下标？
答：这个问题其实挺简单的的，hashCode的取值范围是-2147483648到2147483647，约有40亿个映射空间，而HashMap则是默认16到2^30，HashMap一般是取不到那么大的，所以直接计算就会有很多问题。
将元素放进table里面
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//判断table是否已经初始化
if (table == null) { // pre-size
//如果没有，s就为m的实际个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果t大于阈值，则将阈值赋为大于t的最小二次幂
if (t > threshold)
threshold = tableSizeFor(t);
}
//已经初始化，并且s大于阈值，则进行扩容
else if (s > threshold)
resize();
//将map中的所有元素加入到table中
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);
}
}
}
put方法，重点：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用的putVal：
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)
//resize()：扩容
n = (tab = resize()).length;
//步骤二：计算index，看是否是null，如果当前没有可以直接放，(n - 1) & hash 判断放在table的哪个桶中
//当前新生成的结点实现放在数组中的
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，用e来记录
e = p;
//如果key不重复，判断是否得启动红黑树，如果是的话，则putTreeVal方法返回待存放的node，ps：e可能为null
else if (p instanceof TreeNode)
//将这个元素的信息放入红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//这样就能加入进链表了
else {
//这个binCount用于判断当前的结点长度
for (int binCount = 0; ; ++binCount) {
//这个判断就是判断是否到了链表的最后一位
if ((e = p.next) == null) {
//在链表的最末尾插入结点
p.next = newNode(hash, key, value, null);
//判断是否到达了链表的临界值8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//将链表结构转换为树
treeifyBin(tab, hash);
break;
}
//判断链表中的key是否与新插入的相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果相等直接跳循环
break;
//用于遍历桶中的链表，与前面的e = p.next组合遍历链表
p = e;
}
}
//如果当前key已经存在，又来了一个相同的hash值和key值的，返回新来的
if (e != null) { // existing mapping for key
//保存旧的value
V oldValue = e.value;
//进行覆盖操作，条件是onlyIfAbsent为false或者oldValue为null
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//操作数加一，因为结构性修改了
++modCount;
//如果加入元素后的容量大于阈值就进行扩容
if (++size > threshold)
resize();
//回调函数
afterNodeInsertion(evict);
return null;
}
总结一下：
- 1.在进行put操作的时候，首先判断键值对数组table长度是否为0或为null，如果是就进行第一次扩容
- 2.根据key的hashCode与自身右移16位异或操作后在进行一波 (n – 1) & 这个值 来计算出要在table插入的位置
- 3.如果当前位置没有元素，那就直接塞进table数组该位置即可，然后结束
- 4.如果当前位置有元素，则进行一波判断操作：如果key一样，直接后面的覆盖掉前面的，如果key不一样的话就开始进行下面的判断
- 5.判断这个位置是否已经红黑树了，如果是就直接给红黑树里面插结点
- 6.如果不是红黑树，也就是链表，要进行尾插，先判断链表长度是否大于8，并且数组长度大于64，满足就转红黑树。如果在遍历链表的过程中发现了key相等的情况直接覆盖value
- 7.插入成功后，判断实际存在的table数组的size是否超过了阈值threshold，如果超过进行扩容操作
resize() 扩容方法：
final Node<K,V>[] resize() {
//申明一个oldTab指向table数组，进行操作
Node<K,V>[] oldTab = table;
//旧容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的阈值
int oldThr = threshold;
//新容量和新的阈值
int newCap, newThr = 0;
//如果table数组不为空
if (oldCap > 0) {
//如果旧的容量已经大于最大HashMap容量1<<30，将阈值赋为2147483647，因为map是2的幂次方形式扩展的
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果当前table的长度在扩容后小于最大容量且最大容量大于16，新的阈值就是旧的阈值*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//旧容量小于等于0，但是threshold大于零，代表是有参构造传入，threshold已经被初始化为最小2的n次幂，则直接将该值赋给新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//否则则是无参构造，则新的容量就是默认容量16，阈值就是16*0.75 = 12
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新阈值为0，则表明是有参传入，且此时的旧阈值等于大于参数的最小二次幂，则让新阈值等于新的容量*0.75
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"})
//将当前的newTable 赋给 table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果原本的oldTable不是null开始执行下面
if (oldTab != null) {
//遍历旧数组的所有下标
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//将旧数组的所有元素赋给临时变量e，并且释放原数组中的引用null，这样可以保证数组被GC回收
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果e.next == null 表明table中就一个元素，不存在链表或者红黑树
if (e.next == null)
//用hash映射算法把这个元素加入新的table里
newTab[e.hash & (newCap - 1)] = e;
//如果e是红黑树的结点，并且e.next不是null，则得处理树的重排
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//否则e是链表的头且e.next不是null
else { // preserve order
//loHead，loTail代表扩容后不用变换下标
Node<K,V> loHead = null, loTail = null;
//hiHead，hiTail代表扩容后要变换下标
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历链表
do {
next = e.next;
//如果e的hash经过和旧用来与运算后 == 0，即都不一样，就是老值链表
if ((e.hash & oldCap) == 0) {
//初始化head指向链表的当前元素e，e不一定是链表的最后一个元素，loHead代表下标保持不变的链表的头元素
if (loTail == null)
loHead = e;
else
//如果loTail不是null，则loTail的下一个元素就是e，尾插法
loTail.next = e;
//让loTail指向当前元素e，使得lowHead可以连接到所有属于该链表的元素，避免了循环
loTail = e;
}
else {
//分析过程与前面差不多，新值链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//遍历结束，如果loTail.next不是null，则赋为null。并把新的链表头放入新table的下标。
if (loTail != null) {
loTail.next = null;
//这是不改变下标的
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//我们看出，改变下标的直接就是当前元素加上原本的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容方法小结：
- 1.HashMap中的键值对大于阈值或者初始化的时候，调用此resize方法进行扩容
- 2.每次扩展的时候，都是原来的二倍，初始化默认容量为16
- 3.扩展后table中的node对象要么在原位置，要么移动到原偏移量两倍的位置。即如果当前是1，移动一次就是17
- 4.在进行链表插入的时候，jdk7用的是头插法直接赋值，而jdk8用的是尾插法，先循环再赋值（do while）。这么做避免了链表带环死循环的问题
treeifyBin()方法，即树化方法：
当链表长度binCount大于等于TREEIFY_THRESHOLD（8）且table容量大于64的时候，执行该方法就开始将链表转换为红黑树。这也就是说，不一定链表长度等于8就立刻扩容，而是先判断是否容量到达64。至于为什么是8这个值，参考源码，大概意思就是根据概率学泊松分布，当链表的长度等于8的概率已经特别特别小了，所以就以8为基准。树形化的时候，先去遍历链表中的所有元素，并创建对应的树结点，最后判断table的当前位置如果有树形结点，对其进行转换为红黑树的操作。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
////如果table没有初始化，或者table长度小于MIN_TREEIFY_CAPACITY 64时，进行扩容而不是树形化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//开始树形化，先判断是否该index有链表
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd：头结点，tl：尾结点
TreeNode<K,V> hd = null, tl = null;
//该循环是将原单向链表转换为双向链表
do {
//将每个链表结点转换为树的结点，其中链表的头结点就是树的头结点
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果尾结点为null则表明首次循环，此时e为头结点、p为根结点，因此将p赋给表示头结点的hd
if (tl == null)
hd = p;
else { //树的根结点已经产生了，则t1尾结点指向上次循环创建的树形结点。此时tl与p的关系是前后
//产生当前结点与前驱结点之间的链
p.prev = tl;
//产生前驱结点和当前结点之间的链
tl.next = p;
}
//将tl指向当前结点
tl = p;
} while ((e = e.next) != null);
//如果当前table位置有树形结点，进行树形化
if ((tab[index] = hd) != null)
//根据链表创建红黑树结构
hd.treeify(tab);
}
}
get()方法，根据key取value
get方法执行的时候，首先进行判断：table已经初始化，table长度大于0，第一个元素非空。都符合则先看第一个元素是否符合要求（hash相等，key为一个对象），符合直接返回。否则的话就对后面的元素进行判断，如果为红黑树则调用对应方法在红黑树中找，链表的话则挨个遍历查找。
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;
//table已经初始化，长度大于0，且当前位置有元素。ps：直接通过hash就定位了table中的位置
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;
}
remove()方法，根据key删除key-value对
HashMap中删除指定key对应的键值对，并返回被删除的键值对的值，如果返回空，说明key不存在或该key对应的值为null，如果想确认key是否存在使用containsKey方法。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
调用的removeNode方法：
/**
* Implements Map.remove and related methods.
*
* @param hash 要删除的key的hash值
* @param key 要删除的key值
* @param value 要删除的key对应的value，该值作为删除的条件取决于matchValu是否为true
* @param matchValue 如果true则key对应的值.equals(value)为true才删除，否则不关心value的值
* @param movable 删除候是否移动结点，如果为false则不移动
* @return 返回被删除的对象，没有删除任何结点返回null
*/
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;
//如果table不为空，数组长度大于0，根据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相等），复制给node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//否则表明，首结点并没有匹配到。如果p.next为空，直接返回null即可，就一个结点还匹配不到
else if ((e = p.next) != null) {
//判断是否为树结点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//为链表结点
else {
do {
//如果找到了就把当前结点赋给node，然后break
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
//说明当前的e并不是我们要删除的，则让p存的是下一次循环里e的父结点，如果e匹配到了表明p是e的父结点
p = e;
} while ((e = e.next) != null);
}
}
//如果node不为空，说明匹配到了。如果是直接不需要对比value的值，或者需要对比value的值但是value的值也相等
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);
//否则node为首结点，直接让该table的这个值等于node的下一位就行
else if (node == p)
tab[index] = node.next;
//否则，node不是首结点，而是node的父结点，则链表删除
else
p.next = node.next;
//操作数加一，元素个数减少
++modCount;
--size;
//无任何逻辑，就是让子类进行重写的
afterNodeRemoval(node);
return node;
}
}
return null;
}
这篇文章是本人的一些拙见，如果有误，还请各位大牛在评论区指出，也欢迎大家一起交流，十分感谢！