1. 内容整体设计与思路拆解1.1 三个知识点为什么必须放在一起学很多初学者学 Java 集合的时候习惯把HashMap、TreeMap、HashSet、TreeSet当成四个独立的类去背背完就忘忘了再背。我个人觉得这是学习方法出了问题。如果你把底层的两棵“树”搞清楚——二叉搜索树和哈希表再看 Map 和 Set会发现它们根本不是四个类而是两套底层数据结构各自延伸出来的两个“壳”。也就是说HashMap的底层是哈希表HashSet内部就是包了一个HashMapTreeMap的底层是红黑树而红黑树是一种自平衡的二叉搜索树TreeSet内部就是包了一个TreeMap。所以整条链路其实是这样的哈希表 → HashMap → HashSet以及二叉搜索树 → 红黑树 → TreeMap → TreeSet。你在网上搜“JavaDataStructure---二叉搜索树哈希表Map和Set”这套题本质上就是想考察你能不能打通这条链路。从面试角度看这个标题也特别经典。我帮人模拟过不少技术面试凡是问集合相关的十个里有八个会从“HashMap 的底层原理”切入然后顺藤摸瓜问到hashCode和equals问到哈希冲突问到ConcurrentHashMap的锁粒度。而一旦问到有序的 Map就会绕到TreeMap和红黑树。你要是只背结论不啃原理大概率会被问穿。1.2 这篇文章能帮你解决什么这篇文章我打算用一条线串起来讲先搞懂二叉搜索树的核心操作再对比哈希表的核心机制最后看 Java 里的 Map 和 Set 怎么用代码落地。我还会把平时写代码时踩过的坑比如重写equals不重写hashCode会有什么后果、HashMap在并发环境下为什么不能用、TreeMap的 key 排序规则到底怎么定一并整理出来。内容定位比较适合三类读者准备校招或社招的 Java 开发者、工作中经常跟集合类打交道但没深究过原理的 CRUD 选手以及正在学数据结构的在校学生。如果你是纯零基础建议先掌握 Java 中类和对象的基本概念再来看这篇文章会更顺畅。2. 二叉搜索树有序数据的利器2.1 二叉搜索树的定义以及它为什么“有序”二叉搜索树Binary Search TreeBST是二叉树的一种它有一个非常严格的约束对于任意一个节点它的左子树中所有节点的值都小于该节点右子树中所有节点的值都大于该节点。而且这个约束是递归的也就是说每个子树本身也必须满足这个条件。你可以把二叉搜索树理解成一本“自动分好类的字典”根节点是中间某一页翻到这一页如果目标词比它小就往左翻比它大就往右翻。正是因为这种左小右大的结构二叉搜索树才拥有了一个特别有价值的特性——中序遍历结果是有序的。这个特性在真实开发里非常实用。假设你维护一个在线商城的商品列表需要随时按照价格升序输出商品用二叉搜索树存储一次中序遍历就能搞定时间复杂度是 O(n)不需要额外调用排序算法。class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; } }这个节点的定义非常简单只有一个整型值val和左右孩子指针。实际的代码里节点中通常会存放具体的对象比如商品对象然后按照对象的某个属性来构建搜索树。为了说明原理我用int类型作为示例。2.2 插入操作的三种情况与递归实现插入操作的思路算是最直观的从根节点出发如果待插入的值比当前节点小就往左子树走比当前节点大就往右子树走直到找到一个空位置把新节点挂上去。有一点需要特别强调二叉搜索树默认不存储重复值。如果插入的值已经在树中存在一般直接忽略或覆盖具体行为取决于你的业务语义。如果你想支持重复值可以在节点里加一个计数器字段。比如 Java 的TreeMap不支持重复 key就是直接覆盖旧值。public TreeNode insert(TreeNode root, int val) { if (root null) { return new TreeNode(val); } if (val root.val) { root.left insert(root.left, val); } else if (val root.val) { root.right insert(root.right, val); } return root; }这里用递归实现逻辑非常清爽。新手可能会有个疑问为什么插入后要return root其实是在递归回溯的过程中把新创建的节点或者更新后的子树重新赋给父节点的左/右引用。如果漏掉这一步新节点插入后立刻就会丢失谁也找不到它了。我见过好几个初学者在这里卡住所以写出来提醒一下。2.3 查找操作从 O(n) 到 O(log n) 的关键二分查找之所以快最大前提是数据有序。二叉搜索树的查找过程本质上就是二分查找的树形版本每比较一次搜索范围就缩小一半。但这里的“快”是有条件的我在 2.5 节会详细说退化的问题。public TreeNode search(TreeNode root, int target) { if (root null || root.val target) { return root; } if (target root.val) { return search(root.left, target); } else { return search(root.right, target); } }查找的代码不难真正重要的是理解它的时间复杂度在树比较平衡的情况下查找、插入、删除的平均时间复杂度都是 O(log n)n 是节点总数。比如 100 万条数据链表查找平均要走 50 万次而二叉搜索树只需要大约 20 次比较。这就是数据结构带来的指数级差距。生活中可以这么类比你去图书馆找一本指定书名的书如果图书是按字母摆放的你会按照字母区间缩小范围如果图书没有任何顺序你只能一本一本翻完整个书架。二叉搜索树干的就是“让数据自动按字母摆放”这件事。2.4 删除操作三种情况的完整讲解删除是二叉搜索树最复杂的操作也是面试中容易翻车的地方。麻烦之处在于删除一个节点后整棵树仍然必须保持“左小右大”的性质。一共分三种情况我分开说。情况一删除叶子节点。这个最简单直接移除即可什么都不用管。情况二删除只有一个子节点的节点。把这个节点的唯一子节点提上来顶替它的位置。就好比一个部门经理离职手底下只有一个员工直接让这个员工顶上就行。情况三删除有两个子节点的节点。这一步最绕。正确做法不是直接删掉它而是从它的右子树中找出最小的节点或者从左子树中找出最大的节点用这个节点的值覆盖待删除节点的值然后递归删除那个用于替换的节点。为什么可以这么做因为右子树的最小值一定大于右子树所有其他值但小于待删除节点右子树中除了它之外的所有值同时又大于待删除节点左子树的所有值所以它放上来之后树的顺序不会乱。左子树的最大值同理。public TreeNode delete(TreeNode root, int key) { if (root null) { return null; } if (key root.val) { root.left delete(root.left, key); } else if (key root.val) { root.right delete(root.right, key); } else { if (root.left null) { return root.right; } if (root.right null) { return root.left; } TreeNode minNode findMin(root.right); root.val minNode.val; root.right delete(root.right, root.val); } return root; } private TreeNode findMin(TreeNode node) { while (node.left ! null) { node node.left; } return node; }这里有个细节值得注意当待删除节点有两个孩子时我找的是右子树的最小值。如果右子树为空就不用走这个分支。实际开发中更常见的做法是找左子树的最大值效果一样。你甚至可以走完这两个分支后做一个随机选择对均衡性有点微弱的积极影响不过一般没必要这么花哨。2.5 后退问题成绩排序的隐藏风险二叉搜索树听起来很美但它有一个致命弱点如果在插入时数据已经有序树会退化成链表。比如你按 1 到 10 的顺序依次插入节点根节点是 1所有节点都成为右孩子树的高度变成 n查找的时间复杂度退化成 O(n)和链表没有区别。我在实际项目中遇到过几乎一模一样的场景。有个系统需要实时维护排行榜数据是按分数自然递增写入的如果直接使用二叉搜索树存储树就会严重右倾查询性能越来越差。解决的标准化方案就是用自平衡二叉搜索树比如 AVL 树和红黑树。它们会在每次插入或删除之后自动旋转调整结构把树的高度控制在 O(log n)。Java 里TreeMap和TreeSet底层的红黑树就是这种自平衡的一种实现。红黑树通过给节点涂色红或黑并维护五条约束来保证最长路径不超过最短路径的两倍从而保证树大致平衡。注意红黑树不追求绝对平衡而是近似平衡这样能在插入删除的性能和查询的性能之间取得更好的折中这就是工程实现没有选择 AVL 树做标准库底层的原因。3. 哈希表快速定位的利器3.1 哈希函数的作用把无限空间映射到有限空间哈希表的灵感来自一个很朴素的想法如果我能根据 key 直接算出它存储在数组的哪个下标那不就可以做到 O(1) 的查找了吗这个“计算下标”的函数就是哈希函数。你可以把哈希函数理解成一台机器喂给它任意一个对象比如字符串、自定义对象它吐出来一个整数。这个整数再经过取模之类的处理就变成了数组下标。生活中最直观的例子是医院的就诊叫号系统你到了医院护士把你的挂号信息通过系统分配一个号码这个号码对应到某个诊室后续叫号直接通过号码找人不需要在候诊区挨个喊名字。哈希函数必须满足一个基本条件同一个 key 必须算出同一个值。否则连最基本的查询都做不了。理论上我们当然希望不同 key 算出的值也完全不同但现实中没有这么理想的哈希函数。数组空间有限key 的数量又可能无限所以必然会出现哈希冲突——两个不同的 key 被分配到了同一个下标。3.2 哈希冲突的两种处理方式拉链法与开放地址法解决哈希冲突的主流方案有两种。拉链法链地址法就是在数组的每个位置挂一个链表发生冲突时把新元素直接追加到这个链表的末尾。开放地址法则是在冲突发生后按照某种规则去找数组中的下一个空位比如线性探测依次往后找空位、平方探测等。Java 的HashMap采用的是拉链法这一点从源码的结构就能看出来HashMap底层是一个NodeK,V[] table数组数组每个位置要么是空要么是一个Node节点要么是一条链表的头节点在特定条件下还会变成红黑树。拉链法实现简单删除也相对方便适合读多写多的通用场景。开放地址法对外部存储连续性的要求更高删除处理后会有“空位”造成的断链问题因此工程上用得少一些。你可以想象一个有公共冲突区的停车场每个车位代表一个哈希槽位如果两辆车撞了同一个车位就把后来的车停在旁边的“临时停车区”并挂上链条。拉链法就是这个思路。3.3 HashMap 的扩容机制与负载因子的选择哈希表不是固定大小的。随着元素越存越多冲突概率会上升链表会变长查询效率会下降。所以哈希表需要通过扩容来保持相对稀疏的存储结构。扩容的触发条件是负载因子负载因子 已存储元素个数 / 哈希表容量JavaHashMap默认的负载因子是0.75也就是当元素个数达到容量乘以 0.75 时就触发扩容。默认情况下HashMap的初始容量是 16所以当元素个数超过 12 个时它就会扩容到原来的两倍也就是 32。更多细节不在这里展开后面我会专门讲解 loadFactor 的选择对性能的影响。为什么默认选择 0.75这是空间与时间之间的一个折中。负载因子越大空间利用率高但冲突概率也随之提高负载因子越小空间浪费严重但冲突概率降低。0.75 是经过大量统计后得出的经验值在大部分业务场景下表现都比较好。扩容涉及一个非常关键的操作重新哈希。扩容之后数组大小变了原有的每一个元素都必须根据新的容量重新计算下标然后迁移到新数组中。这个操作的时间复杂度是 O(n)所以如果你能预估数据规模最好在创建HashMap时直接指定合适的初始容量MapString, User userMap new HashMap(64);我会在后面的章节里告诉你怎么估算初始容量这里先记住一个结论你自己预估的元素数量被负载因子除一下就是建议设置的初始容量。例如预估存 100 个元素初始容量至少设为100 / 0.75 ≈ 133.3向上取整到 2 的幂就是 256直接写new HashMap(256)更稳妥。3.4 Java 1.8 之后的底层改进链表转红黑树如果你读过旧版本的HashMap源码会发现一个明显差异JDK 7 中同一槽位的新元素是头插法插入链表的也就是新元素变成链表头节点。JDK 8 改成了尾插法。这两者的差异很关键头插法在并发扩容时多线程同时迁移元素容易形成环形链表导致后续的查找操作出现死循环CPU 飙升。尾插法加上其他细节调整避免了这个问题所以 1.8 之后并发环境下最多是数据丢失而不会出现死循环。不过我要提醒一句这不代表HashMap可以在并发环境里随便用后续章节我会专门说并发问题。JDK 8 还引入了另一个重要机制当链表长度超过 8且数组容量大于等于 64 时链表会转成红黑树。转换的目的很明确冲突严重时链表查询是 O(n)而红黑树查询是 O(log n)。虽然红黑树节点占用的空间比链表节点大转换也需要额外的开销但这是用空间换极端场景下的时间效率保证即使发生大量哈希碰撞查询性能也不会差到不可接受。这里有个反直觉的细节理论上负载因子 0.75 时链表长度达到 8 的概率非常低已经低于千万分之一。既然概率这么低为什么还要转换成红黑树因为现实业务中可能出现恶意构造 hash 值让大量 key 冲突被分到同一个槽位的情况或者自定义的 hashCode 实现太差导致分布极其不均匀。红黑树机制是一道兜底防线保证最坏情况下HashMap的性能也不会完全崩掉。4. Map 和 Set数据结构的上层建筑4.1 为什么需要 Map 和 Set接口抽象的智慧在前面的章节里哈希表和二叉搜索树都是“数据结构”但它们不是业务代码直接使用的对象。Java 集合框架通过Map和Set两个接口把底层数据结构的功能抽象成了面向业务的 API。Map解决的核心问题是通过 key 快速找到 value。业务里到处是这样需求根据用户 ID 查用户详情根据订单号查订单根据 IP 查服务器节点。如果用数组或链表每次查找都要遍历数据量一大就扛不住。Map从接口层面承诺了这一点你只要给一个 key我能快速给到你对应的 value。Set解决的核心问题是去重和集合运算。很多业务场景需要保证元素不重复比如一个活动只能参与一次一批手机号只能领取一次优惠券。Set在接口层面承诺同一时刻最多只有一个相同元素存在并且支持高效的成员判断。这两个接口本身不关心底层实现是哈希表还是二叉树它们把“怎么存”留给了实现类。这样设计的好处显而易见你的业务代码只依赖接口哪天想换实现类改一行代码或者改一个工厂配置就行其他代码完全不用动。4.2 四个实现类的关系与对应规则Java 集合框架里最常用的四个实现类分别是HashMap、HashSet、TreeMap、TreeSet。它们的关系可以用一句话概括HashSet的底层就是一个HashMap添加元素时把元素作为 keyvalue 统一设置为一个固定的PRESENT对象。所以HashSet的“去重”本质上是HashMap的“key 去重”。TreeSet的底层就是一个TreeMap元素同样作为 key 存储。这一点在源码中看得很清楚。HashSet内部持有一个HashMapE,Object引用你调用add(e)的时候实际上执行的是map.put(e, PRESENT)。PRESENT是一个静态的Object实例没有任何业务含义只是一个占位的 value。同理TreeSet内部持有一个TreeMapE,Object。所以学透了HashMapHashSet基本上就自动掌握了。四个类之间从底层的关联关系我整理成一张表容器底层结构核心特性适用场景HashMap哈希表数组链表红黑树插入、查询 O(1)无序大多数通用 Map 场景HashSetHashMap 的 key 部分去重、成员判断 O(1)无序去重、集合判重TreeMap红黑树key 有序操作为 O(log n)需要按 key 范围查询、排序输出的场景TreeSetTreeMap 的 key 部分元素有序、去重有序去重集合、自动排序4.3 如何选择用哪个 Map从使用场景倒推实际开发中“选哪个”的决策其实很简单。默认情况优先考虑HashMap它是性能最好的通用实现。有些场景需要按某种顺序遍历或按范围获取子集比如排行榜需要按积分从高到低输出、商品列表需要按价格区间过滤这时候应该用TreeMap。TreeMap的排序规则来自两种机制一是 key 类型实现了Comparable接口二是通过构造函数传入一个自定义的Comparator。这两者的优先级和规则值得讲一讲如果构造TreeMap时传入了Comparator那么排序完全由它决定key 本身的Comparable不再生效。如果没有传入就会调用 key 的compareTo()方法。如果 key 既不实现Comparable又没有传入Comparator那么在向TreeMap添加第一个元素的时候就会抛出ClassCastException。我给某个系统写过一个排行榜模块当时用TreeMapLong, UserScore存储用户分数key 是用户 id通过自定义Comparator实现按分数倒序排列。但很快发现一个隐患如果两个用户分数相同TreeMap会认为两个 key 相等导致用户 id 不同的两个用户互相覆盖。后来我改用分数和用户 id 组合来作为 keyComparator里先按分数排分数相同再按 id 排才彻底解决。这个案例非常典型地展示了TreeMap排序结果会直接影响 key 的唯一性判断。LinkedHashMap也值得提一句。它继承自HashMap额外维护了一条双向链表记录插入顺序默认是插入序也可以通过构造函数改成访问序。需要“按插入顺序遍历”的需求比如展示最近添加的记录列表就可以用它。4.4 equals 和 hashCode 到底怎么配合这一节是面试和实际踩坑的重灾区。先说结论如果你想用自定义对象作为HashMap的 key或者往HashSet里放自定义对象你就必须同时正确地重写equals()和hashCode()否则去重和查找都会出问题。为什么HashMap的查找过程分两步。第一步调用 key 的hashCode()定位到某个数组槽位第二步在槽位对应的链表或红黑树中通过equals()逐个比较找到真正匹配的 key。如果两个对象业务上相等equals()返回 true但它们的hashCode()不同那么它们会被放到不同的槽位查找时根本走不到第二个比较环节直接认为不存在从而导致“查不到”或“去重失效”。正确的写法有两条铁律对同一个对象hashCode()必须保持不变如果equals()返回 true那么它们的hashCode()必须相等。反过来的约束则不需要满足两个对象hashCode()相等并不要求equals()返回 true。因为哈希碰撞本来就是允许的。举个例子。你定义了一个Person对象业务上认为“身份证号相同就是同一个人”。如果只重写了equals()没重写hashCode()那么两个身份证号相同的Person对象被放入HashSet时由于默认的hashCode()来自对象的内存地址两个对象算出的槽位不同就都会被放进去去重逻辑完全失效。这是新手最容易踩的坑。还有一个被经常忽略的细节放在 Map 中作为 key 的对象它的 hashCode 依赖的字段不能发生改变。假设你用一个人的手机号作为 key 的哈希依据存储到HashMap后如果这个人的手机号被更改了那么再通过同一个对象去查hashCode已经变了定位到的槽位也变了原来的键值对就“消失”了。这种 bug 很难排查。所以业务上做 key 的对象建议选择不可变字段或者直接使用String、Long这类不可变类型。5. 常见问题与排查技巧实录5.1 HashMap 在并发环境下的线程安全问题关于并发我见过很多被网上旧文章误导的说法。这里我尽量给出准确且实用的版本。JDK 1.7 的HashMap在并发扩容时因为头插法的存在多个线程同时操作会导致链表形成环一旦有查询触碰到这个环就会陷入死循环CPU 直接跑满。JDK 1.8 改为尾插法之后环形链表的场景基本上不再出现但并发问题依然存在具体表现为数据覆盖和丢失。举个例子两个线程同时执行put它们都检查到某个槽位为空都准备写入新节点。线程 A 写入完成线程 B 接着写入并直接把指针覆盖了线程 A 的数据就丢了。这跟链表头插尾插没关系是put操作本身缺少同步保证。所以并发场景下请直接用ConcurrentHashMap。它的核心设计思想从 JDK 1.7 的分段锁演进到 JDK 1.8 的 CAS synchronized 锁住单个槽位的头节点锁粒度更细并发性能大幅提升。读操作用了 volatile 来保证可见性实现无锁读。也就是说多线程读的场景几乎不用阻塞。5.2 自定义对象做 key 的注意事项先列一个查验清单都是我看过真实事故后总结的equals()和hashCode()方法必须成对重写参与hashCode()计算的字段不能是可变字段两个对象“相等”的定义标准要和你的业务语义一致别去重了不该重的东西如果对象是 JPA 实体用做 key 时尤其注意主键未分配的情况比如刚 new 出来的对象没有 id此时 hashCode 和 equals 的行为要专门测试。如果你问我“为什么不能用BigDecimal做 key”其实不是不能用而是要小心。new BigDecimal(1.0)和new BigDecimal(1.00)的equals()返回值是 false因为它们的scale不一样。如果你没有意识到这一点用BigDecimal做 key 就会踩到意料之外的映射问题。开发时我一般优先用String或者基础类型的包装类做 key省心。5.3 TreeMap 排序异常排查从堆栈到比较器之前提到过排行榜排名覆盖的案例这里把排查思路写一下。当时我们收到线上反馈排行榜上人数变少部分用户的成绩丢失。我们第一时间查看了日志确认没有异常堆栈然后开始怀疑是不是写库的并发问题。检查了数据源之后发现数据没问题最终把目光落在存储结构上。从TreeMap源码的put方法入手它的逻辑是从根节点开始用 comparator 比较 key。如果compare返回 0就视为 key 相同直接覆盖 value。所以排名覆盖的本质是 comparator 返回了 0但业务上这两个 key 其实是不同的用户。修复方案我前面已经说过在比较器里当业务排序字段相同时必须再引入一个不会重复的字段比如用户 id作为次要比较条件。这样任何两个不同的 key 都不可能返回 0覆盖问题就解决了。这个教训可以推广到所有用TreeMap或TreeSet的场景比较器的“相等”语义必须与业务 key 的唯一性语义保持一致。5.4 性能排查思路哈希碰撞严重时怎么办如果你发现某个HashMap的读写速度明显变慢可以怀疑是冲突太多链表过长。常见的原因有三个第一hashCode()的实现质量太差。比如某些人在类里写return 1;所有对象都落到同一个槽位HashMap直接退化成链表性能从 O(1) 变成 O(n)。排查方法是统计某个槽位链表节点数量或者在代码里临时打印hashCode()的分布。第二容量不够。当元素数量快速增长频繁扩容和重新哈希也会造成 CPU 损耗和内存抖动。这类情况比较隐蔽因为故障时间点往往晚于流量高峰。按我自己的经验提前预估容量并设置合理的初始值是最有效的预防手段。第三负载因子设置不合理。有些团队为了节约内存把负载因子调高到 1 甚至更高。这在极端情况下可能导致冲突概率大幅上升。工程实践中我建议保持默认的 0.75除非你能拿出明确的测试数据证明你的场景更适合其他值。整体排查思路就是善用各类 Java 诊断工具去查看某个 hash 桶内的链表长度和红黑树转换次数这些指标能直接反映哈希分布质量比盲目调参靠谱得多。5.5 快速记忆清单三个容易混淆的知识点最后我把自己平时给新人讲的三个最容易混淆的点也整理在这里毕竟这个标题的核心考点也就是这些。第一个Hashtable、HashMap、ConcurrentHashMap的区别。Hashtable是早期的线程安全容器所有方法都用synchronized加锁效率很低现在已经很少使用了。HashMap非线程安全。ConcurrentHashMap是线程安全的高性能版本并发场景选它语法和HashMap基本一致升级成本很低。第二个HashSet和TreeSet的区别。本质差异是底层结构不同一个用哈希表一个用红黑树。所以一个无序一个有序一个查找 O(1)一个查找 O(log n)。场景需要有序就去选 TreeSet否则用 HashSet。第三个HashMap的 key 为什么要求是不可变对象。因为可变对象的hashCode会随着字段改变而改变破坏“同一个 key 找到同一个 value”的语义。实践上字符串、整数这类不可变类是首选实在需要自定义对象就必须严格遵循不可变设计。总结我的一些真实体会把二叉搜索树、哈希表、Map 和 Set 放在一起读不是死记结论而是通过底层结构去推演出上层容器理解为什么 Java 标准库要做这样的设计选择。就我个人的经验来看很多程序员在业务里写得太顺手以致于见到HashMap就用完全忘了它还有容量、负载因子、哈希冲突这回事。直到压测时性能崩了才回头去查底层。与其等线上事故敲醒你不如在学习阶段就把这些细节啃下来。刚入行时我花了很多时间背“HashMap 默认容量是16负载因子是0.75”这句话但从没想过它背后的概率统计和空间折中后来真正读了源码才明白每一个默认值背后都有一堆工程考量。这些“反直觉”的知识是阅读源码和实验验证得到的不是背出来的这种透彻的感觉也让我面对实际问题时心里更有底。希望你在读完这篇文章之后能试着把TreeMap的源码打开对照红黑树的旋转过程走走流程把HashMap的put流程画出来看看数组下标到底是怎么算出来的。数据结构的魅力就在于此——上一秒你觉得它是理论下一秒它就是你排查线上问题的利器。