📖 目录

  1. 前言
  2. 二叉搜索树（BST）详解
    • 2.1 定义与性质
    • 2.2 核心操作：查找、插入、删除
    • 2.3 二叉搜索树完整实现代码
    • 2.4 性能分析
    • 2.5 与 Java 集合的关系
  3. Map 集合体系全面解析
    • 3.1 Map 接口核心特点
    • 3.2 Map.Entry 键值对封装
    • 3.3 常用方法速查表
    • 3.4 TreeMap vs HashMap 对比
    • 3.5 TreeMap 实战代码
  4. Set 集合体系全面解析
    • 4.1 Set 核心特性
    • 4.2 常用方法速查表
    • 4.3 TreeSet vs HashSet 对比
    • 4.4 TreeSet 实战代码
  5. 哈希表（Hash Table）原理精讲
    • 5.1 哈希表核心思想
    • 5.2 哈希冲突与避免策略
    • 5.3 冲突解决：闭散列 vs 开散列
    • 5.4 自定义哈希桶（极简 HashMap）手写代码
    • 5.5 性能分析
    • 5.6 与 Java 集合的关联
  6. 高频 OJ 刷题方向
  7. 总结

1. 前言

在 Java 开发与面试中，Map 和 Set 是永远绕不开的核心集合。它们负责高效查找、去重、键值映射，底层依赖三大数据结构：

  • 二叉搜索树 / 红黑树
  • 哈希表（哈希桶）

本文从零开始，带你吃透原理、手写代码、掌握场景，彻底搞定 Map/Set。

2. 二叉搜索树（BST）详解

2.1 定义与性质

二叉搜索树（Binary Search Tree，BST）也叫二叉排序树，满足三条规则：

  1. 左子树所有节点值 < 根节点值
  2. 右子树所有节点值 > 根节点值
  3. 左右子树也必须是二叉搜索树

2.2 核心操作

  • 查找：比根小走左，比根大走右，相等即找到。
  • 插入：按查找逻辑走到空位置，插入新节点。
  • 删除（面试重点）：
    1. 无左孩子 → 右孩子顶替
    2. 无右孩子 → 左孩子顶替
    3. 左右都有 → 找右子树最小节点替换，再删除替换节点

2.3 二叉搜索树完整实现代码（可直接运行）

java

运行

/**
 * 二叉搜索树 BST 完整实现
 * 包含：查找、插入、删除
 */
public class BinarySearchTree {
    // 树节点结构
    public static class BSTNode {
        int key;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }
    }

    // 根节点
    private BSTNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // ==================== 查找 ====================
    public BSTNode find(int key) {
        BSTNode current = root;
        while (current != null) {
            if (key == current.key) {
                return current;
            } else if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    // ==================== 插入 ====================
    public boolean add(int key) {
        if (root == null) {
            root = new BSTNode(key);
            return true;
        }

        BSTNode current = root;
        BSTNode parent = null;
        while (current != null) {
            if (key == current.key) {
                // 重复值不插入
                return false;
            } else if (key < current.key) {
                parent = current;
                current = current.left;
            } else {
                parent = current;
                current = current.right;
            }
        }

        BSTNode newNode = new BSTNode(key);
        if (key < parent.key) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        return true;
    }

    // ==================== 删除 ====================
    public boolean delete(int key) {
        BSTNode current = root;
        BSTNode parent = null;

        // 定位待删除节点与父节点
        while (current != null) {
            if (key == current.key) {
                break;
            } else if (key < current.key) {
                parent = current;
                current = current.left;
            } else {
                parent = current;
                current = current.right;
            }
        }

        // 不存在则删除失败
        if (current == null) {
            return false;
        }

        deleteNode(parent, current);
        return true;
    }

    // 删除节点具体逻辑
    private void deleteNode(BSTNode parent, BSTNode cur) {
        // 1. 左孩子为空
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        }
        // 2. 右孩子为空
        else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        }
        // 3. 左右孩子都存在
        else {
            // 找右子树最小节点
            BSTNode minP = cur;
            BSTNode minNode = cur.right;
            while (minNode.left != null) {
                minP = minNode;
                minNode = minNode.left;
            }

            // 替换值
            cur.key = minNode.key;

            // 删除替代节点
            if (minP == cur) {
                minP.right = minNode.right;
            } else {
                minP.left = minNode.right;
            }
        }
    }
}

2.4 性能分析

  • 最优（完全二叉树）：O(logN)
  • 最差（退化成单链）：O(N)

为了解决失衡问题，Java 使用红黑树（平衡二叉搜索树）保证稳定 O (logN)。

2.5 与 Java 集合关系

  • TreeMap / TreeSet 底层 = 红黑树
  • 有序、可排序、稳定高效

3. Map 集合体系全面解析

3.1 Map 接口核心特点

  • 不继承 Collection
  • 存储 Key-Value 键值对
  • Key 唯一不重复，Value 可重复

3.2 Map.Entry<K,V>

Map 的内部接口，用来封装一个键值对：

  • getKey() 获取键
  • getValue() 获取值
  • setValue(V) 修改值

3.3 常用方法速查表

表格

方法 功能
V put(K, V) 添加 / 覆盖键值对
V get(Object) 根据键取值
V remove(Object) 删除指定键
Set<K> keySet() 获取所有键
Set<Map.Entry<K,V>> entrySet() 获取所有键值对
boolean containsKey(Object) 判断是否包含键

3.4 TreeMap vs HashMap 对比

表格

特性 TreeMap HashMap
底层结构 红黑树 哈希桶
时间复杂度 O(logN) O(1)
有序性 Key 有序 无序
Null Key 不允许 允许一个
适用场景 需要排序 追求最快查询

3.5 TreeMap 实战代码

java

运行

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, String> map = new TreeMap<>();

        // 添加数据
        map.put("林冲", "豹子头");
        map.put("鲁智深", "花和尚");
        map.put("武松", "行者");

        // 获取与判断
        System.out.println(map.get("鲁智深"));
        System.out.println(map.containsKey("林冲"));

        // 遍历键值对
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " → " + entry.getValue());
        }
    }
}

4. Set 集合体系全面解析

4.1 Set 核心特性

  • 继承自 Collection
  • 只存 Key，不存 Value
  • 自动去重
  • 底层直接复用 Map 实现

4.2 常用方法速查表

表格

方法 功能
boolean add(E) 添加元素（重复失败）
boolean contains(Object) 判断是否存在
boolean remove(Object) 删除元素
int size() 元素个数
boolean isEmpty() 是否为空

4.3 TreeSet vs HashSet 对比

表格

特性 TreeSet HashSet
底层 红黑树 哈希桶
有序 有序 无序
Null 不允许 允许
效率 O(logN) O(1)

4.4 TreeSet 实战代码

java

运行

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();

        set.add("apple");
        set.add("banana");
        set.add("apple"); // 自动去重

        System.out.println(set.contains("apple"));
        System.out.println(set);
    }
}

5. 哈希表（Hash Table）原理精讲

5.1 哈希表核心思想

通过哈希函数，把 Key 直接映射到数组下标，实现近似 O (1) 的查找、插入、删除。

5.2 哈希冲突

不同 Key 计算出相同下标 → 哈希冲突。冲突无法避免，只能降低。

降低方式：

  • 设计优秀哈希函数
  • 控制负载因子（Java 默认 0.75）
  • 合理扩容

5.3 冲突解决

  1. 闭散列（开放地址）：线性探测、二次探测
  2. 开散列（哈希桶）：数组 + 链表（Java HashMap 采用）

5.4 自定义哈希桶（极简 HashMap）手写代码

java

运行

/**
 * 自定义哈希桶（数组 + 链表）
 * 实现：put、get、扩容、负载因子控制
 */
public class MyHashMap {
    // 链表节点
    private static class HashNode {
        int key;
        int value;
        HashNode next;

        public HashNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    private HashNode[] table;
    private int size;
    private static final double LOAD_FACTOR = 0.75;

    public MyHashMap() {
        table = new HashNode[8];
        size = 0;
    }

    // 计算负载因子
    private double currentLoadFactor() {
        return size * 1.0 / table.length;
    }

    // 扩容
    private void resize() {
        HashNode[] newTable = new HashNode[table.length * 2];
        for (int i = 0; i < table.length; i++) {
            HashNode cur = table[i];
            while (cur != null) {
                HashNode next = cur.next;
                int index = cur.key % newTable.length;
                cur.next = newTable[index];
                newTable[index] = cur;
                cur = next;
            }
        }
        table = newTable;
    }

    // 添加/修改
    public int put(int key, int value) {
        int index = key % table.length;

        // 查找更新
        HashNode cur = table[index];
        while (cur != null) {
            if (cur.key == key) {
                int oldVal = cur.value;
                cur.value = value;
                return oldVal;
            }
            cur = cur.next;
        }

        // 头插法新节点
        HashNode newNode = new HashNode(key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;

        // 超过负载因子扩容
        if (currentLoadFactor() >= LOAD_FACTOR) {
            resize();
        }
        return -1;
    }

    // 获取
    public int get(int key) {
        int index = key % table.length;
        HashNode cur = table[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
}

5.5 性能分析

  • 理想情况：O(1)
  • 冲突严重：退化为 O (N)，Java 会转为红黑树优化

5.6 与 Java 集合的关联

  • HashMap / HashSet = 哈希桶
  • 链表长度 ≥ 8 → 转为红黑树
  • 自定义对象作 Key 必须重写 hashCode () + equals ()

6. 总结

  1. 二叉搜索树是 TreeMap/TreeSet 的基础，红黑树保证稳定效率。
  2. Map 存键值对，Set 存单值自动去重。
  3. 有序选 Tree 系列，高效选 Hash 系列。
  4. 哈希表依靠哈希函数 + 冲突解决实现 O (1) 效率。
  5. 自定义 Key 必须重写 hashCode + equals。
# java # 散列表 # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

Claude API + Python实战：结构化输出后，如何拦住“看起来正确”的JSON

avatar AI编程社区
cover

当 AI 修图师装上“万能插头“：MCP 如何改变修图工作流

avatar AI编程社区
cover

2026年8月开发者实战指南：ChatGPT Plus / Pro + Codex 如何协同完成需求分析、编码、测试、调试与代码审查

avatar AI编程社区