HashMap原理及源码解析解析

前置条件

哈希冲突

在深入了解HashMap之前，必须解释哈希冲突：

1. 1. 平常所说的哈希冲突是指两个不同的输入，在经过同一个Hash函数后得到相同的哈希值，就判定为哈希冲突，比如Java中Object类中的原生哈希值Object.hashCode(),这个哈希值相同的概率是极其低的。
2. 2. HashMap中的哈希冲突是指，key经过哈希运算和数组长度取余之后的值相同，所以这个概率是很大的。
3. 3. 在了解这两个原理后，就不难理解后面HashMap为了解决哈希冲突采用的方法了；

红黑树

红黑树底层逻辑很复杂，新需要需要对比AVL树来做一下了解：

1. 1. 在树的数据结构中，左子树与右子树的高度差叫做平衡因子；
2. 2. 平衡因子太大会影响树的效率；
3. 3. AVL树和红黑树都是为了解决让平衡因子更低的树结构，AVL树通过控制平衡因子的大小来控制树的平衡度，而红黑树是通过一个颜色标志来控制高度差；
4. 4. AVL树是优先保证查询效率，红黑树是优先保证增删效率；

数据结构

HashMap的和心数据结构是数组+链表+红黑树

1. 1. 数组

   1. Node<K,V>[] table:HashMap的核心存储容器，其中数组每一个元素是一个

   桶

   2. Node<K,V>：存储数据的基本单位，数据结构是链表节点，即key+value+hash值+next指针

   3. 数组的初始容量是16，即2的4次方，数组的长度只能是2的n次方幂（核心设计，下面会说）

2. 2. 链表

   1. HashMap通过链表解决哈希冲突的问题，当两个key经过哈希计算和取余操作后得到的数组下标相同就称为

   哈希冲突

   ；

   2. 当发生哈希冲突时候不会覆盖原来的node，而是将新得到Node挂在到数组下标位置的尾部；

   3. JDK7是采用头插法，并发扩容会导致死循环，JDK8采用尾插法，线程安全优化，保值插入顺序；

3. 3. 红黑树（JDK8新增）

   1. 通过红黑树解决数组中链表过长时候的性能问题；

   2. 链表的查询效率是O(n),红黑树是一种平衡二叉树，查询、新增、删除效率都是O(logn);

   3. 树化条件：数组长度>=64 && 链表节点数量>=8;

   4. 红黑树的节点和链表节点不同，它的节点为TreeNode,继承了Node类；

staticclassNode<K,V> implementsMap.Entry<K,V> {
finalint hash;//哈希值
final K key;//键（唯一不可变）
    V value;//值（可重复）
    Node<K,V> next;//下一个节点指针
}
staticfinalclassTreeNode<K,V> extendsLinkedHashMap.Entry<K,V> {
    TreeNode<K, V> parent;  // 父节点
    TreeNode<K, V> left; //左子节点
    TreeNode<K, V> right; //右子节点
    TreeNode<K, V> prev;    // 前驱节点
boolean red; //红黑标记
}

哈希计算和寻址过程

1. 1. 计算key的hash值：二次哈希处理（hash方法）

staticfinalinthash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

1. 2. 计算下标（寻址公式）

intindex= hash & (h -1);

HashMap的get和put方法

直接上源码

/** 对外暴露的方法*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
  }
/** 实际调用的方法，PUT的核心逻辑*/
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为空，证明没有放入国元素，需要懒加载初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
// table不为空，且当前元素要存的下标下没有元素，直接创建一个节点，放到当前下标下
if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
// 数组不为空，计算下标后，当前下标下有元素
else {
        Node<K,V> e; K k;
// 如果当前存的元素hash相同、key相同，equals也相同，覆盖元素
if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
// 如果已经树化，调用红黑树的插入逻辑，注意这里的p已经在第二个if中赋值过，是当前数组下标下的头节点元素
elseif (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//链表的插入逻辑
for (intbinCount=0; ; ++binCount) {
//结合for循环最后一行的 p=e 来看，找到最后一个节点，插入元素，跳出循环
if ((e = p.next) == null) {
                    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;
            }
        }
//如果有相同的key，判断是否覆盖值
if (e != null) { // existing mapping for key
VoldValue= e.value;
if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
return oldValue;
        }
    }
    ++modCount;
//核心扩容触发条件：元素总数+1 > 阈值 → 调用resize()扩容！
if (++size > threshold)
        resize();
//空方法，LinkedHashMap重写用
    afterNodeInsertion(evict);
returnnull;
}

/** 门面方法*/
public V get(Object key) {
    Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
/** 核心逻辑*/
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
// 素组不为空 & 长度大于0 & 当前key的hash值的下标下元素不为空，则找到当前下标下的头节点
if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & (hash = hash(key))]) != null) {
//头部就是当前key，直接返回节点
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);
// 否则，遍历链表，知道找到存放当前key的节点，返回
do {
if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
return e;
            } while ((e = e.next) != null);
        }
    }
returnnull;
}

HashMap的扩容机制（resize方法）

1. 1. 扩容的核心触发条件

   当HashMap的元素总数(size) > 阈值(threshold) 时，这是唯一核心条件

2. 2. JDK8的核心扩容规则

   1. JDK7之前是重新计算哈希值和重新寻址；

   2. JDK8开始，节点的下标只有两种要么是原来地址，要么是扩容前下标+原来长度；

   3. 无需重新计算hash值只需要通过某一位判断；

   4. 同时链表保持原来顺序，解决JDK7头插法的死循环问题；

   1. 数组长度是原来的两倍

   2. 新的阈值等于新容量✖0.75

   3. 数据迁移规则

3. 3. 源码

final Node<K,V>[] resize() {
// 1. 保存原数组、原容量、原阈值
        Node<K,V>[] oldTab = table;
intoldCap= (oldTab == null) ? 0 : oldTab.length;
intoldThr= threshold;
// 2. 初始化新的容量、阈值
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
return oldTab;
            }
elseif ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
elseif (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) {
floatft= (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 3. 创建新数组，扩容、数据迁移的核心逻辑      
        Node<K,V>[] newTab = (Node<K,V>[])newNode[newCap];
        table = newTab;
if (oldTab != null) {
// 遍历整个桶
for (intj=0; j < oldCap; ++j) {
                Node<K,V> e;
// 存储当前节点
if ((e = oldTab[j]) != null) {
// 将当前节点制空
                    oldTab[j] = null;
// 情况1，只有一个元素，重新计算下标，放入新桶中
if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
// 情况2，链表树化，逻辑复杂涉及树的操作
elseif (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 情况3，当前桶是链表的情况，链表迁移逻辑，这里的代码很美！
else { 
// 定义低位链表，即存储原地不动的元素
                        Node<K,V> loHead = null, loTail = null;
// 定义高位链表，即存储需要位移的元素
                        Node<K,V> hiHead = null, hiTail = null;
// 存储后驱节点
                        Node<K,V> next;
do {
                            next = e.next;
// 这里的核心逻辑是判断新增位是0还是1，因为数组长度一定是2的n次方，也就是二进制数中只有一位是1，而扩容后的newCap-1比oldCap-1的二进制数在高位多一位1
// 比如oldCap = 1000,那么扩容后的newCap = 10000，oldCap-1 = 0111,newCap-1 = 01111,可以发现只需要判断高出来的第四位1与hash的第四位数就可以判断新的位置
// 这里转化了一下，不和newCap-1运算，而是和oldCap运算，通过这个就能判断hash新加入运算的位置是0还是1，进而判断位置
// 如果是0，证明hash的新增位是0，那么hash & newCap-1 = hash & oldCap-1,保持原位置
// 如果不是0，证明hash新增位是1， 那么 hash & newCap-1 = hash & oldCap-1 + oldCap,元素位移到原数组下标+原数组容量的位置
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;
    }

HashMap中的精妙设计

精妙设计一：数组长度h必须是2的n次幂

原因1

1. 1. 用位运算代替取模运算，位运算效率比取模运算高；
2. 2. 寻址公式(h-1) & hash
3. 3. 只有当数组长度h为2的n次幂时候，h-1的二进制低位是全1的，此时(h-1) & hash才等于 hash % h

这里涉及一些数学及二进制的运算知识:

1. 1. hash & h的取值范围是[0,h-1]
2. 2. 当h是2的n次方的时候，h-1转成二进制后是低位全1的二进制数，当hash & （h-1)进行运算时，hash高于h-1的位数会全部被置为0，而hash和h-1相同的位数会被保留下，留下的数刚好是二进制的余数；
3. 3. 正例：
1. 1. hash=9 → 二进制 1001 → 9 & 7 = 1001 & 0111 = 0001 = 1 → 9%8=1
2. 2. hash=15 → 二进制 1111 → 15 &7 = 1111 &0111= 0111=7 →15%8=7
4. 4. 反例：
1. 1. 10 & 8 = 1010 &1000 = 1000 =8 而 10 % 9 = 1
2. 2. 9 & 5 = 1001 & 0101 = 0001 = 1 而 9 % 6 = 3
5. 5. 总结：当h=2的n次方的时候，hash & (h-1)的本质就是截取hash的二进制的后n位，而最后的n位恰好等于hash & h的值，两者完全等价。

原因2（这个原因其实有些牵强，毕竟寻址公式的前提就是低位全1，只能算是锦上添花！）

1. 1. 低位全1保证了与哈希值进行与运算时候，哈希值所有的位数都可以参与运算，这让哈希分布更加均匀
2. 2. 什么意思呢？举个例子，1000 & 1111，这个运算和1111中的后三位没关系，0还是1不影响结果，这样就导致不管是1000、1011、1001等这些计算后都会去数组的相同的索引下，导致链表过长！

精美设计二：hash扰动，解决哈希分布不均的问题

1. 1. hash运算的结果是int类型（32位二进制数），hash计算的特点是高位特征明显，低位重复率高，这就导致直接用hash & (h-1)会导致大量的hash冲突；
2. 2. 为了解决这个问题：将hash值[>>>16]无符号右移 6位，把哈希值的高16位移动到低16位，再和原哈希值做「异或 ^」运算，让高低位特征融合。

// 1. 哈希扰动
inthash= key == null ? 0 : key.hashCode() ^ (key.hashCode() >>> 16);
// 2. 计算数组下标
intindex= hash & (table.length - 1);

精美设计三：链表转红黑树的「阈值设计」，时间复杂度的极致平衡

HashMap 对链表和红黑树的转换设置了双向阈值 + 前置条件：

1. 1. 链表 → 红黑树：当链表长度 ≥8 且 数组容量 ≥64 时，链表转为红黑树；
2. 2. 红黑树 → 链表：当红黑树的节点数 ≤6 时，红黑树退化为链表；
3. 3. 前置条件：如果链表长度≥8，但数组容量 < 64，不会转红黑树，而是直接触发数组扩容。
4. 4. 核心处理：
1. 1. 阈值8是因为：这个数值是数学概率统计的最优值，HashMap的哈希冲突遵循「泊松分布」，链表长度达到 8 的概率是 0.00000006（十亿分之六），几乎是小概率事件。设置 8 为阈值，意味着「只有极端冲突时才转红黑树」，避免了红黑树频繁旋转的开销；
2. 2. 阈值6是因为：避免频繁的转换震荡（比如链表长度在 8 左右反复横跳，导致链表和红黑树来回转换），6 和 8 之间留了「缓冲区间」
3. 3. 数组长度小于64时候不扩容是因为：数组容量小时，哈希冲突的本质是「数组桶数太少」，此时扩容比转红黑树更有效，能从根源上减少冲突，而且扩容的成本远低于红黑树的旋转成本。
4. 4. 使用红黑树而不是AVL树是因为：hashMap的增删改的频率高，红黑树是增删效率优先；

精美设计四：懒加载机制（延迟初始化），节省内存空间

HashMap 在创建对象时，底层的哈希数组（table）并不会立即初始化，而是在第一次调用 put () 方法时，才会真正创建数组并分配内存。

精美设计五：负载因子（loadFactor）的设计，空间与时间的极致权衡

负载因子的本质是 「哈希表的填充度」，这个值是空间利用率和哈希冲突率的黄金平衡点，是 Java 官方通过大量测试得出的最优值

精美设计六：扩容机制的「翻倍扩容 + 低位判断」，迁移效率极致优化

1. 1. HashMap 的扩容是数组长度翻倍（len << 1），而且扩容时，元素的迁移逻辑是「无需重新计算哈希，只需判断哈希值的某一位」。
2. 2. 因为数组长度是 2 的幂次，扩容后 len-1 的二进制会多一个高位的 1，hash值和len – 1同步新增加入与运算的位数称为「新增高位」，此时元素的新下标只有两种可能：
1. 1. 如果哈希值的「新增高位」是 0 → 新下标 = 原下标；
2. 2. 如果哈希值的「新增高位」是 1 → 新下标 = 原下标 + 原数组长度。