HashMap基于JDK8
JDK7：
- HashMap实现是
数组 + 链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。- 当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下面有一条长长的链表，极端情况HashMao就相当于一个单链表，假如单链表有n个元素遍历的时间复杂度就是O(n)，完全失去了它的优势
JDK8：
- JDK7与JDK8中HashMap实现的最大区别就是
对于冲突的处理方法。JDK 1.8 中引入了红黑树（查找时间复杂度为O(logn)）,用数组+链表+红黑树的结构来优化这个问题扩容阈值公式
长度=容量*0.75
参数和构造方法
/**
* The default initial capacity - MUST be a power of two.
*/
//默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。
//1向左移位4个，00000001变成00010000
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 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.
*/
//最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
//当桶的某个节点的数大于8时 转为红黑树
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
//当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//存储元素的数组，transient关键字表示该属性不能被序列化
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
//将数据转换成set的另一种存储形式，这个变量主要用于迭代功能
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
//元素个数
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
//统计该map修改的次数
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
//加载因子实际大小
final float loadFactor;
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* 构造一个具有指定初始容量和负载因子的空HashMap
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
//设置初始容量和加载因子
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);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
//设置初始容量，并使用默认的加载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*
* 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap
*/
//空参构造，使用默认的加载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor.
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取map的实际长度
int s = m.size();
if (s > 0) {
//判断table是否初始化
if (table == null) { // pre-size
//求出需要的容量，因为实际使用的长度=容量*0.75得来的，+1是因为小数相除，基本都不会是整数，容量大小不能为小数的，后面转换为int，多余的小数就要被丢掉，所以+1，例如，map实际长度22，22/0.75=29.3,所需要的容量肯定为30，有人会问如果刚刚好除得整数呢，除得整数的话，容量大小多1也没什么影响
float ft = ((float)s / loadFactor) + 1.0F;
//判断容量是否超出最大容量
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
//对临界值进行初始化，tableSizeFor(t)这个方法会返回大于t值的，且离其最近的2次幂，例如t为29，则返回的值是32
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果table已经初始化，则进行扩容操作，resize()就是扩容的方法。
else if (s > threshold)
resize();
//遍历，把map中的数据转到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);
}
}
}
扩容
resize()
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* 初始化或加倍表大小。如果为空，则按照字段阈值中保存的初始容量目标进行分配。
* 否则，因为我们使用二次幂展开，每个 bin 中的元素必须保持相同的索引，或者在新表中以二次幂的偏移量移动。
*
* @return the table
*/
//扩容方法（重点）
final Node<K,V>[] resize() {
//把没插入之前的哈希数组保存在oldTal
Node<K,V>[] oldTab = table;
//获取oldTab长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//old的长度临界值
int oldThr = threshold;
//初始化new的长度和临界值
int newCap, newThr = 0;
//如果oldTab的长度大于零，说明不是第一次初始化。
//这里HashMap使用的懒加载
if (oldCap > 0) {
//判断oldTab长度是否超过最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
//临界值为整数的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容两倍，并且扩容后的长度要小于最大值，old长度也要大于16。
//这里还有个 当old的容量小于默认的容量的时候 会在下面进行补充
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//临界值也扩容为old的阈值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);
}
//这里是对上面old容量小于默认阈值的时候的补充。也就是初始化时容量小于默认值16的，此时newThr没有赋值
if (newThr == 0) {
//new的新阈值
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做了两件事 赋值 和 判空
if ((e = oldTab[j]) != null) {
//赋值完了，就将此处的值置空，方便垃圾回收 释放内存
oldTab[j] = null;
//如果该节点的下一个节点没元素了，说明不是链表，可以直接存入新表的 e.hash & (newCap - 1) 的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
else if (e instanceof TreeNode)
//把此树进行转移到newCap中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//到这来了就说明e后面带了个单链表，这里就需要遍历单链表，存入新的newTab
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//下面这部分比较难理解可以参考下（https://blog.csdn.net/weixin_41565013/article/details/93190786）
do {
//记录下一个节点
next = e.next;
// (e.hash & oldCap) == 0 选择出扩容后在同一个桶中的节点，然后再将他们重新连起来
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;
}
split()
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
//此方法就是拆分树，然后重新构建树或者链表
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
//记录低位链表长度lc
//记录高位链表长度hc
//这里的低位和高位指的数组扩容后 在新数组上的索引位置
int lc = 0, hc = 0;
//遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//以下的操作就是做个按位与运算，按照结果拉出两条链表
if ((e.hash & bit) == 0) {
//低位尾部标记为null,表示还未开始处理，此时e是第一个要处理的低位树链表
//节点，故e.prev等于loTail都等于null
if ((e.prev = loTail) == null)
//低位树链表的第一个树链表节点
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
//高位树链表的第一个树链表节点
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//低位链表头节点不为空
if (loHead != null) {
//判断低位链表的长度是否小于或等于 6（也就是树转链表的阈值）
if (lc <= UNTREEIFY_THRESHOLD)
//那就从红黑树转链表了，低位链表，迁移到新数组中下标不变，还是等于原数组到下标
//untreeify方法先对传入的进行遍历然后再通过replacement方法new新的node节点生成单链表
tab[index] = loHead.untreeify(map);
else {
//低位链表，迁移到新数组中下标不变，还是等于原数组到下标，把低位链表整个拉到这个下标下，做个赋值
tab[index] = loHead;
//高位链表不为空，说明原来旧数组的那颗红黑树已经被拆成了两个链表
if (hiHead != null) // (else is already treeified)
//那么低位就需要重新构建红黑树
loHead.treeify(tab);
}
}
//高位链表不为空
if (hiHead != null) {
//判断高位链表的长度是否小于或等于 6（也就是树转链表的阈值）
if (hc <= UNTREEIFY_THRESHOLD)
//那就从红黑树转链表了，高位链表，迁移到新数组中的下标=【旧数组+旧数组长度】
tab[index + bit] = hiHead.untreeify(map);
else {
//高位链表，迁移到新数组中的下标=【旧数组+旧数组长度】，把高位链表整个拉到这个新下标下，做赋值
tab[index + bit] = hiHead;
//低位链表不为空，说明原来旧数组的那颗红黑树已经被拆成了两个链表
if (loHead != null)
//那么就需要重新构建红黑树
hiHead.treeify(tab);
}
}
}
添加元素
put()
添加和修改都是put方法，因为key唯一，值可以进行覆盖
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//hash这个方法，证明hashmap是可以穿key为空的，当为空的时候哈希值就是0
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key //键的散列值
* @param key the key //键
* @param value the value to put //值
* @param onlyIfAbsent if true, don't change existing value //如果为真，则不更改现有值
* @param evict if false, the table is in creation mode. //如果为 false，则表处于创建模式。
* @return previous value, or null if none //前一个值，如果没有，则为 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table没有初始化，则初始化table，并且返回长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过(n-1)&hash计算出hash值对应的下标，判断数组中该下标的位置是否为空
//如果为空，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
//为空则直接创建新节点
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//要插入的节点的key正好对上table中对应index中储存的头节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
//直接修改值
e = p;
//要插入的数不在头节点，table中存储为红黑树
else if (p instanceof TreeNode)
//putTreeVal方法解析在下面
//this 代表的就是hashmap自身
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//要插入的数不在头节点，table中存储的为链表
else {
for (int binCount = 0; ; ++binCount) {
//如果遍历到尾部都还没找到这个值，就在尾部进行添加
if ((e = p.next) == null) {
//尾插法，1.7是头插法
p.next = newNode(hash, key, value, null);
//当链表长度达到树化的长度，就进行转化成红黑树
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;
p = e;
}
}
//当map中存在key时
if (e != null) { // existing mapping for key
//保存下旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//更新新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size到了扩容阈值就进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put()方法流程：
首先找到hash值对应的下标，如果数组中对下标为空，直接将节点插入，如果不为空则分为三种情况：
1、要插入的节点的key正好为头节点，直接修改value
2、要插入的节点不在头节点，并且table中存储的为红黑树，在树中查找是否存在这个key，存在就进行修改值，不存在就插入
3、要插入的节点不在头节点，并且table中存储的为链表，在链表中查找是否存在这个key，存在直接修改。不存在就插入，且判断链表长度是否达到树化的长度，如果达到就转为红黑树，如果未达到就修改值
4、最后判断size是否大于扩容阈值，大于就进行扩容，如果没到就不需要。
总结：hashmap的初始容量是16，在第一次put的时候才会初始化，否则就是零。当链表的长度 大于8 的时候就会转红黑树，红黑树长度 小于6 的时候会转为链表。中间值是防止链表红黑树频繁转换。扩容因子默认为0.75，扩容阈值为 扩容因子 * 默认容量 = 0.75 * 16 = 12 。当数组的长度 大于12才 会对数组进行两倍扩容。
putTreeVal()
/**
* Tree version of putVal.
*/
/**
* 当存在hash碰撞的时候，且元素数量大于8个时候，就会以红黑树的方式将这些元素组织起来
* map 当前节点所在的HashMap对象
* tab 当前HashMap对象的元素数组
* h 指定key的hash值
* k 指定key
* v 指定key上要写入的值
* 返回：指定key所匹配到的节点对象，针对这个对象去修改V（返回空说明创建了一个新节点）
*/
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;
//this：代表TreeNod自己
//父节点不为空那么查找根节点，为空那么自身就是根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//遍历root
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//如果当前节点hash 大于 指定key的hash值，要添加的元素应该放置在当前节点的左侧
if ((ph = p.hash) > h)
dir = -1;
如果当前节点hash 小于 指定key的hash值，要添加的元素应该放置在当前节点的右侧
else if (ph < h)
dir = 1;
//如果当前节点的键对象 和 指定key对象相同，就返回当前节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//走到这一步说明 当前节点的hash值和指定key的hash值是相等的，但是equals不等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//searched 标识是否已经对比过当前节点的左右子节点了
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;
}
//走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点
//再比较一下当前节点键和指定key键的大小
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
/*
* 如果dir小于等于0，那么看当前节点的左节点是否为空，
* 如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
*
* 如果dir大于等于0，那么看当前节点的右节点是否为空，
* 如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
*
* 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
// 左孩子指向到这个新的树节点
xp.left = x;
else
// 右孩子指向到这个新的树节点
xp.right = x;
// 链表中的next节点指向到这个新的树节点
xp.next = x;
// 这个新的树节点的父节点、前节点均设置为 当前的树节点
x.parent = x.prev = xp;
// 如果原来的next节点不为空
if (xpn != null)
// 那么原来的next节点的前节点指向到新的树节点
((TreeNode<K,V>)xpn).prev = x;
// 重新平衡，以及新的根节点置顶
moveRootToFront(tab, balanceInsertion(root, x));
// 返回空，意味着产生了一个新节点
return null;
}
}
}
treeifyBin()
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
//n是数组长度，index是索引
int n, index; Node<K,V> e;
//这里的tab指的是本HashMap中的数组，n为数字长度，如果数组为null或者数组长度小于最小树的容量就进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//否则说明满足转红黑树条件，通过按位与运算取得索引index，并将该索引对应的node节点赋值给e，e不为null时
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//这里do while做的事情是将 node的单链表转为 treeNode 的双向链表
do {
//将e节点转换为树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果尾节点为空，则说明没有根节点
//这时元素数目都超过8个了，还能没有尾节点么，所以没有尾节点只能说明还没设置根节点
if (tl == null)
//设置根节点
hd = p;
else {
//把tl设置为p的前驱节点
p.prev = tl;
//把p设置为tl的后继节点，这两步其实就是我指向你，你指向我的关系，为了形成双向链表
tl.next = p;
}
//把首节点设置成p后，把p赋值给尾节点tl，然后会再取链表的下一个节点，转成TreeNode类型后再赋值给p，如此循环
tl = p;
} while ((e = e.next) != null);
//用新生成的双向链表替代旧的单向链表，其实就是把这个数组对应的位置重新赋值成新双向链表的首节点
if ((tab[index] = hd) != null)
//这个方法里就开始做各种比较，左旋右旋，然后把双向链表搞成一个红黑树
hd.treeify(tab);
}
}
treeify()
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//遍历链表 this 表示当前要插入的节点 即x
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//将当前节点下一个节点保存下来
next = (TreeNode<K,V>)x.next;
//将当前节点的左右节点制空
x.left = x.right = null;
//判断root是否为空
if (root == null) {
//root为空，就将当前节点的父节点置空，颜色变为黑色，将当前节点置为root
x.parent = null;
x.red = false;
root = x;
}
//当根节点不为空
else {
//保存要插入的节点的值
K k = x.key;
//得到当前要插入的节点的hash值
int h = x.hash;
Class<?> kc = null;
//将root赋值树节点p 且进行遍历，p指的是红黑树的节点
for (TreeNode<K,V> p = root;;) {
int dir, ph;
//获取当前树节点的值 且保存
K pk = p.key;
//将当前树节点hash值赋值给ph保存，然后和插入元素的哈希值比较大小
//然后决定是插入到树节点的左边还是右边
if ((ph = p.hash) > h)
//插入在左边
dir = -1;
else if (ph < h)
//插入在右边
dir = 1;
//如果k所属的类没有实现Comparable接口 或者 k和p节点的key相等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//用于不可比较或者hashCode相同时进行比较的方法,
//只是一个一致的插入规则，用来维护重定位的等价性。
dir = tieBreakOrder(k, pk);
//将当前树节点p赋值给xp
TreeNode<K,V> xp = p;
//判断dir大小，再将当前节点的左或者右节点赋值给p 去判断是否为空
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//将当前节点置为插入节点的父节点
x.parent = xp;
//如果dir小于0，就插入在当前节点的左边
if (dir <= 0)
xp.left = x;
else
//反之，就插入在当前节点的左边
xp.right = x;
//插入当前节点后，需要重新平衡。返回的是平衡好了后的根节点
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
balanceInsertion()
//参数：root：当前节点的根节点 x：插入的节点
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
//新插入的节点
x.red = true;
//定义变量
//xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果插入节点的父节点为空，那么该节点就是根节点
if ((xp = x.parent) == null) {
//将该节点标为黑色
x.red = false;
return x;
}
//父节点为黑色 或者 爷爷节点为空，那么 root 就是根节点
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果父节点是爷爷节点的左孩子
if (xp == (xppl = xpp.left)) {
//如果右叔叔节点不为空 且 右叔叔节点为红色
if ((xppr = xpp.right) != null && xppr.red) {
//右叔叔置为黑色
xppr.red = false;
//父节点置为黑色
xp.red = false;
//爷爷节点置为红色
xpp.red = true;
//将爷爷节点当为其实节点，进行下一轮循环
x = xpp;
} else {//如果右叔叔为空 或者 为黑色
//如果插入节点是父亲节点的右孩子
if (x == xp.right) {
//左旋
root = rotateLeft(root, x = xp);
//获取爷爷节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//父亲节点不为空
if (xp != null) {
//将父亲节点置为黑色
xp.red = false;
//爷爷节点不为空
if (xpp != null) {
//爷爷节点置为红色
xpp.red = true;
//右旋
root = rotateRight(root, xpp);
}
}
}
} else {//如果父节点是爷爷节点的右孩子
//左叔叔节点不为空 且 为红色
if (xppl != null && xppl.red) {
//左叔叔节点置为黑色
xppl.red = false;
//父节点置为黑色
xp.red = false;
//爷爷节点置为红色
xpp.red = true;
//讲爷爷节点置为当前处理的起始节点
x = xpp;
} else {//左叔叔节点为空 或者 为黑色
//当前节点为父节点的左孩子
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
//获取爷爷节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//父节点不为空
if (xp != null) {
//父节点置为黑色
xp.red = false;
//爷爷节点不为空
if (xpp != null) {
//爷爷节点置为红色
xpp.red = true;
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
rotateLeft()、rotateRight()
//参数：root：根节点 p左旋的节点
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//左旋节点不为空且左旋节点的右孩子不为空
if (p != null && (r = p.right) != null) {
//左旋节点的右边孩子的左节点 赋值给 左旋节点的右孩子 且不为空
if ((rl = p.right = r.left) != null)
//设置rl和左旋节点的父子关系
rl.parent = p;
//左旋节点的的父节点 指向 左旋节点的右孩子的父节点
//此时如果父节点为空，说明r 已经是顶层节点，应该作为root 并且标记为黑色
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
//左旋节点为父节点的左孩子
else if (pp.left == p)
//设置r和父节点的父子关系
pp.left = r;
//左旋节点为右孩子
else
//设置r和父节点的父子关系
pp.right = r;
//左旋节点作为 左旋节点的右孩子的左节点
r.left = p;
//左旋节点的右孩子 作为 左旋节点的父节点
p.parent = r;
}
return root;
}
//和上面的左旋类似 类比一下
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
moveRootToFront()
/**
* Ensures that the given root is the first node of its bin.
* 确保给定的根是其容器的第一个节点。
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//红黑树根节点不能为空 table数组不能为空
if (root != null && tab != null && (n = tab.length) > 0) {
//获取红黑树的根节点 放在数组上的下标位置
//此处计算出的数组下标的索引位置 与 原链表的索引位置应该是一致的
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果当前的下标位置放的对象和需要验证的对象不是同一个
if (root != first) {
Node<K,V> rn;
//设置红黑树根节点在数组上的索引位置
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//重置红黑树根节点的上下级关系，
//主要是调整root,root.prev,root.next,first;四者的关系
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//检查红黑树
assert checkInvariants(root);
}
}
红黑树光看代码比较抽象，可以看看这篇文章结合图片理解：https://blog.csdn.net/weixin_42340670/article/details/80550932
移除元素
remove()
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
//移除元素
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 hash for key //key的hash值
* @param key the key //key
* @param value the value to match if matchValue, else ignored //value 有就有没有就忽略
* @param matchValue if true only remove if value is equal //如果为true，则仅在值相等时删除
* @param movable if false do not move other nodes while removing //可移动如果为false，则在删除时不要移动其他节点
* @return the node, or null if none
*/
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不为空，并且hash对应的桶不为空时
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;
//桶中的头节点就是我们要删除的节点
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 {
//hash值相等，且key地址相等或者key不为空且equals相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
//记录要删除的节点
node = e;
break;
}
//p保存当前遍历到的节点
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;
--size;
//此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理
afterNodeRemoval(node);
return node;
}
}
//返回null则表示没有该节点，删除失败
return null;
}
removeTreeNode()
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
//参数：map 删除操作的map tab：map存放数据的链表 movable：是否移动根节点到头节点
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
//获取索引值
int index = (n - 1) & hash;
//first：数组存放数据的索引位置的值
//root：根节点 红黑树根节 根first应该是同一个
//rl：root节点的左孩子节点
//succ：后节点
//pred：前节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//succ：调用这个方法的节点（待删除节点）的后驱节点
//prev：调用这个方法的节点（待删除节点）的前驱节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//维护双向链表（map在红黑树数据存储的过程中，除了维护红黑树之外还对双向链表进行了维护）
//从链表中将该节点删除
//若要删除的节点的前一个为空，则first和tab[index]都指向要删除结点的后一个结点
if (pred == null)
tab[index] = first = succ;
//若要删除的节点的前一个不为空，后驱节点的前置指针设为删除节点的前置节点
else
pred.next = succ;
//后驱节点不为空，后驱节点的前置指针设为删除节点的前置节点
if (succ != null)
succ.prev = pred;
//若删除的节点是树中的唯一结点则直接结束
if (first == null)
return;
//更新root根节点
if (root.parent != null)
root = root.root();
//根自身或者左右儿子其中一个为空说明结点数过少（不超过2）转为线性表并结束
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
//p指向要删除的结点，pl指p的左子节点，pr指p的右子节点，replacement用于后续的红黑树调整，指向的是p或者p的继承者。
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//删除节点的左右节点都不为空时，寻找右子树中最左的叶结点作为后继，s指向这个后继节点
while ((sl = s.left) != null) // find successor
s = sl;
//交换后继节点和要删除节点的颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
//s后继节点的右子节点
TreeNode<K,V> sr = s.right;
//p要删除节点的父节点
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
//p是s的直接父亲，交换p和s的位置
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
//s在sp父节点的左节点
if (s == sp.left)
//p放到s原本的位置
sp.left = p;
//s在sp父节点的右节点
else
//p放到s原本的位置
sp.right = p;
}
//p的右子树节点成为s的右子树节点
if ((s.right = pr) != null)
//s放到p原本的位置
pr.parent = s;
}
p.left = null;
//s原本的右子树成为p的右子树
if ((p.right = sr) != null)
//p放到s原本的位置
sr.parent = p;
//p原本的左子树成为s的左子树
if ((s.left = pl) != null)
//s放到p原本的位置
pl.parent = s;
//s的父节点为p的父节点是null
if ((s.parent = pp) == null)
//若s原本是根则新的根是s
root = s;
else if (p == pp.left)
//若p是某个节点的左节点，则s成为该节点的左节点
pp.left = s;
else
//若p是某个节点的右节点，则s成为该节点的右节点
pp.right = s;
//若s节点有右节点（s一定没有左节点），则replacement为这个右节点否则为p
if (sr != null)
replacement = sr;
else
replacement = p;
}
//若p的左右节点有一方为null，则replacement为非空的一方，否则为p自己
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
//如果p是叶子节点，replacement==p，否则replacement为p的右子树中最左节点
//p有子节点或者s有子节点
if (replacement != p) {
//若p不是叶子节点，则让replacement的父节点指向p的父节点
TreeNode<K,V> pp = replacement.parent = p.parent;
//用replacement来替换p
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
//移除p结点
p.left = p.right = p.parent = null;
}
//以replacement为中心，进行红黑树性质的修复，replacement可能为s的右节点或者p的子节点或者p自己
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//p没有子节点或者s没有子节点，直接移除p
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
//整理根结点
moveRootToFront(tab, r);
}
clear()
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
//清空所有元素
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;
}
}
获取元素
get()
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
//通过key获取value
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
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))))
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;
}
HashMap基于JDK7
构造方法
public HashMap() {
//默认容量16
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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);
//超过最大容纳量，取最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子容错处理
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//通过1左移运算，找到一个大于/等于自定义容量的最小2的幂次方数
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//基于容量，创建数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
添加元素
put()
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//HashMap允许存储null键，存储在数组的0索引位置
if (key == null)
return putForNullKey(value);
//内部通过一个扰乱算法获得一个hash值，用于计算数组索引
int hash = hash(key);
//计算数组索引
int i = indexFor(hash, table.length);
//遍历当前桶下的链表，判断是否存在重复键，存在就覆盖值，不存在就新增
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//添加元素
addEntry(hash, key, value, i);
return null;
}
addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
//元素个数大于阈值，同时当前索引位有值，就会执行扩容操作
if ((size >= threshold) && (null != table[bucketIndex])) {
//2倍扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//重新计算索引位置
bucketIndex = indexFor(hash, table.length);
}
//基于键值创建Entry节点，并以头插法存入对应位置
createEntry(hash, key, value, bucketIndex);
}
createEntry()
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
resize()
//扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer()
/**
* Transfers all entries from current table to newTable.
*/
//迁移链表
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
获取元素
get()
public V get(Object key) {
//取空键对应的值
if (key == null)
return getForNullKey();
//取非空键对应的值
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getEntry()
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
//遍历链表获取值
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
总结
HashMap如何防止碰撞
解决hash碰撞的方式有很多，比如开放地址法，重哈希，链地址法，公共溢出区等等。
HashMap中防止碰撞的方式主要有两个：哈希值扰动+链地址法（当扰动后，还是hash碰撞，使用链表/红黑树存储元素）
HashMap的扰动方法
-
JDK1.7
final int hash(Object k) { int h = 0; h ^= k.hashCode(); //充分利用高低位 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } -
JDK1.8
static final int hash(Object key) { int h; //充分利用高低位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
位运算符号的介绍
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| | | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
为什么容量必须是2的幂次方数呢？
1、那些2的幂次方数有一个特点，高位为1，后续全部为0，这样的数减一，就会变成刚才为1的位置为0，后续所有值都为1，这样减一之后的数，和任何数进行与运算，得到的结果，永远是0-2的幂次方减一，正好符合数组角标的范围。
2、同时减一后，一定是一个奇数，末位一定是1，那么和其他数进行与运算后，得到的结果可能是奇数，也可能是偶数，那么可以充分利用数组的容量。
3、的幂次方数减一后，低位都是1，这样数组的索引位都有可能存入元素，如果低位不都是1，就会导致有些数组的索引位永远空缺，不利于数组的充分利用
4、便于扩容时，重新定位元素的索引位，我们知道扩容的原则是原来数组的2倍，那么扩容后，数组容量还是一个2的幂次方数，原数组中的元素在新数组中，要么在原始索引位，要么在原始索引位+扩容值的位置，避免了重新hash的效率问题
JDK1.8和1.7的区别
- JDK1.8时红黑树+链表+数组的形式，当桶内元素大于8时，便会树化
- hash值的计算方式不同
- JDK1.7table在创建hashmap时分配空间，而JDK1.8在put的时候分配，如果table为空，则为table分配空间。
- 在发生冲突，插入链中时，7是头插法，8是尾插法。
- 在resize操作中，JDK1.7需要重新进行index的计算，而JDK1.8不需要，通过判断相应的位是0还是1，要么依旧是原index，要么是oldCap + 原index
- JDK1.7
- 数据结构：数组+单链表
- 扩容：先扩容，再添加值。添加值使用的头插法
- 多线程下：扩容会导致循环引用
- JDK1.8
- 数据结构：数组+单链表+红黑树+双向链表
- 扩容：先添加值，再扩容。添加值使用的尾插法
- 多线程下：会导致数据丢失