---

前言

今天用 Java 手写一个最简化的 HashMap，帮你彻底搞懂哈希冲突和扩容机制。代码基于 JDK 1.8 之前的「数组 + 链表」思路（暂不涉及红黑树），新手也能轻松看懂！！

第一章到第四章是分步讲解，第五章有完整代码，在最后我附上了一些考点帮助大家巩固~~

---

一、HashMap 的基本骨架

先把「骨架」搭好：定义内部链表节点类、核心成员变量、构造器和辅助的size()方法

public class MyHashMap<K,V> {
    /*
    1、搭建完整结构：所有链表头节点的数组即为最简单直观的哈希表完整结构的体现（红黑树略），需要考虑初始容量，这里设为16
        完成基本函数：构造器和size方法
     */
    private Node<K, V>[] table; //链表头节点数组
    private static final int DEFAULT_CAPACITY = 16; //初始容量
    private int size; //当前元素数量
    //完成链表节点
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    //构造函数
    public MyHashMap() {
        this.table = new Node[DEFAULT_CAPACITY]; // 初始化桶数组
        this.size = 0; // 初始键值对数量为0
    }
    //获取长度
    public int size() {
        return size;
    }
}

二、哈希函数

核心逻辑：把 key 转成 hashcode，再映射成数组索引。
第一步：用 key.hashCode() 获取 hash 值；
第二步：& 0x7FFFFFFF 去掉符号位（保证非负）；
第三步：对桶容量取模（保证索引不越界）。
代码如下：

    // 哈希函数：key==>桶索引
    private int hash(K key) {
        if (key == null) return 0;
        // 1、去掉符号位，转成非负数
        // 2、对桶容量取模，索引不超过桶容量
        return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }

三、resize扩容函数 + put函数（重点！！！）

这两个是 HashMap 的灵魂，我们先写resize，再写依赖它的put。

1. resize 扩容函数

触发条件：size ≥ 容量 × 负载因子（0.75）。
逻辑：

• 桶容量翻倍；
• 遍历旧桶，把所有元素重新插入新桶（复用 put 方法）。

    // resize扩容函数：桶容量翻倍，旧元素进新桶
    private void resize() {
        Node<K, V>[] oldTable = table; // 旧桶
        int newCapacity = oldTable.length * 2; // 新容量二倍
        Node<K, V>[] newTable = new Node[newCapacity]; // 新的“骨架”
        table = newTable;
        size = 0; // 重置容量
        // 遍历复制
        for (Node<K, V> node : oldTable) {
            while (node != null) {
                put(node.key, node.value); // 复用put方法重新插入
                node = node.next;
            }
        }
    }
    public void put(K key, V value) {

    }

2. put 函数（核心中的核心）

逻辑：

1. 计算 key 对应的桶索引；
2. 遍历该桶链表：若 key 已存在，直接更新 value；
3. 若 key 不存在，在链表末尾插入新节点；
4. 插入后检查是否需要扩容。

下面代码有详细的注释解释每一步

    private static final float LOAD_FACTOR = 0.75f;  // 负载因子
    // put函数：添加/更新键值对
    public void put(K key, V value) {
        int index = hash(key); // 步骤1————计算key对应的桶索引
        Node<K, V> current = table[index]; // 拿到该桶的头节点
        // 步骤2————遍历桶内链表，检查key是否已存在
        while (current != null) {
            if (current.key.equals(key)) { // key已存在
                current.value = value; // 更新value
                return; // 直接结束，不需要后续操作
            }
            current = current.next; // 没找到，继续看下一个节点
        }
        // 步骤3————key不存在，创建新节点并插入链表末尾
        Node<K, V> newNode = new Node<>(key, value);
        if (table[index] == null) {
            table[index] = newNode; // 桶为空，新节点直接做头节点
        } else {
            // 桶不为空，找到链表最后一个节点，把新节点插在后面
            Node<K, V> tail = table[index];
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = newNode;
        }
        size++; // 键值对数量+1
        // 步骤4————判断是否需要扩容（size大于等于容量×负载因子）
        if (size >= table.length * LOAD_FACTOR) {
            resize();
        }
    }

四、get 函数

还是分两步：
1、用hashcode查找
2、用equals查找
（所以哈希碰撞不代表两个元素相同，这也是我们java要求重写equals必须重写hashcode的原因）

    // get函数，key查value
    public V get(K key) {
        int index = hash(key); //计算索引
        Node<K, V> current = table[index];
        // 链表遍历找 key
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null; // 遍历完没找到，返回null
    }

五、测试结果和完整代码

测试结果：

附上完整代码，代码很基础，希望大家也能试试！

public class MyHashMap<K,V> {
    /*
    1、搭建完整结构：所有链表头节点的数组即为最简单直观的哈希表完整结构的体现（红黑树略），需要考虑初始容量，这里设为16
        完成基本函数：构造器和size方法
    2、哈希函数
        先转hashcode，最简单的调用即可
        索引还是非负加取模
    3、扩容：resize，添加：put函数
        在达到负载因子是需要resize，所以先完成，容量翻倍也就是先留旧桶数组，复制到一个新的2倍！
        最核心的是put，需要完整整理逻辑
    4、查询：get函数
        先哈希再equals就完事
     */
    private static final float LOAD_FACTOR = 0.75f;  // 负载因子
    private Node<K, V>[] table; //链表头节点数组
    private static final int DEFAULT_CAPACITY = 16; //初始容量
    private int size; //当前元素数量
    //完成链表节点
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    //构造函数
    public MyHashMap() {
        this.table = new Node[DEFAULT_CAPACITY]; // 初始化桶数组
        this.size = 0; // 初始键值对数量为0
    }
    //获取长度
    public int size() {
        return size;
    }

    // 哈希函数：key==>桶索引
    private int hash(K key) {
        if (key == null) return 0;
        // 1、去掉符号位，转成非负数
        // 2、对桶容量取模，索引不超过桶容量
        return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }
    // resize扩容函数：桶容量翻倍，旧元素进新桶
    private void resize() {
        Node<K, V>[] oldTable = table; // 旧桶
        int newCapacity = oldTable.length * 2; // 新容量二倍
        Node<K, V>[] newTable = new Node[newCapacity]; // 新的“骨架”
        table = newTable;
        size = 0; // 重置容量
        // 遍历复制
        for (Node<K, V> node : oldTable) {
            while (node != null) {
                put(node.key, node.value); // 复用put方法重新插入
                node = node.next;
            }
        }
    }
    // put函数：添加/更新键值对
    public void put(K key, V value) {
        int index = hash(key); // 步骤1————计算key对应的桶索引
        Node<K, V> current = table[index]; // 拿到该桶的头节点
        // 步骤2————遍历桶内链表，检查key是否已存在
        while (current != null) {
            if (current.key.equals(key)) { // key已存在
                current.value = value; // 更新value
                return; // 直接结束，不需要后续操作
            }
            current = current.next; // 没找到，继续看下一个节点
        }
        // 步骤3————key不存在，创建新节点并插入链表末尾
        Node<K, V> newNode = new Node<>(key, value);
        if (table[index] == null) {
            table[index] = newNode; // 桶为空，新节点直接做头节点
        } else {
            // 桶不为空，找到链表最后一个节点，把新节点插在后面
            Node<K, V> tail = table[index];
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = newNode;
        }
        size++; // 键值对数量+1
        // 步骤4————判断是否需要扩容（size大于等于容量×负载因子）
        if (size >= table.length * LOAD_FACTOR) {
            resize();
        }
    }

    // get函数，key查value
    public V get(K key) {
        int index = hash(key); //计算索引
        Node<K, V> current = table[index];
        // 链表遍历找 key
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null; // 遍历完没找到，返回null
    }
    // 测试一下
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>();
        // put，size
        map.put("张三", 18);
        map.put("李四", 20);
        System.out.println("put后长度：" + map.size());
        // 更新
        map.put("张三", 19);
        System.out.println("更新后：" + map.get("张三"));
        // get
        System.out.println("李四的年龄：" + map.get("李四"));
        // get不存在的
        System.out.println("王五的年龄：" + map.get("王五"));
    }
}

六、哈希表面试考点

代码内容到此结束了，我整理了一些哈希表的高频考点，简写了答案！
1、HashMap 的数据结构是什么？
（数组 + 链表 / 红黑树，JDK1.8 后链表过长转红黑树）
2、哈希冲突是什么？如何解决？
（不同 key 映射到同一索引；拉链法、开放地址法等，HashMap 用拉链法）
3、HashMap 的 put 流程是怎样的？
（计算 hash → 找索引 → 判断空桶或遍历链表 → 插入/更新 → 判断扩容）
4、为什么数组长度必须是 2 的幂？
（方便位运算取模，扩容时元素位置要么不变要么移动 oldCap，减少计算）
5、HashMap 的扩容机制（resize）？
（容量翻倍，重新计算元素位置；JDK1.8 优化为判断 hash & oldCap）
6、hash 函数如何设计？为什么要用高低位异或？
（让高位参与运算，减少碰撞，使分布更均匀）
7、HashMap 是线程安全的吗？多线程下有什么问题？
（不安全，并发 put 可能导致数据丢失、死循环（JDK1.7 头插法），可用 ConcurrentHashMap）
8、负载因子为什么是 0.75？
（时间与空间的权衡，过大增加碰撞概率，过小浪费空间，0.75 是经过实验得出的）
9、HashMap 中 key 为 null 的处理？
（JDK 中 null 的 hash 为 0，存在 table[0] 位置，简化版可以类似处理，或直接不允许 null）
10、equals 和 hashCode 在 HashMap 中的作用？
（hashCode 确定桶位置，equals 在桶内查找具体 key；二者必须一致）