今天复习了一下HashMap的部分，写一篇博客记录一下今天学习内容

虽然之前学习过，但由于后来没怎么使用过而且也没复习基本忘得差不多了

在Java的HashMap中，高效存储键值对的核心在于哈希算法和索引定位。本文将结合源码逐步拆解存储流程，并给出代码示例。

 核心流程概述

1. 扰动函数处理Key 通过扰动函数优化Key的哈希值，减少碰撞
2. 存储哈希值 计算后的哈希值存入Node对象的hash字段
3. 计算桶下标 用(n-1) & hash定位数组索引（n为数组长度）
4. 存入数据结构 根据下标存入数组（或链表/红黑树）

 源码级分步解析（基于JDK 17）

① 扰动函数与哈希计算

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

• 作用：将原始哈希码的高16位与低16位异或
• 目的：让高位参与运算，解决低位相同导致的哈希碰撞
• 结果：扰动后的哈希值存储在Node的hash字段

② Node对象结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 存储扰动计算后的哈希值
    final K key;
    V value;
    Node<K,V> next; // 链表结构指针
}

③ 索引定位公式

// 在putVal方法中：
int index = (n - 1) & hash;

• n-1：当前数组长度减1（如长度16→15，二进制0...01111）
• 位与运算：高效实现取模运算，hash % n等价于(n-1) & hash

④ 完整put流程伪代码

final V putVal(int hash, K key, V value) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 首次使用触发初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 计算桶下标 (核心公式)
    i = (n - 1) & hash;
    
    // 3. 处理碰撞情况
    if ((p = tab[i]) == null) 
        tab[i] = newNode(hash, key, value); // 无碰撞直接存
    else {
        // 碰撞后遍历链表/红黑树
        if (p.hash == hash && ...)
            // 更新已存在key的值
        else {
            // 链表新增节点
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash); // 链表转红黑树
        }
    }
}

举个🌰 实战示例与验证

import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>(16); // 初始容量16
        
        // 存储键值对 "A":1
        map.put("A", 1);
        
        // 手动验证存储过程
        String key = "A";
        // 1. 原始哈希码
        int hashCode = key.hashCode(); 
        System.out.println("原始哈希码: 0x" + Integer.toHexString(hashCode));
        
        // 2. 扰动计算
        int perturbedHash = hash(key);
        System.out.println("扰动哈希值: 0x" + Integer.toHexString(perturbedHash));
        
        // 3. 计算桶下标 (n=16)
        int n = 16;
        int index = (n - 1) & perturbedHash;
        System.out.println("数组下标: " + index);
    }
    
    // JDK扰动函数实现
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

输出结果：

原始哈希码: 0x41
扰动哈希值: 0x41  // 小值无高位变化
数组下标: 1       // (16-1)=15: 0b1111 & 0x41=65 → 1

 设计原理深度剖析

1. 为什么用位与代替取模？

   • 位运算(n-1) & hash比%效率高10倍以上（实测）
   • 前提：数组长度必须是2的幂（保证n-1的二进制全为1）

2. 扰动函数的必要性

   原始哈希: 0x1234abcd 和 0x5678abcd
   n=16时：
     未扰动 → 两值低位相同 → 碰撞
     扰动后 → 高位参与运算 → 低位不同 → 避免碰撞

     3.哈希碰撞策略

最佳实践建议

1. 避免自定义Key哈希碰撞

   // 错误实现：所有对象返回相同哈希码
   @Override
   public int hashCode() { return 1; } // 导致HashMap退化为链表
   
   // 正确实现：组合关键字段哈希
   @Override
   public int hashCode() {
       return Objects.hash(field1, field2);
   }

1. 初始化容量优化

   // 预期存储1000个元素时
   new HashMap<>(2048); // 避免扩容 (1000/0.75≈1333 → 取2的幂2048)

至此，本章的内容结束，后续我会补充一下在高并发情况下HashMap会出现的一些问题