JDK 1.8的HashMap与JDk1.7版本相比最大的区别是，为了避免哈希冲突，使用红黑树的数据结构代替了1.7版本中的单项链表，因为红黑树的插入。增加，删除操作的时间复杂度都为O(lg n)，在效率上查找起来要比链表的O(n)更快。我们可以将JDK1.8的HashMap理解为是链表、数组、红黑树的结合体
HashMap并不是只要hash冲突就直接以红黑树这种复杂的方式去储存冲突的节点，而是一开始使用链表的方式，当桶节点的数量大于8时，会从链表转化为红黑树的方式储存，当筒节点的数量小于6时，又会从红黑树退化为链表，当然前提是该桶是以红黑树储存的。
这里和Jdk1.7版本相比基本没有区别
static class Node<K,V> implements Map.Entry<K,V> {
//key的HashCode（此hashcode是通过hash方法扰乱后的结果）
final int hash;
//HashMap的键
final K key;
//HashMap的值
V value;
//下一个节点的引用
Node<K,V> next;
//4参数构造方法
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
TreeNode<K,V>类继承于LinkedHashMap.Entry<K,V>类
LinkedHashMap, Entry<K,V>又继承于HashMap.Node<K,V>l类
所以 TreeNode<K,V>类的构造方法中的本质上是调用了HashMap.Node<K,V>类的四参构造方法
//此类的一个对象就代表红黑树的一个节点
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;//节点的颜色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Node<K,V>，TreeNode<K,V>，再加上下面属性提到的table数组，就构成了HashMap的结构——哈希桶（也可以叫散列桶）
//序列号，用于序列化和反序列化操作
private static final long serialVersionUID = 362498820763181265L;
//默认的容量为16，具体为什么是16，这是通过大量计算得到的最优解，不必纠结，该容量必须是2的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
//HashMap的最大容量为1<<30,即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
*负载因子，是用来计算是否要进行扩容操作的阀值，
*比如HashMap的容量为16，阀值 = 16 * 0.75 = 12；
*也就是说当HashMap被使用12个元素空间时，就要进行扩容，以保证HashMap的效率
*有的人估计会纠结为什么是0.75，我在这里作一个简单的解释
*假设负载因子是1，HashMap的容量是16，那么随着HashMap中元素的增加，哈希冲突会越来越严重
*Jdk1.8中的解决冲突的数据结构是红黑树，大量的哈希冲突会导致红黑树高度会越来越高。大大减小了查询速率
*假设负载因子是0.5，也就是当HashMap的容量用到一半的时候，就进行的扩容，虽然这样可以减少红黑树的高度，提高查询效率
*但是以前需要1M的存储空间，现在就需要2M。换句话说就是，我们虽然获得了时间，但是我们牺牲了空间
*所以0.75是编辑HashMap的那些高手们中和时间与空间得到的一个比较合适的值
*
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/*
当桶的节点数大于为8时，将链表转化为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
当红黑树结构的节点数小于6时，节点退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/*
当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//储存Node数据结构的数据
transient Node<K,V>[] table;
/**
将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
*/
transient Set<Map.Entry<K,V>> entrySet;
//HashMap中的元素数量
transient int size;
//每次对HashMap的操作的会使modCount++；可以用来检查线程安全，官方称这种检查方式为fail-fast
transient int modCount;
//threshold为阈值，计算方法为threshold = initialCapacity * loadFactor；总体作用上方注释有说明
int threshold;
//负载因子
final float loadFactor;
双参构造中的tableSizeFor(initialCapacity);方法下面的内容会提到
/*
*双参构造方法
*initialCapacity，HashMap初始容量
*loadFactor负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//初始容量小于0，
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量大于最大容量，将初始容量赋值为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
/*
负载因子不可能小于零，也不能是NaN，读者可以自己输出一下System.out.println(0.0f/0.0f);
就可以知道NaN是什么了，实际上就是如果loadFactor是通过除法计算得来的，当分母为零时，计算的结果就是NaN
NaN的全称为Not a Number，显然是不能作为负载因子的
*/
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//JDK1.7版本直接将initialCapacity赋值给threshold
this.threshold = tableSizeFor(initialCapacity);
}
//初始化HashMap使用自己定义的初始容量，使用默认的负载因子0.75f
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无惨构造最简单全部使用默认的属性
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//使用一个实现Map接口的容器来初始化一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//默认负载因子0.75f
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//得到参数m容器的元素个数
int s = m.size();
//如果这是个空容器这个方法就直接结束了
if (s > 0) {
//初始化table数组
if (table == null) {
//通过元素的个数和负载因子反推出原数组的容量，加1是因为除以一个小数，一般都会得到小数
float ft = ((float)s / loadFactor) + 1.0F;
//这个容量要大于MAXIMUM_CAPACITY，就将它赋值为MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//初始化threshold
if (t > threshold)
//tableSizeFor(t)方法是返回一个大于t的2的幂次方，比如t = 13 就返回16
threshold = tableSizeFor(t);
}
//table数组已经被初始化，并且数量大于负载因子，进行扩容
else if (s > threshold)
resize();
//遍历参数m，将其中的键值对，加入到本对象的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);
}
}
}
详情可以去看我的另一篇博文
/*
此方法与JDk1.7版本的hash方法在功能上一样
都是的到key的hashcode，并进行一系列的扰动操作得到一个hash值
处理方式上不同的是JDK1.8采用将32为的hashcode的高16位于低16异或的方式进行扰动
省去了JDK1.7版本大量的位运算。这算是Jdk1.8版本对于Jdk1.7版本的一个优化
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 这方法类似于JDK 1.7版本的highestOneBit(int i)方法，详情请看JDK1.7版本的博客
tableSizeFor(int cap)返回一个大于等于cap的2的幂次方，作为table数组的容量
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//以上操作使变量n的低位编程连续的1
//比如 0101 => 0111,这么做的的好处是只需给n加1，返回值就会变成2的幂次方
//我们table数组的容量必须是2的幂次方
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
流程图
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) {
//tab代表table数组， p初值代表桶的头节点，n代表table数组的长度，i代表当前下标
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;
//通过参数hash值求出下标，下标对应的桶没有元素，直接加入进去即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//桶不为空
else {
/*
桶不为空就存在如下三种情况
1.你要加入的节点的key与桶的头节点的一样
2.桶的头节点是TreeNode，桶是红黑树结构
3.桶的头节点不是TreeNode，桶是链表结构
*/
//e用来临时表示一个节点，k代表桶的头节点p的键
Node<K,V> e; K k;
//如过你要加入的节点的key与桶的头节点的一样
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//用变量e来记录该节点
e = p;
//如果桶的头节点是TreeNode
else if (p instanceof TreeNode)
/*
像红黑树中添加节点，如果该节点已经存在，则返回该节点（不为null），如果添加成功返回null
*/
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果桶的头节点不为TreeNode,也就是说，该桶目前是链表
else {
//遍历该链表
for (int binCount = 0; ; ++binCount) {
//找到链表的尾节点，尾插法插入新的节点，若果遍历完最后一个节点，e= null
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果此时链表在加入新节点后，此时该链表有9个节点，就要将该链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
//将桶从链表结构变换为红黑树结构
treeifyBin(tab, hash);
break;
}
//如果键已经存在
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果HashMap中已经存在你要加入的键，这是e代表桶中那个已经存在的节点,返回老值，给节点赋为新的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//程序能执行到这里，说明桶中不存在与你要加入的节点的键相同的情况
//修改次数加一
++modCount;
//节点数量+1，如果此时的节点数量大于阈值，要对table数组进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//将Node转换为TreeNode节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若果tab数组没有被初始化，通过resize方法去初始化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//通过hash值求出对应的下标，从数组中得到下标所对应的节点
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//将节点变化为TreeNode节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
//将TreeNode节点变为一条链
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//将链表转化为红黑树的储存结构
hd.treeify(tab);
}
}
流程图
//通过键得到对应的值
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) {d
//tab代表table数组，first发表对应桶的头节点，n代表tab数组的大小，k代表键
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) {
//如果桶的头节点的hash值与key与你要查找的相等，直接返回桶的头节点
if (first.hash == hash && //
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果该桶存在后续节点，将桶的第二个节点赋值给e
if ((e = first.next) != null) {
//如果该桶的数据结构是红黑树
if (first instanceof TreeNode)
//通过hash值和key值从红黑树中查找到对应的节点，并返回，没有找到返回null
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//不为红黑树，说明桶的数据结构是链表，那么就遍历该链表进行查找
do {
//如果hash值和键都与要查找的节点相等，返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
1.8版本的resize方法要比JDK1.7版本的更复杂，抛开红黑树，1.8版本的resize方法不光可以扩容table数组，还可以对其初始化
当初次使用resize方法时
threshold有两种情况：
final Node<K,V>[] resize() {
//将当前的table数组用oldTab数组来临时保存
Node<K,V>[] oldTab = table;
//代表老数组的容量，如果老数组为null。容量就为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr代表当前的threshold
int oldThr = threshold;
//newCap代表新的数组容量，newThr代表新的扩容阈值
int newCap, newThr = 0;
//非首次初始化时
if (oldCap > 0) {
//如果老容量已经是HashMap允许的最大容量了，那么将不进行扩容操作，直接返回老数组
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果老数组可以扩容，那么将它扩容两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果扩容后的容量还是要比最大容量要小，那么新的扩容阈值也是老的两倍
newThr = oldThr << 1; // 线性变化，容量扩大两倍，负载因子也扩大两倍
}
else if (oldThr > 0) //非无参构造初始化
newCap = oldThr;
else { // 无参构造初始化，oldThr只有在无惨构造时才小于等于0
//所以新的容量为默认容量16
newCap = DEFAULT_INITIAL_CAPACITY;
//新的扩容阈值是默认负载因子0.75 * 默认容量16 = 12
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"})
//给table数组申请空间
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//以下操作是将老数组中的节点赋值给新数组中，如果是初始化数组，这部分不执行
if (oldTab != null) {
//遍历oldTable数组，挨个取出数组的每一个节点，数组中的节点会出现三种情况
//1.不存在后续节点，直接放入到新数组中即可
//2.存在后续节点，桶是红黑树的结构
//3.存在后续节点，桶是链表的结构
for (int j = 0; j < oldCap; ++j) {
//e临时代表桶的头节点
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//取出一个节点赋值给e，然后将该节点在数组中的存在清空
oldTab[j] = null;
//如果该节点不存在后续节点
if (e.next == null)
//通过e节点的hash值，对新容量求出新的下标，放入到新数组中即可
newTab[e.hash & (newCap - 1)] = e;
//如果此时桶的数据结构是红黑树
else if (e instanceof TreeNode)
//将红黑树拆分到新的HashMap数组中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 此时桶的数据结构为链表
//将一条链表进行重新散列，可能会变成两条链表
//因为hash值是不变的，数组扩大两倍，所以在计算下标时会多算一位，这一位要么0，要么1
//所以同一个链表的节点进行哈希散列，会得到两种下标
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//do-while循环之后,就会生成以loHead和hiHead为头节点的两个链表
do {
next = e.next;
//如果多取的这一位为0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果多取的这一位为1
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//如果loTail不为空，将该链表的头节点加入到新数组中
if (loTail != null) {
//将最后一个节点的链域赋为null
loTail.next = null;
//计算下标时多算的那一位为0是，该下标与原来的下标时一样的，就像010 = 10一样
newTab[j] = loHead;
}
//如果hiTail不为空，将该链表的头节点加入到新数组中
if (hiTail != null) {
//将最后一个节点的链域赋为null
hiTail.next = null;
//计算下标时多算的那一位为1是，该下标与原来的下标相差oldCap，就像010 = 1010一样
//010是取低三位，说明数组容量为8, 1010（B）= 10（D）= 2 + 8 = 10
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回扩容后的新数组
return newTab;
}
流程图
//删除指定key的节点，并返回删除的值
public V remove(Object key) {
Node<K,V> e;
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) {
//tab代表table数组 p代表桶的头节点，n代表桶的长度，index代表桶头节点在数组中的下标
Node<K,V>[] tab; Node<K,V> p; int n, index;
//tab数组存在，并且有容量，并且存在下标所对应的头节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node用来存储要删除的节点
Node<K,V> node = null, e; K k; V v;
//先判断桶的头节点是否是要删除的节点，如果是的话，将桶的头节点赋值给node
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
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { //该桶的结构是单项链表
//遍历该链表，找到要删除的节点，并赋值给node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//node！= null，说明hashMap中存在要删除的节点
//matchValue参数可以用来决定是否要用需要比较节点的值，如果matchValue = false
//那么不论怎么样(!matchValue || (v = node.value) == value || (value != null && value.equals(v))))都为true
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是node的前一个节点
p.next = node.next;
//操作数++
++modCount;
//删除后元素数量减1
--size;
//该方法是一个包权限的方法，在HashMap中是一个空方法，可以被包内覆盖，作用是在删除一个节点后调用
afterNodeRemoval(node);
//返回被删除的节点
return node;
}
}
//HashMap中不存在要删除的节点返回null
return null;
}
//和JDK1.7版本的处理方式一样，都是使用gc来回收空间
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
//不管是红黑树还是链表都可以这个遍历，主要是因为treeifyBin方法，将红黑树节点也形成了一条链
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
在JDK1.7版本的HashMap中，为了避免Hash冲突采用的是头插法的方式向链表中插入新的节点，在多个线程同时进行扩容时，就有可能造成链表成环的情况，一旦链表成环，我们遍历时就会陷入死循环，所以在JDK1.8的版本中使用了尾插法的方式，但是这样就多线程安全了吗，答案是否定的，采用尾插法虽然避免了链表成环的问题，但是产生了新的问题——数据丢失，所以HashMap仍然不能再多线程的环境下使用。
如何造成数据丢失，下面的代码是resize方法的一部分
1 if (oldTab != null) {
2 for (int j = 0; j < oldCap; ++j) {
3 Node<K,V> e;
4 if ((e = oldTab[j]) != null) {
5 oldTab[j] = null;//通过gc回收空间
6 if (e.next == null)
7 //通过e节点的hash值，对新容量求出新的下标，放入到新数组中即可
8 newTab[e.hash & (newCap - 1)] = e;
假设有两个线程A和线程B共同执行resize方法
线程A执行完第1行，时间片段到了，该线程被阻塞，线程B抢占到了CPU
线程B执行完第5行，时间片段结束，
线程A执行到第4行时，此时oldTab[j] == null，那么以e为头节点的链表或者红黑树就会被跳过去，新数组中将没有这些元素，这就造成了数据丢失