1. 集合体系先分清语义再选择实现Java 集合框架可以先拆成两个平行部分Collection保存一个个元素Map保存 key-value 键值映射。Collection下面最常用的接口是List、Set、Queue和Deque。接口只规定使用语义具体实现类才决定数据放在连续数组、链表、哈希桶还是红黑树中。1.1 常见接口的语义接口关注点常见实现是否允许重复是否保证顺序List一组有位置的元素ArrayList、LinkedList允许通常保持插入顺序Set元素唯一HashSet、TreeSet不允许取决于实现Queue排队和取出ArrayDeque、PriorityQueue可以FIFO 或按优先级Deque两端操作ArrayDeque、LinkedList可以两端都可操作Mapkey 定位 valueHashMap、TreeMapkey 通常唯一取决于实现因此集合选型不要从“我记得哪个类比较快”开始而要从业务语义开始需要按下标随机访问还是主要在两端操作允许重复还是必须去重只需要快速定位还是需要有序遍历和范围查询key 是否会被修改是否需要并发安全2. ArrayList连续数组、size 和 capacityArrayList的底层可以理解为一段连续的Object[]数组。数组有两个容易混淆的概念size当前真正保存了多少个元素capacity底层数组当前能够容纳多少个位置。size可以小于capacity所以数组后面出现空位置是正常的。2.1 为什么按下标读取很快数组元素连续存储JVM 可以根据数组起始地址和下标计算目标位置元素地址 数组起始地址 index × 元素大小因此ListStringnamesnewArrayList();names.add(A);names.add(B);Stringvaluenames.get(1);// 直接按下标定位get(index)和set(index, value)的典型复杂度是O(1)。连续内存也更有利于 CPU 缓存遍历时通常比节点分散的链表更友好。2.2 尾部追加与扩容当尾部还有空位置时追加元素只需要写入数组并增加size。如果数组已经满了ArrayList会申请一个更大的新数组把旧数组中的元素复制过去让elementData指向新数组把新元素写入末尾。以常见的 JDK 8 实现为例扩容后的容量大约是旧容量的 1.5 倍。具体扩容策略可能随 JDK 版本变化但“扩容需要复制”是稳定结论。所以尾部追加的摊销复杂度接近O(1)某一次触发扩容的追加可能是O(n)如果能预估数据量可以通过构造初始容量减少扩容次数。ListOrderordersnewArrayList(1000);2.3 中间插入为什么是 O(n)假设数组中已有[A][B][C][D][E]现在执行add(2, X)为了给X腾出位置C、D、E都要向右移动[A][B][X][C][D][E]因此中间插入和删除的成本主要来自后续元素搬移典型复杂度为O(n)。2.4 ArrayList 的优缺点优点随机访问快遍历性能通常好节点对象和指针开销小适合读多写少、按位置访问明显的列表。代价扩容需要复制数组中间插入和删除需要移动元素本身不保证线程安全删除元素不会因为逻辑上size变小就自动释放整个底层数组。3. LinkedListNode 节点组成双向链表LinkedList的底层不是连续数组而是一个个NodeE节点。每个节点至少包含三部分privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;}链表对象本身还会保存first/head和last/tail分别指向首节点和尾节点。3.1 双向连接是怎样工作的一个包含四个节点的链表可以表示为null - Node1 - Node2 - Node3 - Node4 - null head tail从Node2删除Node3时不需要搬移其他节点只需要让Node2.next Node4 Node4.prev Node2这就是链表“已定位节点后增删可以是O(1)”的来源。3.2 为什么 LinkedList 按下标访问很慢链表没有办法像数组一样根据下标直接计算地址。执行get(index)时必须从头部或尾部沿指针逐个走到目标节点。实现通常会根据 index 离哪一端更近来选择遍历方向但最坏仍然需要走很多节点典型复杂度是O(n)。ListStringlistnewLinkedList();Stringvaluelist.get(500);// 需要沿节点逐个查找所以“LinkedList 插入删除是O(1)”不能脱离前提。下面两步合起来整体通常仍然是O(n)先通过下标找到位置再修改节点指针。3.3 LinkedList 的适用场景适合已经持有节点或迭代器位置需要局部插入和删除主要做首尾操作需要同时使用List和Deque语义。不应仅因为“听说链表增删快”就默认使用它。节点对象、prev/next指针和分散内存都会带来额外成本。只需要双端队列时通常还要比较ArrayDeque。4. HashMap哈希表 链表 红黑树HashMap 是这几个结构中最需要结合图来理解的一个。先给出结论JDK 8 的 HashMap 可以理解为一个桶数组哈希表 桶内链表 在冲突严重时使用的红黑树。4.1 HashMap 的基本数据结构HashMap 的核心成员可以抽象成NodeK,V[]table;table是一个数组。数组中的每个位置叫一个桶bucket桶中可能是null这个位置还没有元素一个Node当前桶只有一个元素一条由next连接的链表多个 key 发生哈希冲突一棵红黑树冲突节点较多时链表桶可能树化。节点大致包含staticclassNodeK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;}其中hash保存 key 的哈希结果key真正的键value与 key 关联的值next冲突时指向同一个桶中的下一个节点。4.2 从 key 到桶下标调用map.put(key,value);大致会经历以下步骤第一步计算 hashCodeinthkey.hashCode();对象的hashCode()不要求唯一。不同对象得到相同哈希值是允许的这就是冲突的根源之一。第二步扰动高低位JDK 8 中常见的哈希扰动可以简化理解为inthashh^(h16);这样做是为了让高位信息参与低位计算减少一些 key 分布不均的情况。第三步计算桶下标当数组长度为n且n是 2 的幂时常见下标计算可以理解为intindex(n-1)hash;这就是为什么 HashMap 的数组长度通常会保持为 2 的幂。使用位运算可以快速计算下标同时让扩容时的节点迁移更简单。4.3 为什么会发生哈希冲突假设 table 有 7 个桶index: 0 1 2 3 4 5 6 Entry null Entry null Entry Entry null不同 key 经过 hash 和下标计算后可能落到同一个 index。例如userA和userB都落到下标 1table[1] - Entry(userA) - Entry(userB) - null数组下标相同并不代表两个 key 相等。HashMap 会继续比较hash 是否相等key 是否相等是否应该更新旧 value还是追加新的节点。因此HashMap 依赖hashCode()和equals()共同完成定位。4.4put的完整思路向 HashMap 放入一个键值对时可以按下面的流程理解key ↓ hashCode() ↓ 扰动 hash ↓ 计算 table[index] ↓ ┌───────────────┐ │ 桶为空 │── 是 ── 放入新 Node └──────┬────────┘ │ 否 ↓ 比较 hash 和 key ↓ ┌──────────────────────┐ │ 找到相同 key │── 是 ── 覆盖 value └──────────┬───────────┘ │ 否 ↓ 沿链表查找或在红黑树中查找 ↓ 追加节点 / 插入树节点4.5 链表什么时候会变成红黑树早期的 HashMap 在冲突较多时桶内就是一条越来越长的链表table[index] ↓ Entry1 - Entry2 - Entry3 - Entry4 - ... - null链表查找需要从头到尾比较冲突严重时可能退化到O(n)。JDK 8 引入了桶树化机制当单个桶中的节点数量达到树化阈值并且 table 容量足够大时链表可能转换为红黑树。常见实现参数是TREEIFY_THRESHOLD 8链表节点达到这个数量附近时考虑树化MIN_TREEIFY_CAPACITY 64table 太小时优先扩容而不是立刻树化UNTREEIFY_THRESHOLD 6节点减少后可能退回链表。这些是 JDK 8 常见实现参数具体行为仍应以当前 JDK 源码为准。因此复杂冲突下的 HashMap 不是“单纯的数组”而是HashMap ├── tableNode[] 桶数组 ├── 普通桶单个 Node ├── 冲突桶Node next 链表 └── 冲突严重桶TreeNode 组成红黑树4.6 HashMap 的复杂度场景典型复杂度说明无冲突查找平均O(1)一次定位到桶并比较节点普通链表桶取决于链表长度冲突越多比较次数越多严重冲突且已树化典型O(log n)红黑树保持近似平衡极端链表退化O(n)发生在未树化或特殊退化情况下扩容单次O(n)需要迁移现有节点所以“HashMap 的查询是O(1)”应该说成“平均情况下接近O(1)”。它不是一个无条件成立的最坏复杂度结论。4.7hashCode和equals必须保持契约如果两个对象a.equals(b)true那么必须满足a.hashCode()b.hashCode()但哈希值相等不代表两个对象一定相等因为冲突是允许的。作为 key 的对象还必须尽量保持不可变。下面的风险很常见UserKeykeynewUserKey(1L,alice);MapUserKey,StringmapnewHashMap();map.put(key,data);key.setUsername(bob);// 改变了参与 hashCode/equals 的字段map.get(key);// 可能无法找到原来的节点对象实际上可能仍然在旧桶里但新的哈希值让查询走到了另一个桶。4.8 HashMap 的其他特点允许一个nullkey允许多个nullvalue不保证遍历顺序普通HashMap不保证线程安全扩容通常会扩大 table 容量并重新组织桶中的节点如果业务需要插入顺序可以考虑LinkedHashMap如果业务需要排序和范围查询可以考虑TreeMap。5. HashSet用 HashMap 的 key 实现去重HashSet 没有重新发明一套哈希结构。它可以理解为HashSet 的元素放在内部 HashMap 的 key 位置value 统一使用一个固定占位对象PRESENT。5.1 HashSet.add 的实现思路可以简化成privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}调用SetStringnamesnewHashSet();names.add(alice);逻辑上接近map.put(alice,PRESENT);真正重要的是 key也就是集合元素本身value 只是一个统一的占位对象。5.2 HashSet 如何判断重复HashSet 的去重过程仍然依赖 HashMap对元素调用hashCode()根据 hash 定位桶在桶内比较 hash 和 key使用equals()判断是否是同一个元素如果已经存在就不再添加。因此放入 HashSet 的对象同样必须正确实现hashCode()和equals()。5.3 HashSet 的特点平均查找和去重接近O(1)不保证遍历顺序底层可能经历数组、链表和红黑树结构元素参与去重的字段不应在放入后改变只需要去重时通常比 TreeSet 更轻量需要插入顺序时使用LinkedHashSet需要排序时使用TreeSet。6. TreeMap没有哈希桶只有按比较器组织的红黑树TreeMap 和 HashMap 的底层思路完全不同HashMap 先算 hash再找桶TreeMap 不算 hash而是从根节点开始比较 key小于当前节点就往左子树走大于当前节点就往右子树走。6.1 TreeMap 的节点结构TreeMap 中的节点可以抽象成staticfinalclassEntryK,V{Kkey;Vvalue;EntryK,Vleft;EntryK,Vright;EntryK,Vparent;booleancolor;}它是一棵红黑树每个节点保存keyvalue左孩子右孩子父节点颜色标记。6.2 查询路径执行map.get(targetKey);大致流程是root ↓ compare(targetKey, currentKey) ├── 小于 0进入 left ├── 大于 0进入 right └── 等于 0找到目标节点红黑树通过旋转和变色保持树高受控因此get、put、remove的典型复杂度都是O(log n)。6.3 TreeMap 为什么适合范围查询因为 key 始终按照自然顺序或Comparator组织所以 TreeMap 很适合查找最小 keyfirstKey()查找最大 keylastKey()查找不小于目标的 keyceilingKey()查找不大于目标的 keyfloorKey()获取一个 key 范围内的子 Map按 key 顺序遍历。NavigableMapInteger,StringlevelsnewTreeMap();levels.put(10,高级);levels.put(20,专家);Stringlevellevels.ceilingEntry(12).getValue();// 找到不小于 12 的最小 key6.4 TreeMap 的“重复”由比较结果决定TreeMap 判断两个 key 是否相同关键看自然顺序或比较器是否返回0不一定只看equals()。SetStringnamesnewTreeSet(Comparator.comparingInt(String::length));names.add(cat);names.add(dog);// 长度相同比较结果为 0可能被当作重复如果比较器只比较长度cat和dog就没有第二排序条件。业务上如果要求两个值都能保存应补充稳定的次级比较规则。6.5 TreeMap 的特点不使用哈希桶底层是红黑树get/put/remove典型复杂度为O(log n)中序遍历可以得到有序 key适合范围查询、边界查询和有序遍历不适合只追求平均快速定位、完全不关心顺序的场景key 的比较规则必须稳定并尽量与equals保持一致。7. 六种结构放在一起比较类型底层结构读取/查找插入/删除顺序特征适合场景ArrayList动态数组按下标O(1)中间操作O(n)插入顺序随机访问、列表遍历LinkedList双向链表按下标O(n)已定位节点O(1)插入顺序首尾操作、局部节点增删HashMap桶数组 链表/红黑树平均O(1)平均O(1)不保证key 快速定位HashSetHashMap 的 key平均O(1)平均O(1)不保证去重TreeMap红黑树O(log n)O(log n)key 有序范围查询、排序8. 最后用一句话记忆ArrayList数组连续按下标快中间移动慢LinkedList节点靠指针连接定位慢已定位后改指针快HashMap哈希表定位冲突用链表冲突严重时可能树化HashSet元素放进 HashMap 的 key靠 hashCode 和 equals 去重TreeMap不算 hash靠比较器走红黑树查询有序但复杂度是O(log n)集合选型先看顺序、重复、排序、访问方式和 key 规则再决定实现类。
Java 集合Java 集合框架知识点汇总
1. 集合体系先分清语义再选择实现Java 集合框架可以先拆成两个平行部分Collection保存一个个元素Map保存 key-value 键值映射。Collection下面最常用的接口是List、Set、Queue和Deque。接口只规定使用语义具体实现类才决定数据放在连续数组、链表、哈希桶还是红黑树中。1.1 常见接口的语义接口关注点常见实现是否允许重复是否保证顺序List一组有位置的元素ArrayList、LinkedList允许通常保持插入顺序Set元素唯一HashSet、TreeSet不允许取决于实现Queue排队和取出ArrayDeque、PriorityQueue可以FIFO 或按优先级Deque两端操作ArrayDeque、LinkedList可以两端都可操作Mapkey 定位 valueHashMap、TreeMapkey 通常唯一取决于实现因此集合选型不要从“我记得哪个类比较快”开始而要从业务语义开始需要按下标随机访问还是主要在两端操作允许重复还是必须去重只需要快速定位还是需要有序遍历和范围查询key 是否会被修改是否需要并发安全2. ArrayList连续数组、size 和 capacityArrayList的底层可以理解为一段连续的Object[]数组。数组有两个容易混淆的概念size当前真正保存了多少个元素capacity底层数组当前能够容纳多少个位置。size可以小于capacity所以数组后面出现空位置是正常的。2.1 为什么按下标读取很快数组元素连续存储JVM 可以根据数组起始地址和下标计算目标位置元素地址 数组起始地址 index × 元素大小因此ListStringnamesnewArrayList();names.add(A);names.add(B);Stringvaluenames.get(1);// 直接按下标定位get(index)和set(index, value)的典型复杂度是O(1)。连续内存也更有利于 CPU 缓存遍历时通常比节点分散的链表更友好。2.2 尾部追加与扩容当尾部还有空位置时追加元素只需要写入数组并增加size。如果数组已经满了ArrayList会申请一个更大的新数组把旧数组中的元素复制过去让elementData指向新数组把新元素写入末尾。以常见的 JDK 8 实现为例扩容后的容量大约是旧容量的 1.5 倍。具体扩容策略可能随 JDK 版本变化但“扩容需要复制”是稳定结论。所以尾部追加的摊销复杂度接近O(1)某一次触发扩容的追加可能是O(n)如果能预估数据量可以通过构造初始容量减少扩容次数。ListOrderordersnewArrayList(1000);2.3 中间插入为什么是 O(n)假设数组中已有[A][B][C][D][E]现在执行add(2, X)为了给X腾出位置C、D、E都要向右移动[A][B][X][C][D][E]因此中间插入和删除的成本主要来自后续元素搬移典型复杂度为O(n)。2.4 ArrayList 的优缺点优点随机访问快遍历性能通常好节点对象和指针开销小适合读多写少、按位置访问明显的列表。代价扩容需要复制数组中间插入和删除需要移动元素本身不保证线程安全删除元素不会因为逻辑上size变小就自动释放整个底层数组。3. LinkedListNode 节点组成双向链表LinkedList的底层不是连续数组而是一个个NodeE节点。每个节点至少包含三部分privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;}链表对象本身还会保存first/head和last/tail分别指向首节点和尾节点。3.1 双向连接是怎样工作的一个包含四个节点的链表可以表示为null - Node1 - Node2 - Node3 - Node4 - null head tail从Node2删除Node3时不需要搬移其他节点只需要让Node2.next Node4 Node4.prev Node2这就是链表“已定位节点后增删可以是O(1)”的来源。3.2 为什么 LinkedList 按下标访问很慢链表没有办法像数组一样根据下标直接计算地址。执行get(index)时必须从头部或尾部沿指针逐个走到目标节点。实现通常会根据 index 离哪一端更近来选择遍历方向但最坏仍然需要走很多节点典型复杂度是O(n)。ListStringlistnewLinkedList();Stringvaluelist.get(500);// 需要沿节点逐个查找所以“LinkedList 插入删除是O(1)”不能脱离前提。下面两步合起来整体通常仍然是O(n)先通过下标找到位置再修改节点指针。3.3 LinkedList 的适用场景适合已经持有节点或迭代器位置需要局部插入和删除主要做首尾操作需要同时使用List和Deque语义。不应仅因为“听说链表增删快”就默认使用它。节点对象、prev/next指针和分散内存都会带来额外成本。只需要双端队列时通常还要比较ArrayDeque。4. HashMap哈希表 链表 红黑树HashMap 是这几个结构中最需要结合图来理解的一个。先给出结论JDK 8 的 HashMap 可以理解为一个桶数组哈希表 桶内链表 在冲突严重时使用的红黑树。4.1 HashMap 的基本数据结构HashMap 的核心成员可以抽象成NodeK,V[]table;table是一个数组。数组中的每个位置叫一个桶bucket桶中可能是null这个位置还没有元素一个Node当前桶只有一个元素一条由next连接的链表多个 key 发生哈希冲突一棵红黑树冲突节点较多时链表桶可能树化。节点大致包含staticclassNodeK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;}其中hash保存 key 的哈希结果key真正的键value与 key 关联的值next冲突时指向同一个桶中的下一个节点。4.2 从 key 到桶下标调用map.put(key,value);大致会经历以下步骤第一步计算 hashCodeinthkey.hashCode();对象的hashCode()不要求唯一。不同对象得到相同哈希值是允许的这就是冲突的根源之一。第二步扰动高低位JDK 8 中常见的哈希扰动可以简化理解为inthashh^(h16);这样做是为了让高位信息参与低位计算减少一些 key 分布不均的情况。第三步计算桶下标当数组长度为n且n是 2 的幂时常见下标计算可以理解为intindex(n-1)hash;这就是为什么 HashMap 的数组长度通常会保持为 2 的幂。使用位运算可以快速计算下标同时让扩容时的节点迁移更简单。4.3 为什么会发生哈希冲突假设 table 有 7 个桶index: 0 1 2 3 4 5 6 Entry null Entry null Entry Entry null不同 key 经过 hash 和下标计算后可能落到同一个 index。例如userA和userB都落到下标 1table[1] - Entry(userA) - Entry(userB) - null数组下标相同并不代表两个 key 相等。HashMap 会继续比较hash 是否相等key 是否相等是否应该更新旧 value还是追加新的节点。因此HashMap 依赖hashCode()和equals()共同完成定位。4.4put的完整思路向 HashMap 放入一个键值对时可以按下面的流程理解key ↓ hashCode() ↓ 扰动 hash ↓ 计算 table[index] ↓ ┌───────────────┐ │ 桶为空 │── 是 ── 放入新 Node └──────┬────────┘ │ 否 ↓ 比较 hash 和 key ↓ ┌──────────────────────┐ │ 找到相同 key │── 是 ── 覆盖 value └──────────┬───────────┘ │ 否 ↓ 沿链表查找或在红黑树中查找 ↓ 追加节点 / 插入树节点4.5 链表什么时候会变成红黑树早期的 HashMap 在冲突较多时桶内就是一条越来越长的链表table[index] ↓ Entry1 - Entry2 - Entry3 - Entry4 - ... - null链表查找需要从头到尾比较冲突严重时可能退化到O(n)。JDK 8 引入了桶树化机制当单个桶中的节点数量达到树化阈值并且 table 容量足够大时链表可能转换为红黑树。常见实现参数是TREEIFY_THRESHOLD 8链表节点达到这个数量附近时考虑树化MIN_TREEIFY_CAPACITY 64table 太小时优先扩容而不是立刻树化UNTREEIFY_THRESHOLD 6节点减少后可能退回链表。这些是 JDK 8 常见实现参数具体行为仍应以当前 JDK 源码为准。因此复杂冲突下的 HashMap 不是“单纯的数组”而是HashMap ├── tableNode[] 桶数组 ├── 普通桶单个 Node ├── 冲突桶Node next 链表 └── 冲突严重桶TreeNode 组成红黑树4.6 HashMap 的复杂度场景典型复杂度说明无冲突查找平均O(1)一次定位到桶并比较节点普通链表桶取决于链表长度冲突越多比较次数越多严重冲突且已树化典型O(log n)红黑树保持近似平衡极端链表退化O(n)发生在未树化或特殊退化情况下扩容单次O(n)需要迁移现有节点所以“HashMap 的查询是O(1)”应该说成“平均情况下接近O(1)”。它不是一个无条件成立的最坏复杂度结论。4.7hashCode和equals必须保持契约如果两个对象a.equals(b)true那么必须满足a.hashCode()b.hashCode()但哈希值相等不代表两个对象一定相等因为冲突是允许的。作为 key 的对象还必须尽量保持不可变。下面的风险很常见UserKeykeynewUserKey(1L,alice);MapUserKey,StringmapnewHashMap();map.put(key,data);key.setUsername(bob);// 改变了参与 hashCode/equals 的字段map.get(key);// 可能无法找到原来的节点对象实际上可能仍然在旧桶里但新的哈希值让查询走到了另一个桶。4.8 HashMap 的其他特点允许一个nullkey允许多个nullvalue不保证遍历顺序普通HashMap不保证线程安全扩容通常会扩大 table 容量并重新组织桶中的节点如果业务需要插入顺序可以考虑LinkedHashMap如果业务需要排序和范围查询可以考虑TreeMap。5. HashSet用 HashMap 的 key 实现去重HashSet 没有重新发明一套哈希结构。它可以理解为HashSet 的元素放在内部 HashMap 的 key 位置value 统一使用一个固定占位对象PRESENT。5.1 HashSet.add 的实现思路可以简化成privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}调用SetStringnamesnewHashSet();names.add(alice);逻辑上接近map.put(alice,PRESENT);真正重要的是 key也就是集合元素本身value 只是一个统一的占位对象。5.2 HashSet 如何判断重复HashSet 的去重过程仍然依赖 HashMap对元素调用hashCode()根据 hash 定位桶在桶内比较 hash 和 key使用equals()判断是否是同一个元素如果已经存在就不再添加。因此放入 HashSet 的对象同样必须正确实现hashCode()和equals()。5.3 HashSet 的特点平均查找和去重接近O(1)不保证遍历顺序底层可能经历数组、链表和红黑树结构元素参与去重的字段不应在放入后改变只需要去重时通常比 TreeSet 更轻量需要插入顺序时使用LinkedHashSet需要排序时使用TreeSet。6. TreeMap没有哈希桶只有按比较器组织的红黑树TreeMap 和 HashMap 的底层思路完全不同HashMap 先算 hash再找桶TreeMap 不算 hash而是从根节点开始比较 key小于当前节点就往左子树走大于当前节点就往右子树走。6.1 TreeMap 的节点结构TreeMap 中的节点可以抽象成staticfinalclassEntryK,V{Kkey;Vvalue;EntryK,Vleft;EntryK,Vright;EntryK,Vparent;booleancolor;}它是一棵红黑树每个节点保存keyvalue左孩子右孩子父节点颜色标记。6.2 查询路径执行map.get(targetKey);大致流程是root ↓ compare(targetKey, currentKey) ├── 小于 0进入 left ├── 大于 0进入 right └── 等于 0找到目标节点红黑树通过旋转和变色保持树高受控因此get、put、remove的典型复杂度都是O(log n)。6.3 TreeMap 为什么适合范围查询因为 key 始终按照自然顺序或Comparator组织所以 TreeMap 很适合查找最小 keyfirstKey()查找最大 keylastKey()查找不小于目标的 keyceilingKey()查找不大于目标的 keyfloorKey()获取一个 key 范围内的子 Map按 key 顺序遍历。NavigableMapInteger,StringlevelsnewTreeMap();levels.put(10,高级);levels.put(20,专家);Stringlevellevels.ceilingEntry(12).getValue();// 找到不小于 12 的最小 key6.4 TreeMap 的“重复”由比较结果决定TreeMap 判断两个 key 是否相同关键看自然顺序或比较器是否返回0不一定只看equals()。SetStringnamesnewTreeSet(Comparator.comparingInt(String::length));names.add(cat);names.add(dog);// 长度相同比较结果为 0可能被当作重复如果比较器只比较长度cat和dog就没有第二排序条件。业务上如果要求两个值都能保存应补充稳定的次级比较规则。6.5 TreeMap 的特点不使用哈希桶底层是红黑树get/put/remove典型复杂度为O(log n)中序遍历可以得到有序 key适合范围查询、边界查询和有序遍历不适合只追求平均快速定位、完全不关心顺序的场景key 的比较规则必须稳定并尽量与equals保持一致。7. 六种结构放在一起比较类型底层结构读取/查找插入/删除顺序特征适合场景ArrayList动态数组按下标O(1)中间操作O(n)插入顺序随机访问、列表遍历LinkedList双向链表按下标O(n)已定位节点O(1)插入顺序首尾操作、局部节点增删HashMap桶数组 链表/红黑树平均O(1)平均O(1)不保证key 快速定位HashSetHashMap 的 key平均O(1)平均O(1)不保证去重TreeMap红黑树O(log n)O(log n)key 有序范围查询、排序8. 最后用一句话记忆ArrayList数组连续按下标快中间移动慢LinkedList节点靠指针连接定位慢已定位后改指针快HashMap哈希表定位冲突用链表冲突严重时可能树化HashSet元素放进 HashMap 的 key靠 hashCode 和 equals 去重TreeMap不算 hash靠比较器走红黑树查询有序但复杂度是O(log n)集合选型先看顺序、重复、排序、访问方式和 key 规则再决定实现类。
外企专属题库)
