面试题：Java TreeMap中如何验证键的唯一性

Question

请描述在Java的TreeMap中，键唯一性是如何实现验证的？如果插入重复键会发生什么？请结合TreeMap的底层数据结构和实现原理进行说明。

Answer 1

1. TreeMap 键唯一性验证

• 底层数据结构：TreeMap 基于红黑树（一种自平衡的二叉搜索树）实现。
• 唯一性验证原理：在插入新键值对时，TreeMap 会使用 compareTo 方法（若键实现了 Comparable 接口）或在构造 TreeMap 时传入的 Comparator 来比较新插入的键与树中已存在的键。二叉搜索树的特性决定了每个节点的左子树所有节点的键小于该节点的键，右子树所有节点的键大于该节点的键。通过这种比较方式，在插入过程中可以找到合适的位置插入新键，同时能判断是否存在重复键。

2. 插入重复键的情况

• 替换值：如果插入的键与 TreeMap 中已有的键相等（根据 compareTo 或 Comparator 比较结果），则不会插入新的键值对，而是用新的值替换旧的值。例如：

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("key1", 1);
// 此时 "key1" 已存在，执行下面操作会用 2 替换旧值 1
treeMap.put("key1", 2);

总之，TreeMap 利用红黑树的有序性和比较机制保证键的唯一性，重复键会导致值的替换。