一、引言

    也是来到了数据结构的末尾了关于map和set的东西其实是很多的，并且难度也不小，我们学完以后要熟练的知道哈希冲突和冲突避免这两个我个人认为是非常重点的，这篇博客也会在这两个内容大费周章，其实搜索树也是比较重要所以关于搜索树的内容会单独出一篇博客，那么下面来开始讲解吧。

二、Key-Val模型

    在说Map和Set之前我们先来聊聊什么是Key-Val模型，简单来说其实就是对应的一个关系，一个key会对应一个val值，举一个例子学生最常用的学号，学号都是对应学生名字的，就可以把学号看成key名字看成val，学号和名字之间的对应关系就是我们的一个Key-Val模型，map就是存储了Key-Val的对应而set则是只存储了key。要注意的是key是不可以重复的也就相当于一个学号不可能指两个学生。

三、Map

3.1 Map 核心概念

Map 是 Java 集合框架中专门用于存储 ** 键值对（Key-Value）** 的接口，它和 List、Set 不同，不是单列集合，而是双列集合。简单理解就是：通过 key 来找 value。

1. 键值对结构

   • 一个 key 唯一对应一个 value
   • key 是唯一标识，不允许重复
   • value 可以重复，也可以为 null
   • 同一个 key 多次 put，只会覆盖旧的 value，不会新增元素

2. key 的约束

   • HashMap 中 key 可以为 null，但最多只能有一个 null key
   • TreeMap 中 key 不能为 null，且必须是可比较的类型
   • 自定义类作为 key 时，必须正确重写 equals() 和 hashCode()，否则无法正常判重、查找

3. 无序与有序

   • HashMap：底层哈希表，元素无序，存取顺序不一致
   • TreeMap：底层红黑树，元素按键有序，默认升序

4. 访问方式

   • Map 不能直接通过 for-each 遍历，必须借助：
     • keySet ()：获取所有 key 的集合
     • values ()：获取所有 value 的集合
     • entrySet ()：获取所有 key-value 映射关系的集合

5. 效率特点

   • HashMap：增删改查平均时间复杂度 O(1)，效率极高
   • TreeMap：增删改查稳定 O(logN)，适合需要排序的场景

6. 线程安全

   • HashMap 和 TreeMap 都是线程不安全的
   • 多线程环境下不能直接使用，否则会出现数据错乱、扩容死循环等问题

    Map是一个接口类是不能之间实例化的，所以有两个类实现了Map<K,V>接口分别是HashMap和TreeMap这两个都继承了Map的方法，下面先把常用的方法列出来。

Java Map 常用方法大全
方法名	语法格式	功能描述	示例代码	返回值	使用场景
put	put(K key, V value)	向Map中添加键值对；若键已存在，则覆盖原有值	map.put("name", "张三"); map.put("age", 20);	返回键对应的旧值（键不存在时返回null）	初始化/动态添加键值对、更新已有键的配置信息
get	get(Object key)	根据指定的键获取对应的值	String name = map.get("name"); Integer age = map.get("age");	返回键对应的值；键不存在时返回null	查询指定键的对应值，是最常用的查询操作
containsKey	containsKey(Object key)	检查Map中是否包含指定的键	boolean hasName = map.containsKey("name");	包含键返回true，否则返回false	判断键是否存在，避免get返回null的空指针异常
containsValue	containsValue(Object value)	检查Map中是否包含指定的值	boolean hasZhangSan = map.containsValue("张三");	包含值返回true，否则返回false	反向查找值是否存在，校验值的唯一性
remove	remove(Object key)	删除指定键对应的键值对	Integer oldAge = map.remove("age");	返回被删除的值；键不存在时返回null	移除不再需要的键值对，清理无效数据
getOrDefault	getOrDefault(Object key, V defaultValue)	获取指定键的值，若键不存在则返回默认值	String address = map.getOrDefault("address", "未知地址");	键存在返回对应值，不存在返回指定的默认值	简化空值处理，避免显式的containsKey判断
forEach	forEach(BiConsumer<? super K, ? super V> action)	遍历Map中的所有键值对，执行指定操作	map.forEach((k, v) -> System.out.println(k + ": " + v));	无返回值	简洁遍历键值对，替代传统的entrySet循环
merge	merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)	合并键值对，键存在时用函数计算新值，不存在则直接插入	map.merge("score", 90, (oldVal, newVal) -> oldVal + newVal);	返回合并后的新值	数据聚合、累计计算，如统计相同键的数值总和
computeIfAbsent	computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)	键不存在时，通过函数计算值并插入Map，返回当前值	map.computeIfAbsent("id", k -> UUID.randomUUID().toString());	返回键对应的值（插入的新值或原有值）	延迟初始化，避免重复创建对象，如缓存场景
computeIfPresent	computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	键存在时，通过函数重新计算值并更新，返回新值	map.computeIfPresent("age", (k, v) -> v + 1);	键存在返回计算后的新值，不存在返回null	仅在键存在时更新值，避免无效的插入操作
keySet	keySet()	获取Map中所有键的Set集合	Set<String> keys = map.keySet();	返回包含所有键的Set<K>集合	遍历所有键、批量处理键的场景
values	values()	获取Map中所有值的Collection集合	Collection<Object> values = map.values();	返回包含所有值的Collection<V>集合	遍历所有值、统计值的相关数据
entrySet	entrySet()	获取Map中所有键值对的Set集合	Set<Map.Entry<String, Object>> entries = map.entrySet();	返回包含所有键值对的Set<Map.Entry<K,V>>集合	传统遍历键值对、需要同时操作键和值的场景
isEmpty	isEmpty()	检查Map是否为空（无任何键值对）	boolean empty = map.isEmpty();	Map为空返回true，否则返回false	判断Map是否有数据，避免空遍历
size	size()	获取Map中键值对的数量	int count = map.size();	返回键值对的数量（int类型）	统计Map的元素个数、判断数据规模
clear	clear()	清空Map中所有的键值对	map.clear();	无返回值	重置Map、清理所有数据
replace	replace(K key, V value)	仅当键存在时，替换对应的值	Integer oldAge = map.replace("age", 21);	键存在返回旧值，不存在返回null	仅更新已有键的值，避免误插入新键
replace	replace(K key, V oldValue, V newValue)	仅当键对应的值等于oldValue时，才替换为newValue	boolean success = map.replace("name", "张三", "李四");	替换成功返回true，否则返回false	并发场景下的安全更新，避免覆盖其他线程修改的值

3.2 TreeMap

    TreeMap的底层是红黑树实现的，并且key是要可以比较的数据因为要靠key的大小顺序做排序，存储，查找，如果不是可以比较的数据的话会直接抛出异常。所以当在实例化的时候如果传的是自定义的类的话要在构造的时候传入比较器。下面是TreeMap的使用案例。

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建一个 TreeMap，默认按键的自然顺序排序（升序）
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        // 向 TreeMap 中添加键值对
        treeMap.put("Apple", 10);
        treeMap.put("Banana", 20);
        treeMap.put("Cherry", 30);
        treeMap.put("Date", 40);

        // 遍历 TreeMap 并打印键值对（按键升序）
        System.out.println("TreeMap 内容（升序）：");
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 获取第一个和最后一个键值对
        System.out.println("\n第一个键值对: " + treeMap.firstEntry());
        System.out.println("最后一个键值对: " + treeMap.lastEntry());

        // 使用自定义排序（降序）
        TreeMap<String, Integer> reverseTreeMap = new TreeMap<>((a, b) -> b.compareTo(a));
        reverseTreeMap.putAll(treeMap);

        System.out.println("\nTreeMap 内容（降序）：");
        for (Map.Entry<String, Integer> entry : reverseTreeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 查找键的范围（"Banana" 到 "Date"）
        System.out.println("\n键范围查询（Banana 到 Date）：");
        Map<String, Integer> subMap = treeMap.subMap("Banana", "Date");
        for (Map.Entry<String, Integer> entry : subMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}
 

3.3哈希表（HashMap）

    顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键 码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log N)，搜索的效率取决于搜索过程中 元素的比较次数。

3.3.1 哈希冲突

    冲突的概念就是对于两个数据元素的关键字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。既然有了冲突我们就要去避免去解决。

    关于避免我们要重点了解负载因子，先说定义负载因子α=填入表中的元素/散列表的长度。举一个简单例子一辆卡车利用装10t的货但是平常肯定不会装那么多吧一般就装8t或者7t，我们用8/10=0.8，0.8就是负载因子。如果表长固定的话那么α越大发生冲突的概率也越大，反之α越小冲突的概率也就小了。所以当冲突到达无法忍受的时候就要降低负载因子，这个时候就可以去调整哈希表的数组大小来降低α。另外一种避免方法就是去重新设计合理的哈希函数了常见的哈希函数有两种除了上面的还有是Hash（Key）= A*Key + B也称为直接定制法，这里不做过多讲解。

    那么也是来到了重点冲突-解决了，解决哈希冲突最常见有两种方法闭散列合开散列，下面一一来说明。

    闭散列：

    闭散列也叫开放定址法。当发生哈希冲突时，如果哈希表还没满，就说明表中仍有空位置，此时可以把 key 存放到冲突位置的下一个可用空位置。常见的探测方式有两种：线性探测和二次探测。

线性探测

    就是顺着下标依次往后找，遇到空位就插入。比如插入 16 时，下标 6 已经被占用，就依次尝试 7、8…… 直到找到空位。但线性探测有明显缺陷：冲突的元素会扎堆聚集在一起，形成 “冲突堆积”，后续查找、插入效率都会明显下降。另外，采用闭散列处理冲突时，不能直接物理删除元素。比如删除下标 6 的元素后，原本存在 16 就可能因为空位导致查找中断，找不到了。因此线性探测通常使用标记伪删除，而不是真正移除节点。

二次探测

    为了缓解线性探测的堆积问题，二次探测改用平方步长寻找下一个位置，而不是逐个往后找。探测公式如下：

Hi​=(H0​+i2)%m

也可使用反向探测：Hi​=(H0​−i2)%m

其中：

H0​：key 通过哈希函数计算出的初始下标

i：冲突次数，从 1 开始递增

m：哈希表长度

第一次冲突步长为 12=1，第二次为 22=4，第三次为 32=9……这样元素不会密集挤在相邻位置，能有效减少冲突堆积。

但二次探测依旧属于闭散列，空间利用率低、删除麻烦、需要伪删除等问题依然存在，因此在实际工程中很少使用。

闭散列最大的问题就是空间利用率较低，必须预留大量空位来降低冲突概率，这也是它不如开散列实用的主要原因。

   开散列（重点）：

    开散列也叫链地址法、拉链法，是HashMap 底层真正采用的哈希冲突解决方案，也是工业界最常用、效率最高的冲突解决方式，完全弥补了闭散列空间利用率低、查找效率差的缺陷。

开散列核心思想

1. 哈希表底层依然是数组，每个数组位置不直接存储元素，而是存储一条链表 / 红黑树的头节点；
2. 通过哈希函数计算出下标后，把元素直接挂在对应下标的链表上；
3. 多个产生哈希冲突的元素，全部存放在同一个下标对应的链表中。

一句话总结：数组 + 链表 / 红黑树，冲突的元素串成一条链子挂在数组上。

 开散列工作流程（以插入为例）

1. 计算 key 的哈希值，得到数组下标 index；
2. 查看 index 位置是否为空：
   • 为空：直接创建节点，放在该位置作为链表头；
   • 不为空：说明发生哈希冲突，将新节点尾插 / 头插到这条链表上。

对比项	闭散列（开放定址法）	开散列（链地址法）
空间利用率	极低（必须留大量空位防冲突）	极高（链表可无限挂元素）
删除操作	麻烦，必须用伪删除标记	简单，直接删除链表节点
冲突堆积	严重，会导致整条数组探测	只影响当前下标链表，不干扰其他位置
实现复杂度	简单	稍复杂，但更实用
实际工程使用	极少使用	HashMap、HashSet 底层标准实现

 

代码模拟实现：

/**
 * 手写 哈希桶(开散列/拉链法) 实现
 * 底层结构：数组 + 链表
 * 作用：模拟 HashMap 底层核心原理
 */
public class HashBuck {

    /**
     * 内部节点类
     * 每个节点存储 key-value 键值对
     * 并且带有 next 指针，用于挂链表
     */
    static class Node {
        public int key;  // 键（唯一，不能重复）
        public int val;  // 值
        public Node next;// 指向链表下一个节点的指针

        // 构造方法：创建一个节点
        public Node(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }

    // 当前哈希表中【实际存储的元素个数】
    public int Usize;

    // 哈希表的核心：数组（每个位置是链表的头节点，也叫“桶”）
    // 初始长度 10
    private Node[] array = new Node[10];

    /**
     * 插入 / 修改 方法
     * @param key 键
     * @param val 值
     * 逻辑：
     * 1. 根据 key 计算数组下标
     * 2. 遍历链表，看 key 是否已经存在
     *    - 存在：覆盖 value
     *    - 不存在：尾插法插入新节点
     * 3. 插入成功后 Usize++
     * 4. 判断负载因子，超过 0.75 就扩容
     */
    public void push(int key, int val) {
        // 1. 哈希函数：key % 数组长度 → 计算当前 key 应该放在哪个下标
        int index = key % array.length;

        // 2. 从当前下标的链表头开始遍历
        Node cur = array[index];
        Node temp = null; // 用来记录链表的最后一个节点（方便尾插）

        // 3. 遍历链表，查找 key 是否已经存在
        while (cur != null) {
            // 如果 key 已存在，直接覆盖 val，结束方法
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            temp = cur;    // temp 跟着 cur 走，始终指向当前节点的前一个
            cur = cur.next;// cur 往后走
        }

        // 4. 代码走到这里 → key 不存在，需要新建节点
        Node node = new Node(key, val);

        // 5. 尾插法
        if (temp == null) {
            // temp == null 说明链表为空 → 新节点直接作为链表头
            array[index] = node;
        } else {
            // 链表不为空 → 把新节点挂在最后一个节点后面
            temp.next = node;
        }

        // 6. 元素个数 +1
        Usize++;

        // 7. 判断负载因子是否 ≥ 0.75
        // 如果超过，说明冲突概率变高，需要扩容
        if (find() >= 0.75) {
            resize();
        }
    }

    /**
     * 扩容方法
     * 逻辑：
     * 1. 创建新数组，长度是原来的 2 倍
     * 2. 遍历老数组的每一个位置
     * 3. 把每个位置上的链表节点【重新哈希】到新数组
     * 4. 最后让 array 指向新数组
     */
    private void resize() {
        // 1. 新数组长度 = 旧数组 * 2
        Node[] newArray = new Node[array.length * 2];

        // 2. 遍历旧数组的每一个下标
        for (int i = 0; i < array.length; i++) {
            // 拿到旧数组当前下标的链表头
            Node cur = array[i];

            // 3. 遍历这条链表上的所有节点
            while (cur != null) {
                // 记录当前节点的下一个节点（防止断链）
                Node curN = cur.next;

                // 4. 重新计算在新数组中的下标
                int newIndex = cur.key % newArray.length;

                // 5. 采用【头插法】把节点插入到新数组
                // 把当前节点的 next 指向新数组下标处的链表头
                cur.next = newArray[newIndex];
                // 新数组下标处的头节点变成当前节点
                newArray[newIndex] = cur;

                // 继续处理下一个节点
                cur = curN;
            }
        }

        // 6. 扩容完成！让哈希表底层数组指向新数组
        array = newArray;
    }

    /**
     * 计算负载因子
     * 负载因子 = 实际元素个数 / 数组长度
     */
    private double find() {
        return Usize * 1.0 / array.length;
    }

    /**
     * 根据 key 获取对应的 value
     * @return 找到返回 val，没找到返回 -1
     */
    public int getvalue(int key) {
        // 1. 计算 key 对应的下标
        int index = key % array.length;

        // 2. 遍历该下标下的链表
        Node cur = array[index];
        while (cur != null) {
            // 找到 key，返回对应 val
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }

        // 3. 没找到，返回 -1
        return -1;
    }
}

核心逻辑总结：

1. 底层结构

   • 数组 + 链表（开散列 / 拉链法）
   • 每个数组位置 = 一个桶，桶里挂冲突的节点

2. 插入逻辑

   • 哈希函数算下标
   • 遍历链表看 key 是否存在
   • 存在则覆盖，不存在则尾插
   • 负载因子 ≥ 0.75 自动扩容

3. 扩容逻辑

   • 新数组 = 旧数组 ×2
   • 所有节点重新哈希
   • 采用头插法放入新数组

4. 查找逻辑

   • 算下标 → 遍历链表 → 比较 key → 返回值

下面再给一段Hash Map的使用案例代码。

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // 1. 创建 HashMap 对象
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 2. 添加元素 put(key, value)
        hashMap.put("Apple", 10);
        hashMap.put("Banana", 20);
        hashMap.put("Cherry", 30);
        hashMap.put("Date", 40);
        // key 重复会覆盖旧值
        hashMap.put("Apple", 99);

        // 3. 根据 key 获取 value
        System.out.println("Apple 对应的 value：" + hashMap.get("Apple"));

        // 4. 判断是否包含某个 key / value
        System.out.println("是否包含 Banana：" + hashMap.containsKey("Banana"));
        System.out.println("是否包含 value=30：" + hashMap.containsValue(30));

        System.out.println("=====================================");

        // 5. 遍历方式1：entrySet 遍历（最常用）
        System.out.println("entrySet 遍历：");
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        System.out.println("=====================================");

        // 6. 遍历方式2：keySet 遍历 key，再 get value
        System.out.println("keySet 遍历：");
        for (String key : hashMap.keySet()) {
            System.out.println(key + " : " + hashMap.get(key));
        }

        System.out.println("=====================================");

        // 7. 删除元素
        hashMap.remove("Cherry");
        System.out.println("删除 Cherry 后大小：" + hashMap.size());

        // 8. 清空集合
        // hashMap.clear();
    }
}

 

四、Set

    Set 和 Map 可以说是亲兄弟，在 Java 中，Set 底层就是基于 Map 实现的，这一点非常关键！

    Set 存储的特点非常纯粹：只存储 key，不存储 value，并且 key 绝对不允许重复，底层原理和 Map 完全一致，对应的实现类也是 HashSet 和 TreeSet，分别对应 HashMap 和 TreeMap。

4.1 Set 核心概念

Set 是一个接口类，不能直接实例化，底层完全依赖 Map 实现：

• HashSet：底层是 HashMap，只存 key，value 统一存一个固定的 Object 对象
• TreeSet：底层是 TreeMap，只存 key，保证元素有序且不重复

核心特点：

1. 元素不重复：存入相同元素会直接覆盖，保证唯一性
2. 无索引：不能通过下标访问元素
3. 无序 / 有序：HashSet 无序，TreeSet 有序（和 HashMap、TreeMap 规则一致）
4. 允许存 null：HashSet 允许存一个 null，TreeSet 不允许存 null（需要比较）

    下面是Set的方法：

方法名	语法格式	功能描述	示例代码	返回值	使用场景
add	add(E e)	向 Set 中添加元素，重复则不添加	set.add ("张三");	成功返回 true，失败 false	存入唯一元素
remove	remove(Object o)	删除 Set 中的指定元素	set.remove ("张三");	成功返回 true，失败 false	删除指定元素
contains	contains(Object o)	判断 Set 中是否包含指定元素	boolean f = set.contains ("张三");	包含返回 true，否则 false	判断元素是否存在
isEmpty	isEmpty()	判断 Set 是否为空	boolean empty = set.isEmpty();	空返回 true，否则 false	判空
size	size()	获取 Set 中元素个数	int count = set.size();	元素个数 int	统计元素数量
clear	clear()	清空 Set 所有元素	set.clear();	无返回值	清空数据
forEach	forEach(Consumer c)	遍历 Set 所有元素	set.forEach(s->System.out.println(s));	无返回值	简洁遍历
iterator	iterator()	获取迭代器，遍历元素	Iterator it = set.iterator();	迭代器对象	传统遍历

4.2 TreeSet

TreeSet和TreeMap是很相似的 底层是 TreeMap（红黑树），存储的元素必须可比较，默认按照自然顺序升序排序，自定义类必须传入比较器，否则抛出异常。下面是使用案例的代码。

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // 创建 TreeSet，默认升序排序
        TreeSet<String> treeSet = new TreeSet<>();

        // 添加元素
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Cherry");
        treeSet.add("Date");

        // 遍历（有序）
        System.out.println("TreeSet 升序：");
        for (String s : treeSet) {
            System.out.println(s);
        }

        // 第一个、最后一个元素
        System.out.println("第一个元素：" + treeSet.first());
        System.out.println("最后一个元素：" + treeSet.last());

        // 自定义比较器（降序）
        TreeSet<String> reverseSet = new TreeSet<>((a, b) -> b.compareTo(a));
        reverseSet.addAll(treeSet);
        System.out.println("\nTreeSet 降序：");
        reverseSet.forEach(System.out::println);
    }
}

4.3 HashSet

    HashSet 底层是 HashMap（哈希表 + 开散列 / 拉链法），是我们最常用的 Set 实现类。

4.3.1 HashSet 底层原理

1. 底层数组 + 链表 / 红黑树，和 HashMap 结构完全一样
2. 调用 add(e) 时，本质是调用 map.put(e, PRESENT)，PRESENT 是一个固定的静态 Object 对象，所有 key 共用这个 value
3. 哈希冲突、负载因子、扩容机制、树化规则 全部和 HashMap 一模一样
4. 查找、添加、删除效率平均都是 O(1)

4.3.2 HashSet 核心特点

    1.无序：不保证存取顺序一致

    2.不重复：key 唯一

    3.高效：哈希表结构，增删改查极快

    4.允许一个 null 值

     下面给一个使用案例代码

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        // 创建 HashSet
        HashSet<String> hashSet = new HashSet<>();

        // 添加元素（重复元素不会添加成功）
        hashSet.add("Java");
        hashSet.add("C++");
        hashSet.add("Python");
        hashSet.add("Java"); // 重复，添加失败

        // 遍历
        System.out.println("HashSet 内容：");
        hashSet.forEach(System.out::println);

        // 判断是否包含
        System.out.println("是否包含 Java：" + hashSet.contains("Java"));

        // 删除元素
        hashSet.remove("C++");
        System.out.println("删除后大小：" + hashSet.size());
    }
}

4.3.3 HashSet 底层简易实现

    为了让你彻底理解，我改写出一个 简易 HashSet，会发现和刚才的HashBuck十分相似，你会发现代码几乎一模一样，只是不存 value。

/**
 * 手写 HashSet 模拟实现
 * 底层 = 哈希桶(开散列)
 * 只存 key，不存 value
 */
public class MyHashSet {
    static class Node {
        public int key;
        public Node next;

        public Node(int key) {
            this.key = key;
        }
    }

    public int Usize;
    private Node[] array = new Node[10];

    // 添加元素（Set 核心方法）
    public void add(int key) {
        int index = key % array.length;
        Node cur = array[index];
        Node temp = null;

        // 遍历查重，重复则不添加
        while (cur != null) {
            if (cur.key == key) {
                return; // 重复，直接返回
            }
            temp = cur;
            cur = cur.next;
        }

        // 不重复，尾插
        Node node = new Node(key);
        if (temp == null) {
            array[index] = node;
        } else {
            temp.next = node;
        }

        Usize++;
        if (find() >= 0.75) {
            resize();
        }
    }

    // 判断是否包含
    public boolean contains(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 删除元素
    public void remove(int key) {
        int index = key % array.length;
        Node cur = array[index];
        Node prev = null;
        while (cur != null) {
            if (cur.key == key) {
                if (prev == null) {
                    array[index] = cur.next;
                } else {
                    prev.next = cur.next;
                }
                Usize--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    // 扩容（和 HashBuck 完全一样）
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node curN = cur.next;
                int newIndex = cur.key % newArray.length;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curN;
            }
        }
        array = newArray;
    }

    // 负载因子
    private double find() {
        return Usize * 1.0 / array.length;
    }

    // 获取大小
    public int size() {
        return Usize;
    }
}

五、总结

    这篇博客我们完整学完了 Java 集合框架中最核心的 Map 和 Set，从基础模型到底层原理、从使用方法到手写实现，把重点难点全部梳理清楚了，这里做一个整体总结，方便大家复习记忆。

基础模型：

1. Map 和 Set 都基于 Key-Val 模型，Map 存储键值对，Set 只存储唯一 key。
2. key 绝对不允许重复，重复添加会覆盖或直接忽略，这是它们最核心的特性。

Map 体系：

    1.Map 是双列集合接口，不能直接实例化，常用实现类：HashMap、TreeMap。

    2.TreeMap：底层红黑树，key 必须可比较，有序，增删改查效率 O (logN)。

    3.HashMap：底层哈希表 + 开散列（拉链法），无序，平均效率 O (1)，是日常开发最常用的实现。

    4.两者都线程不安全，多线程不能直接使用。

哈希核心（重中之重）：

1. 哈希表通过哈希函数建立 key 和存储位置的映射，实现快速查找。
2. 哈希冲突是不可避免的，解决方式主要有闭散列和开散列。
3. 闭散列：开放定址法，缺点是空间利用率低、删除麻烦，实际很少用
4. 开散列（拉链法）：数组 + 链表 / 红黑树，删除方便、效率高，是 HashMap 底层标准方案。
5. 负载因子默认 0.75，达到阈值自动扩容，用来控制冲突概率。

Set 体系：

1. Set 是单列集合，底层完全依赖 Map 实现，只存 key，不存 value。
2. TreeSet 对应 TreeMap，有序、元素唯一。
3. HashSet 对应 HashMap，无序、高效、元素唯一。
4. 手写 HashSet 与手写哈希桶逻辑几乎一致，只是去掉了 value 存储。

使用与选择：

1. 需要有序存储、范围查找 → 选 TreeMap / TreeSet。
2. 需要最高效率、快速增删改查 → 选 HashMap / HashSet。
3. 哈希冲突、负载因子、扩容、树化规则，Map 和 Set 完全通用。

一句话终极总结：

    Map 存键值对，Set 只存键；Tree 版有序，Hash 版高效；哈希冲突不可怕，拉链法（开散列）搞定它；掌握哈希原理与使用场景，就能完全吃透 Map 和 Set 核心！