JDK7与JDK8中HashMap的实现
JDK7中的HashMap
HashMap底层维护一个数组，数组中的每一项都是一个Entry
transient Entry<K,V>[] table;我们向 HashMap 中所放置的对象实际上是存储在该数组当中；
而Map中的key，value则以Entry的形式存放在数组中
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;这个Entry需要放置于数组中的哪个位置（其中具有相同hash值的Entries被存储在同一位置），其确定方法是基于key的hashCode值）。该过程确保具有相同hashCode值的Entries会被存储在同一个position并由chain连接起来）。
final int hash(Object k) {
int h = 0;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}根据hash值计算得出的结果将通过indexFor方法来确定该值所属的table索引位置
static int indexFor(int h, int length) {
return h & (length-1);
}该方法本质上等价于计算table.length的模数。当两个不同的key在调用hashCode()运算时返回相同的数值时，则会发生哈希碰撞(Hash Collision)。为了缓解这种冲突情况，HashMap采用了将这些键存储在同一个链表中的策略。
当发生hash冲突时，则将存放于数组中的Entry赋值给新项的next指针（需要注意的是，在这种情况下，在map.put(B)操作执行之前,A已经在该位置被占用,因此后续会将B直接存入同一个下标i的位置上,而原先存在的A则会被赋予B的next指针指向关系）
示意图：
所以当hash冲突很多时，HashMap退化成链表。
总结一下map.put后的过程：
当在一个HashMap中执行put操作时（即往HashMap中添加键值对），该操作会通过键的hashCode值来确定存储的位置。
若在指定位置尚未放置任何对象，则将其直接放置于数组中；否则，在现有位置上已经放置了一个目标。沿着已有的目标节点向前遍历（以确定各目标节点之间是否存在相同的属性值），若发现存在相同属性值的目标节点，则继续沿其后继查找；若未找到匹配项，则将当前目标节点插入到合适的位置，并将其与前一目标节点进行关联。
值得注意的是，当key为null时，都放到table[0]中
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}当size超过threshold时会发生扩容操作；其中threshold等于capacity乘以load\ factor值。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}在jdk7中进行.resize操作时，仅在满足以下两个条件的情况下才会触发：一是当前的size值大于等于设置的阈值；二是槽中已经存在至少一个记录。需要注意的是，在这两个条件都得到满足的情况下，并不会立即执行 resize 操作；而是需要等到所有槽中都至少有一个记录后才会进行容量扩展。此外，在每次 resize 过程中，系统都会将容量增加一倍
JDK8中的HashMap
在JDK7之前设计的HashMap结构相对简单，在其实现过程中基于一个数组和若干链表，并且当发生冲突时将相关节点存放在链表中。
在JDK7版本中，默认实现为基于位桶的双层散列表结构。其中第一层为普通的哈希散列表用于存储键值对。自JDK8起，默认实现为一种双层结构：第一层仍使用哈希散列表存储数据。当某个位桶对应的链表长度达到预设阈值时，则会触发将该单向链表转换为平衡二叉查找树（Red-Black Tree），这在官方文档中有详细说明：Red-Black Tree。这种改进使得在处理高负载场景时能够显著提升查询效率，并降低内存占用开销。值得注意的是，在某些特殊场景下（如单节点锁外侧操作），该改进可能带来额外开销从而影响性能表现
在JDK8的实现中，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下 getDefault() when a hash value has 8 or more nodes, it will no longer be stored as a single linked list; instead, it will be converted into a red-black tree structure (as shown in the figure). This is the main difference between HashMap implementations in JDK7 and JDK8.
接下来，我们来看下JDK8中HashMap的源码实现。
JDK中Entry的名字变成了Node，原因是和红黑树的实现TreeNode相关联。
transient Node<K,V>[] table;当冲突节点数不小于8-1时，转换成红黑树。
static final int TREEIFY_THRESHOLD = 8;以put方法在JDK8中有了很大的改变
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) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//如果当前map中无数据，执行resize方法。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则的话，说明这上面有元素
else {
Node<K,V> e; K k;
//如果这个元素的key与要插入的一样，那么就替换一下，也完事。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//还是遍历这条链子上的数据，跟jdk7没什么区别
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //true || --
e.value = value;
//3.
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断阈值，决定是否扩容
if (++size > threshold)
resize();
//4.
afterNodeInsertion(evict);
return null;
}
treeifyBin()就是将链表转换成红黑树。
之前的indefFor()方法消失 了，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的下角标。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}