Java 集合深入理解一、集合体系结构Collection 是单列集合的祖宗接口它的功能是全部单列集合都可以继承使用的。List 系列集合添加的元素是有序、可重复、有索引。Set 系列集合添加的元素是无序、不重复、无索引。二、Collection 通用方法所有单列集合ArrayList、LinkedList、HashSet、TreeSet 等都可以直接使用这些方法用法完全一致。add(E e)—— 把给定的对象添加到当前集合中对于 ArrayListadd 永远返回 true因为 List 允许重复对于 HashSet 等 Set 实现类如果元素已存在返回 falseclear()—— 清空集合中所有的元素remove(E e)—— 把给定的对象在当前集合中删除对于 List删除的是第一次出现的指定元素返回值表示是否删除成功contains(Object obj)—— 判断当前集合中是否包含给定的对象isEmpty()—— 判断当前集合是否为空size()—— 返回集合中元素的个数集合的长度CollectionStringcollectionnewArrayList();collection.add(Java);// 添加元素collection.size();// 获取元素个数collection.contains(Java);// 判断是否包含collection.remove(Java);// 删除元素collection.isEmpty();// 判断是否为空collection.clear();// 清空集合三、Collection 的三种遍历方式1. 迭代器遍历迭代器是集合专用的遍历方式不依赖索引。获取迭代器IteratorE iterator()—— 返回迭代器对象默认指向当前集合的 0 索引。Iterator 中的常用方法boolean hasNext()—— 判断当前位置是否有元素有则返回 trueE next()—— 获取当前位置的元素并将迭代器对象移向下一个位置IteratorStringitlist.iterator();while(it.hasNext()){Stringstrit.next();System.out.println(str);}迭代器的四个细节指针指向最后一位元素后面时再调用 next()会报 NoSuchElementException迭代器遍历完后指针不会复位。若要重复遍历需要重新获取迭代器对象循环中只能用一次 next() 方法迭代器遍历时不能用集合的方法进行增加或删除2. 增强 for 遍历增强 for 的底层就是迭代器是为了简化迭代器代码而出现的。JDK5 之后出现所有的单列集合和数组都可以使用。for(Strings:list){System.out.println(s);}3. Lambda 表达式遍历使用 Collection 的 forEach 方法配合 Lambda 表达式。list.forEach(s-System.out.println(s));// 或更简写为方法引用list.forEach(System.out::println);三种遍历方式的选择遍历过程中需要删除元素 → 使用迭代器仅需要遍历 → 使用增强 for 或 Lambda 表达式四、List 集合List 集合因为有索引所以除了继承 Collection 的方法外还多了很多索引操作的方法。List 特有方法void add(int index, E element)—— 在指定位置插入指定的元素E remove(int index)—— 删除指定索引处的元素返回被删除的元素E set(int index, E element)—— 修改指定索引处的元素返回被修改的元素E get(int index)—— 返回指定索引处的元素List 的遍历方式迭代器遍历遍历过程中需要删除元素时使用列表迭代器遍历遍历过程中需要添加元素时使用List 特有增强 for 遍历纯遍历时使用Lambda 表达式遍历纯遍历时使用普通 for 循环遍历时需要操作索引时使用List 特有因为有索引五、数据结构栈先进后出后进先出只有一个出入口队列先进先出后进后出一个出口一个入口数组内存中连续存储查询快通过地址值和索引定位查询任意数据耗时相同增删慢删除元素需要将后面所有元素前移添加元素需要将后面所有元素后移链表节点在内存中不连续每个节点包含数据值和下一个节点的地址查询慢无论查询哪个数据都要从头开始找增删相对快只需要修改相邻节点的指针六、ArrayList 底层原理底层是 Object[] 数组查询快、增删慢无参构造new ArrayList()初始为空数组 {}第一次 add() 时扩容到 10扩容触发条件添加后的总元素个数大于当前数组容量扩容时先按 1.5 倍计算旧容量 旧容量 / 2如果 1.5 倍还不够装下所有元素则直接扩容到刚好能装下的容量判断依据是添加后的总长度而非本次添加几个扩容本质创建新数组 → 拷贝旧数据 → 内部引用指向新数组 → 旧数组被 GC 回收每次扩容时间复杂度为 O(n)能预估大小时建议指定初始容量以减少扩容次数核心一句话数组 1.5 倍扩容 新建拷贝七、LinkedList 底层原理底层是双向链表Node 节点查询慢、增删快操作首位元素时速度极快每个节点包含三部分prev前驱、item数据、next后继链表本身维护两个指针first头节点地址和 last尾节点地址特有方法addFirst(E e)—— 在列表开头插入元素addLast(E e)—— 将元素追加到列表末尾getFirst()—— 返回第一个元素getLast()—— 返回最后一个元素removeFirst()—— 删除并返回第一个元素removeLast()—— 删除并返回最后一个元素核心操作原理addLast()创建新节点 → 旧尾的 next 指向新节点 → 新节点的 prev 指向旧尾 → last 更新为新节点addFirst()创建新节点 → 新节点的 next 指向旧头 → 旧头的 prev 指向新节点 → first 更新为新节点removeFirst()first 指向第二个节点 → 新头的 prev 置为 null → 旧节点断开链接等待 GCremoveLast()last 指向前一个节点 → 新尾的 next 置为 null → 旧节点断开链接等待 GCgetFirst() / getLast() 直接通过 first / last 获取时间复杂度 O(1)按索引查询或删除需要从头或尾遍历时间复杂度 O(n)不需要连续内存空间没有扩容机制添加元素随用随建核心一句话双向链表 头尾指针 节点即加即建八、迭代器底层原理迭代器是一个设计模式提供统一方式遍历集合不暴露底层结构。每个集合都有自己的迭代器实现类底层依赖集合自身的数据结构。ArrayList 的迭代器底层持有一个 cursor 游标指针从 0 开始next() 返回 cursor 位置的元素然后 cursorhasNext() 判断 cursor ! size依赖数组索引按顺序遍历核心游标指针 数组索引遍历// 简化逻辑intcursor0;publicbooleanhasNext(){returncursor!size;}publicEnext(){returnelementData[cursor];}LinkedList 的迭代器底层直接持有节点引用维护一个 next 节点指针指向下一个要返回的节点next() 直接返回当前 next 节点的数据然后 next 往后移一个节点next next.nexthasNext() 判断 next ! null核心节点引用 沿着 next 指针向后遍历// 简化逻辑NodeEnextfirst;publicbooleanhasNext(){returnnext!null;}publicEnext(){Edatanext.item;nextnext.next;returndata;}集合迭代器底层依赖遍历方式ArrayList数组索引 cursor 游标按索引取元素LinkedList节点指针next沿着链表指针走九、泛型泛型是 JDK5 引入的特性可以在编译阶段约束操作的数据类型并进行检查。泛型的好处统一数据类型把运行时期的问题提前到了编译时期避免了强制类型转换可能出现的异常泛型的细节泛型中不能写基本数据类型指定泛型的具体类型后传递数据时可以传入该类型或其子类类型如果不写泛型类型默认是 Object泛型类当一个类中某个变量的数据类型不确定时就可以定义带有泛型的类。修饰符class类名类型{}例如public class ArrayListE { }创建该类对象时E 就确定类型。E 可以理解为变量但存的不是数据而是数据类型。常见写法T、E、K、V 等。泛型类 把数据类型当变量创建对象时再确定具体是什么类型。泛型方法当单个方法中某个参数或返回值的数据类型不确定时使用。修饰符类型返回值类型 方法名(类型 参数){}// 示例publicTTshow(Tt){returnt;}特点调用方法时确定类型泛型写在返回值前面。泛型接口当接口中某个数据类型不确定时使用。修饰符interface接口名类型{}// 示例publicinterfaceListE{voidadd(Ee);}特点实现类实现接口时确定类型。种类泛型声明位置确定类型时机示例泛型类类名后面创建对象时ArrayListString list new ArrayList()泛型方法返回值前面调用方法时show(hello)自动推断为 String泛型接口接口名后面实现接口时class MyList implements ListString泛型的继承和通配符泛型不具备继承性但是数据具备继承性泛型的通配符?? extends E—— 表示 E 及其子类? super E—— 表示 E 及其父类使用场景定义类、方法、接口时如果类型不确定可以定义泛型如果类型不确定但知道是哪个继承体系中的可以使用泛型的通配符泛型就是把类型当作参数传递类、方法、接口各自在需要时声明在使用时确定。十、二叉树基本概念节点的内部结构父节点地址、本身值、左子节点地址、右子节点地址度每一个节点的子节点数量二叉树中任意节点的度小于等于 2树高树的总层数根节点最顶层的节点左子节点左下方的节点右子节点右下方的节点根节点的左子树根节点的左子节点下的所有节点根节点的右子树根节点的右子节点下的所有节点二叉查找树二叉排序树 / 二叉搜索树特点有序摆放每一个节点上最多有两个子节点任意节点左子树上的值都小于当前节点任意节点右子树上的值都大于当前节点二叉树的四种遍历方式前序遍历根左右从顶部节点开始 → 当前节点 → 左子节点 → 右子节点中序遍历左根右从左子节点开始 → 左子节点 → 当前节点 → 右子节点后序遍历左右根从左子节点开始 → 左子节点 → 右子节点 → 当前节点层序遍历从顶部节点开始一层一层遍历十一、平衡二叉树AVL树任意一个节点的左右子树高度差不能超过 1|左子树高度 - 右子树高度| ≤ 1。平衡因子左子树高度 - 右子树高度取绝对值后应 ≤ 1。目的防止二叉查找树退化成链表保证查找效率为 O(log n)。二叉树的旋转操作维护平衡左旋右孩子上位原节点变成左孩子右孩子的左子树过继给原节点右旋左孩子上位原节点变成右孩子左孩子的右子树过继给原节点左旋和右旋互为镜像操作AVL 树四种失衡调整LL左左左子树的左子树插入 → 右旋RR右右右子树的右子树插入 → 左旋LR左右左子树的右子树插入 → 先左旋再右旋RL右左右子树的左子树插入 → 先右旋再左旋十二、红黑树红黑树是一种自平衡的二叉查找树每个节点包含五个属性父节点地址、本身值、左子节点地址、右子节点地址、颜色。红黑树的五个性质每一个节点是红色或者黑色根节点必须是黑色如果一个节点没有子节点或父节点则该节点相应的指针属性值为 Nil这些 Nil 视为叶节点每个叶节点Nil是黑色的如果某一个节点是红色那么它的子节点必须是黑色不能出现两个红色节点相连对每一个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点添加节点的规则红黑树在添加节点的时候添加的节点默认是红色的。添加节点后的修复规则设新节点为 N情况 1N 是根节点 → 将 N 改为黑色情况 2N 的父节点是黑色 → 不做调整情况 3N 的父节点是红色叔父节点是红色 → 父节点和叔父节点改黑祖父节点改红将祖父节点作为新 N 继续向上修复情况 4N 的父节点是红色叔父节点是黑色或 Nil4.1LL父节点是祖父的左子N 是父的左子 → 祖父右旋父节点改黑祖父节点改红4.2RR父节点是祖父的右子N 是父的右子 → 祖父左旋父节点改黑祖父节点改红4.3LR父节点是祖父的左子N 是父的右子 → 父节点左旋变成 LL 情况处理4.4RL父节点是祖父的右子N 是父的左子 → 父节点右旋变成 RR 情况处理十三、Set 系列集合Set 集合的特点无序、不重复、无索引。Set 是接口继承 Collection。Set 集合的实现类特点HashSet无序、不重复、无索引LinkedHashSet有序按插入顺序、不重复、无索引TreeSet可排序、不重复、无索引十四、HashSet底层数据结构是哈希表数组 链表 红黑树JDK8。核心特点无序存放元素不重复允许 null。底层结构默认情况只有数组长度 16哈希碰撞时数组 链表碰撞的地址下形成链表链表过长时≥ 8 且数组 ≥ 64数组 红黑树数组是常态链表是意外红黑树是极端兜底概率低于千万分之一存储原理添加元素时调用元素的 hashCode()计算哈希值哈希值运算后得到数组存储位置索引该位置为空 → 直接存入该位置已有元素哈希碰撞→ 调用 equals() 比较equals() 返回 true → 重复元素不存入equals() 返回 false → 存入形成链表JDK 7新元素插头部头插法JDK 8新元素插尾部尾插法判断重复的规则两个元素相等的条件hashCode()相同 equals()返回 true。重写 equals() 时必须同时重写 hashCode()保证两个 equals() 相等的对象hashCode() 也相等。初始容量与扩容默认初始容量16数组长度默认负载因子0.75扩容时机元素个数大于容量 × 负载因子16 × 0.75 12时触发扩容扩容方式容量翻倍16 → 32 → 64数组是懒加载new HashSet()时不创建数组第一次 add() 时才创建负载因子 0.75 的含义元素个数达到数组长度的 0.75 倍时触发扩容。0.75 是时间和空间的平衡点小于 0.75扩容太频繁浪费内存大于 0.75哈希冲突太多查找变慢0.75 是泊松分布计算的最优值链表与红黑树的转换条件链表长度大于等于 8 且数组长度大于等于 64 时链表转红黑树链表长度大于等于 8 但数组长度小于 64 时先扩容不转红黑树红黑树节点数小于等于 6 时红黑树转链表增加时以 8 为界定值减少时以 6 为界定值线程安全HashSet 线程不安全多线程同时修改时会抛出 ConcurrentModificationException。线程安全替代方案Collections.synchronizedSet(new HashSet())CopyOnWriteArraySet读多写少场景使用场景数据去重快速查找O(1)不需要保持顺序的集合存储核心要点默认就是数组只有哈希碰撞才出现链表链表转红黑树概率极低元素无序存放元素不允许重复hashCode equals 判断元素个数超过容量 × 0.75 时数组翻倍扩容。十五、LinkedHashSet底层是哈希表 双向链表。特点有序按插入顺序、不重复、允许 null。跟 HashSet 基本一致只多了一个点额外维护了一条双向链表把元素按添加顺序串起来所以遍历时按插入顺序输出。具体分工哈希表负责去重和查找跟 HashSet 一样双向链表负责记录插入顺序LinkedHashSet 独有判断重复、扩容、转红黑树都跟 HashSet 一样比 HashSet 略慢、多占内存多两个指针使用场景需要去重 需要保持插入顺序。十六、TreeSet底层是红黑树。特点元素自动排序自然顺序 / 自定义排序、不重复、不允许 null。增删改查时间复杂度为 O(log n)。排序方式自然排序元素实现 Comparable 接口String、Integer 默认就有比较器排序构造时传入 Comparator自定义排序规则与 HashSet 的区别特性HashSetTreeSet底层哈希表红黑树顺序无序自动排序时间复杂度O(1)O(log n)是否允许 null允许不允许使用场景需要排序去重取最大值、最小值范围查找总结开发中用得少知道底层是红黑树、元素自动排序就够了。大多数排序需求用数据库 ORDER BY 或 ArrayList Collections.sort() 解决。十七、双列集合Map双列集合的特点一次需要存一对数据分别为键和值键不能重复值可以重复键和值是一一对应的每一个键只能找到自己对应的值键 值这个整体称为键值对或键值对对象在 Java 中叫做 “Entry 对象”十八、Map 的通用 APIMap 是双列集合的顶层接口。put(K key, V value)—— 添加元素key 存在则覆盖 value返回旧 valuekey 不存在则新增返回 null注意key 一旦生成不能被 put 修改只能改 valueremove(Object key)—— 根据键删除键值对元素返回被删除的 valuekey 不存在返回 nullclear()—— 移除所有的键值对元素containsKey(Object key)—— 判断集合是否包含指定的键containsValue(Object value)—— 判断集合是否包含指定的值isEmpty()—— 判断集合是否为空size()—— 返回集合中键值对的个数十九、Map 的三种遍历方式键找值keySet先拿到所有 Key再逐个用 Key 取 Value。SetStringkeysmap.keySet();for(Stringkey:keys){Stringvaluemap.get(key);System.out.println(keyvalue);}特点只适合需要 Key 的场景。如果每次都要取 Value会多一次哈希查找效率略低。键值对entrySet—— 推荐直接把 Key 和 Value 打包成 Entry 对象一次性全拿出来。SetMap.EntryString,Stringentriesmap.entrySet();for(Map.EntryString,Stringentry:entries){Stringkeyentry.getKey();Stringvalueentry.getValue();System.out.println(keyvalue);}特点同时拿 Key 和 Value 时效率最高一次遍历全搞定。日常开发最常用。Lambda 表达式 forEachJava 8直接用 Map 自带的 forEach 方法配合 Lambda 简化代码。map.forEach((key,value)-{System.out.println(keyvalue);});特点代码最简洁配合 Stream 流式编程时非常方便。但遍历中不能删除元素会报并发修改异常。三种方式对比方式写法适用场景keySet先拿 Key 再 get(key)只需要 Key或偶尔取 ValueentrySet直接拿 Entry取 Key 和 Value需要同时用 Key 和 Value最推荐Lambda forEachmap.forEach((k,v) - {…})代码追求简洁配合 Stream 使用遍历时删除元素三种方式中只有迭代器Iterator能在遍历时安全删除。IteratorMap.EntryString,Stringitmap.entrySet().iterator();while(it.hasNext()){Map.EntryString,Stringentryit.next();if(条件){it.remove();// 安全删除}}增强 for 和 Lambda forEach 在遍历时删除都会报 ConcurrentModificationException。总结日常遍历用 entrySet 增强 for要删元素用迭代器要写流式代码用 Lambda forEach。二十、HashMap底层是哈希表结构和 HashSet 差不多依赖 hashCode 方法和 equals 方法保证键的唯一如果键存储的是自定义对象需要重写 hashCode 和 equals 方法如果只存储值自定义对象不需要重写这两个方法二十一、LinkedHashMap底层是哈希表数组 链表 红黑树 双向链表。特点有序按插入顺序、键不重复、值可重复、允许 null 键和 null 值。LinkedHashMap 是 HashMap 的子类底层完全一样只是多维护了一条双向链表把每个 Entry 按顺序串起来所以遍历时按插入顺序输出。具体分工哈希表 → 负责快速查找、去重跟 HashMap 一样双向链表 → 负责记录插入顺序LinkedHashMap 独有两种顺序模式默认 → 按插入顺序遍历构造传 true → 按访问顺序遍历每次 get/put 操作被访问的元素移到链表末尾性能比 HashMap 略慢多维护链表指针多占内存每个 Entry 多两个指针 before/after。使用场景需要保持插入顺序实现 LRU 缓存重写 removeEldestEntry开启访问顺序模式二十二、TreeMap底层是红黑树。特点Key 自动排序、键不重复、值可重复、不允许 null 键值允许 null。增删改查时间复杂度为 O(log n)。排序方式自然排序Key 实现 Comparable 接口String、Integer 默认就有比较器排序构造时传入 Comparator自定义排序规则与 HashMap 的区别特性HashMapTreeMap底层哈希表红黑树顺序无序Key 自动排序时间复杂度O(1)O(log n)是否允许 null 键允许不允许特有方法firstKey()/lastKey()→ 取最小 / 最大 KeylowerKey(key)/higherKey(key)→ 取小于 / 大于指定 Key 的最近 KeysubMap(fromKey, toKey)→ 截取从 fromKey 到 toKey 这一段使用场景需要 Key 有序取最小 Key / 最大 Key范围查找二十三、Collections 工具类Collections 是 Java 提供的一个操作集合的工具类里面全是 static 方法专门用来对 CollectionList、Set进行各种操作。注意它叫 Collections带 s和接口 Collection不带 s是两码事。排序sort(ListT list)—— 按自然顺序排序sort(ListT list, ComparatorT c)—— 按自定义比较器排序reverse(List? list)—— 反转顺序shuffle(List? list)—— 打乱顺序洗牌查找binarySearch(List? list, T key)—— 二分查找要求先排序max(Collection? coll)—— 取最大值min(Collection? coll)—— 取最小值frequency(Collection? c, Object o)—— 统计元素出现次数批量操作addAll(Collection? super T c, T... elements)—— 批量添加copy(List? super T dest, List? extends T src)—— 复制到另一个 Listfill(List? super T list, T obj)—— 全部填充为指定元素线程安全重点synchronizedList(ListT list)—— 把普通 List 转为线程安全的 ListsynchronizedSet(SetT set)—— 转为线程安全的 SetsynchronizedMap(MapK,V map)—— 转为线程安全的 Map不可变集合emptyList()/emptySet()/emptyMap()—— 返回空集合singletonList(T o)/singletonSet(T o)/singletonMap(K key, V value)—— 返回只有一个元素的集合unmodifiableList(List? extends T list)—— 返回只读 List不能增删改代码示例ListIntegerlistnewArrayList();list.add(3);list.add(1);list.add(2);Collections.sort(list);// [1, 2, 3]Collections.reverse(list);// [3, 2, 1]Collections.shuffle(list);// 随机打乱intmaxCollections.max(list);// 最大值intcountCollections.frequency(list,1);// 1 出现了几次// 转成线程安全的 ListListIntegersafeListCollections.synchronizedList(list);// 转成只读 ListListIntegerreadOnlyCollections.unmodifiableList(list);readOnly.add(4);// 抛异常 UnsupportedOperationException与 Arrays 工具类的区别特性CollectionsArrays操作对象CollectionList、Set数组常用方法sort、reverse、shuffle、binarySearchsort、fill、asList、toString一句话总结Collections 是集合的万能工具箱排序、打乱、取极值、转线程安全、转只读全都有。记住 sort、shuffle、synchronizedXxx 这三个最常用的就够了其他的用到再查。
Java 集合深入理解
Java 集合深入理解一、集合体系结构Collection 是单列集合的祖宗接口它的功能是全部单列集合都可以继承使用的。List 系列集合添加的元素是有序、可重复、有索引。Set 系列集合添加的元素是无序、不重复、无索引。二、Collection 通用方法所有单列集合ArrayList、LinkedList、HashSet、TreeSet 等都可以直接使用这些方法用法完全一致。add(E e)—— 把给定的对象添加到当前集合中对于 ArrayListadd 永远返回 true因为 List 允许重复对于 HashSet 等 Set 实现类如果元素已存在返回 falseclear()—— 清空集合中所有的元素remove(E e)—— 把给定的对象在当前集合中删除对于 List删除的是第一次出现的指定元素返回值表示是否删除成功contains(Object obj)—— 判断当前集合中是否包含给定的对象isEmpty()—— 判断当前集合是否为空size()—— 返回集合中元素的个数集合的长度CollectionStringcollectionnewArrayList();collection.add(Java);// 添加元素collection.size();// 获取元素个数collection.contains(Java);// 判断是否包含collection.remove(Java);// 删除元素collection.isEmpty();// 判断是否为空collection.clear();// 清空集合三、Collection 的三种遍历方式1. 迭代器遍历迭代器是集合专用的遍历方式不依赖索引。获取迭代器IteratorE iterator()—— 返回迭代器对象默认指向当前集合的 0 索引。Iterator 中的常用方法boolean hasNext()—— 判断当前位置是否有元素有则返回 trueE next()—— 获取当前位置的元素并将迭代器对象移向下一个位置IteratorStringitlist.iterator();while(it.hasNext()){Stringstrit.next();System.out.println(str);}迭代器的四个细节指针指向最后一位元素后面时再调用 next()会报 NoSuchElementException迭代器遍历完后指针不会复位。若要重复遍历需要重新获取迭代器对象循环中只能用一次 next() 方法迭代器遍历时不能用集合的方法进行增加或删除2. 增强 for 遍历增强 for 的底层就是迭代器是为了简化迭代器代码而出现的。JDK5 之后出现所有的单列集合和数组都可以使用。for(Strings:list){System.out.println(s);}3. Lambda 表达式遍历使用 Collection 的 forEach 方法配合 Lambda 表达式。list.forEach(s-System.out.println(s));// 或更简写为方法引用list.forEach(System.out::println);三种遍历方式的选择遍历过程中需要删除元素 → 使用迭代器仅需要遍历 → 使用增强 for 或 Lambda 表达式四、List 集合List 集合因为有索引所以除了继承 Collection 的方法外还多了很多索引操作的方法。List 特有方法void add(int index, E element)—— 在指定位置插入指定的元素E remove(int index)—— 删除指定索引处的元素返回被删除的元素E set(int index, E element)—— 修改指定索引处的元素返回被修改的元素E get(int index)—— 返回指定索引处的元素List 的遍历方式迭代器遍历遍历过程中需要删除元素时使用列表迭代器遍历遍历过程中需要添加元素时使用List 特有增强 for 遍历纯遍历时使用Lambda 表达式遍历纯遍历时使用普通 for 循环遍历时需要操作索引时使用List 特有因为有索引五、数据结构栈先进后出后进先出只有一个出入口队列先进先出后进后出一个出口一个入口数组内存中连续存储查询快通过地址值和索引定位查询任意数据耗时相同增删慢删除元素需要将后面所有元素前移添加元素需要将后面所有元素后移链表节点在内存中不连续每个节点包含数据值和下一个节点的地址查询慢无论查询哪个数据都要从头开始找增删相对快只需要修改相邻节点的指针六、ArrayList 底层原理底层是 Object[] 数组查询快、增删慢无参构造new ArrayList()初始为空数组 {}第一次 add() 时扩容到 10扩容触发条件添加后的总元素个数大于当前数组容量扩容时先按 1.5 倍计算旧容量 旧容量 / 2如果 1.5 倍还不够装下所有元素则直接扩容到刚好能装下的容量判断依据是添加后的总长度而非本次添加几个扩容本质创建新数组 → 拷贝旧数据 → 内部引用指向新数组 → 旧数组被 GC 回收每次扩容时间复杂度为 O(n)能预估大小时建议指定初始容量以减少扩容次数核心一句话数组 1.5 倍扩容 新建拷贝七、LinkedList 底层原理底层是双向链表Node 节点查询慢、增删快操作首位元素时速度极快每个节点包含三部分prev前驱、item数据、next后继链表本身维护两个指针first头节点地址和 last尾节点地址特有方法addFirst(E e)—— 在列表开头插入元素addLast(E e)—— 将元素追加到列表末尾getFirst()—— 返回第一个元素getLast()—— 返回最后一个元素removeFirst()—— 删除并返回第一个元素removeLast()—— 删除并返回最后一个元素核心操作原理addLast()创建新节点 → 旧尾的 next 指向新节点 → 新节点的 prev 指向旧尾 → last 更新为新节点addFirst()创建新节点 → 新节点的 next 指向旧头 → 旧头的 prev 指向新节点 → first 更新为新节点removeFirst()first 指向第二个节点 → 新头的 prev 置为 null → 旧节点断开链接等待 GCremoveLast()last 指向前一个节点 → 新尾的 next 置为 null → 旧节点断开链接等待 GCgetFirst() / getLast() 直接通过 first / last 获取时间复杂度 O(1)按索引查询或删除需要从头或尾遍历时间复杂度 O(n)不需要连续内存空间没有扩容机制添加元素随用随建核心一句话双向链表 头尾指针 节点即加即建八、迭代器底层原理迭代器是一个设计模式提供统一方式遍历集合不暴露底层结构。每个集合都有自己的迭代器实现类底层依赖集合自身的数据结构。ArrayList 的迭代器底层持有一个 cursor 游标指针从 0 开始next() 返回 cursor 位置的元素然后 cursorhasNext() 判断 cursor ! size依赖数组索引按顺序遍历核心游标指针 数组索引遍历// 简化逻辑intcursor0;publicbooleanhasNext(){returncursor!size;}publicEnext(){returnelementData[cursor];}LinkedList 的迭代器底层直接持有节点引用维护一个 next 节点指针指向下一个要返回的节点next() 直接返回当前 next 节点的数据然后 next 往后移一个节点next next.nexthasNext() 判断 next ! null核心节点引用 沿着 next 指针向后遍历// 简化逻辑NodeEnextfirst;publicbooleanhasNext(){returnnext!null;}publicEnext(){Edatanext.item;nextnext.next;returndata;}集合迭代器底层依赖遍历方式ArrayList数组索引 cursor 游标按索引取元素LinkedList节点指针next沿着链表指针走九、泛型泛型是 JDK5 引入的特性可以在编译阶段约束操作的数据类型并进行检查。泛型的好处统一数据类型把运行时期的问题提前到了编译时期避免了强制类型转换可能出现的异常泛型的细节泛型中不能写基本数据类型指定泛型的具体类型后传递数据时可以传入该类型或其子类类型如果不写泛型类型默认是 Object泛型类当一个类中某个变量的数据类型不确定时就可以定义带有泛型的类。修饰符class类名类型{}例如public class ArrayListE { }创建该类对象时E 就确定类型。E 可以理解为变量但存的不是数据而是数据类型。常见写法T、E、K、V 等。泛型类 把数据类型当变量创建对象时再确定具体是什么类型。泛型方法当单个方法中某个参数或返回值的数据类型不确定时使用。修饰符类型返回值类型 方法名(类型 参数){}// 示例publicTTshow(Tt){returnt;}特点调用方法时确定类型泛型写在返回值前面。泛型接口当接口中某个数据类型不确定时使用。修饰符interface接口名类型{}// 示例publicinterfaceListE{voidadd(Ee);}特点实现类实现接口时确定类型。种类泛型声明位置确定类型时机示例泛型类类名后面创建对象时ArrayListString list new ArrayList()泛型方法返回值前面调用方法时show(hello)自动推断为 String泛型接口接口名后面实现接口时class MyList implements ListString泛型的继承和通配符泛型不具备继承性但是数据具备继承性泛型的通配符?? extends E—— 表示 E 及其子类? super E—— 表示 E 及其父类使用场景定义类、方法、接口时如果类型不确定可以定义泛型如果类型不确定但知道是哪个继承体系中的可以使用泛型的通配符泛型就是把类型当作参数传递类、方法、接口各自在需要时声明在使用时确定。十、二叉树基本概念节点的内部结构父节点地址、本身值、左子节点地址、右子节点地址度每一个节点的子节点数量二叉树中任意节点的度小于等于 2树高树的总层数根节点最顶层的节点左子节点左下方的节点右子节点右下方的节点根节点的左子树根节点的左子节点下的所有节点根节点的右子树根节点的右子节点下的所有节点二叉查找树二叉排序树 / 二叉搜索树特点有序摆放每一个节点上最多有两个子节点任意节点左子树上的值都小于当前节点任意节点右子树上的值都大于当前节点二叉树的四种遍历方式前序遍历根左右从顶部节点开始 → 当前节点 → 左子节点 → 右子节点中序遍历左根右从左子节点开始 → 左子节点 → 当前节点 → 右子节点后序遍历左右根从左子节点开始 → 左子节点 → 右子节点 → 当前节点层序遍历从顶部节点开始一层一层遍历十一、平衡二叉树AVL树任意一个节点的左右子树高度差不能超过 1|左子树高度 - 右子树高度| ≤ 1。平衡因子左子树高度 - 右子树高度取绝对值后应 ≤ 1。目的防止二叉查找树退化成链表保证查找效率为 O(log n)。二叉树的旋转操作维护平衡左旋右孩子上位原节点变成左孩子右孩子的左子树过继给原节点右旋左孩子上位原节点变成右孩子左孩子的右子树过继给原节点左旋和右旋互为镜像操作AVL 树四种失衡调整LL左左左子树的左子树插入 → 右旋RR右右右子树的右子树插入 → 左旋LR左右左子树的右子树插入 → 先左旋再右旋RL右左右子树的左子树插入 → 先右旋再左旋十二、红黑树红黑树是一种自平衡的二叉查找树每个节点包含五个属性父节点地址、本身值、左子节点地址、右子节点地址、颜色。红黑树的五个性质每一个节点是红色或者黑色根节点必须是黑色如果一个节点没有子节点或父节点则该节点相应的指针属性值为 Nil这些 Nil 视为叶节点每个叶节点Nil是黑色的如果某一个节点是红色那么它的子节点必须是黑色不能出现两个红色节点相连对每一个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点添加节点的规则红黑树在添加节点的时候添加的节点默认是红色的。添加节点后的修复规则设新节点为 N情况 1N 是根节点 → 将 N 改为黑色情况 2N 的父节点是黑色 → 不做调整情况 3N 的父节点是红色叔父节点是红色 → 父节点和叔父节点改黑祖父节点改红将祖父节点作为新 N 继续向上修复情况 4N 的父节点是红色叔父节点是黑色或 Nil4.1LL父节点是祖父的左子N 是父的左子 → 祖父右旋父节点改黑祖父节点改红4.2RR父节点是祖父的右子N 是父的右子 → 祖父左旋父节点改黑祖父节点改红4.3LR父节点是祖父的左子N 是父的右子 → 父节点左旋变成 LL 情况处理4.4RL父节点是祖父的右子N 是父的左子 → 父节点右旋变成 RR 情况处理十三、Set 系列集合Set 集合的特点无序、不重复、无索引。Set 是接口继承 Collection。Set 集合的实现类特点HashSet无序、不重复、无索引LinkedHashSet有序按插入顺序、不重复、无索引TreeSet可排序、不重复、无索引十四、HashSet底层数据结构是哈希表数组 链表 红黑树JDK8。核心特点无序存放元素不重复允许 null。底层结构默认情况只有数组长度 16哈希碰撞时数组 链表碰撞的地址下形成链表链表过长时≥ 8 且数组 ≥ 64数组 红黑树数组是常态链表是意外红黑树是极端兜底概率低于千万分之一存储原理添加元素时调用元素的 hashCode()计算哈希值哈希值运算后得到数组存储位置索引该位置为空 → 直接存入该位置已有元素哈希碰撞→ 调用 equals() 比较equals() 返回 true → 重复元素不存入equals() 返回 false → 存入形成链表JDK 7新元素插头部头插法JDK 8新元素插尾部尾插法判断重复的规则两个元素相等的条件hashCode()相同 equals()返回 true。重写 equals() 时必须同时重写 hashCode()保证两个 equals() 相等的对象hashCode() 也相等。初始容量与扩容默认初始容量16数组长度默认负载因子0.75扩容时机元素个数大于容量 × 负载因子16 × 0.75 12时触发扩容扩容方式容量翻倍16 → 32 → 64数组是懒加载new HashSet()时不创建数组第一次 add() 时才创建负载因子 0.75 的含义元素个数达到数组长度的 0.75 倍时触发扩容。0.75 是时间和空间的平衡点小于 0.75扩容太频繁浪费内存大于 0.75哈希冲突太多查找变慢0.75 是泊松分布计算的最优值链表与红黑树的转换条件链表长度大于等于 8 且数组长度大于等于 64 时链表转红黑树链表长度大于等于 8 但数组长度小于 64 时先扩容不转红黑树红黑树节点数小于等于 6 时红黑树转链表增加时以 8 为界定值减少时以 6 为界定值线程安全HashSet 线程不安全多线程同时修改时会抛出 ConcurrentModificationException。线程安全替代方案Collections.synchronizedSet(new HashSet())CopyOnWriteArraySet读多写少场景使用场景数据去重快速查找O(1)不需要保持顺序的集合存储核心要点默认就是数组只有哈希碰撞才出现链表链表转红黑树概率极低元素无序存放元素不允许重复hashCode equals 判断元素个数超过容量 × 0.75 时数组翻倍扩容。十五、LinkedHashSet底层是哈希表 双向链表。特点有序按插入顺序、不重复、允许 null。跟 HashSet 基本一致只多了一个点额外维护了一条双向链表把元素按添加顺序串起来所以遍历时按插入顺序输出。具体分工哈希表负责去重和查找跟 HashSet 一样双向链表负责记录插入顺序LinkedHashSet 独有判断重复、扩容、转红黑树都跟 HashSet 一样比 HashSet 略慢、多占内存多两个指针使用场景需要去重 需要保持插入顺序。十六、TreeSet底层是红黑树。特点元素自动排序自然顺序 / 自定义排序、不重复、不允许 null。增删改查时间复杂度为 O(log n)。排序方式自然排序元素实现 Comparable 接口String、Integer 默认就有比较器排序构造时传入 Comparator自定义排序规则与 HashSet 的区别特性HashSetTreeSet底层哈希表红黑树顺序无序自动排序时间复杂度O(1)O(log n)是否允许 null允许不允许使用场景需要排序去重取最大值、最小值范围查找总结开发中用得少知道底层是红黑树、元素自动排序就够了。大多数排序需求用数据库 ORDER BY 或 ArrayList Collections.sort() 解决。十七、双列集合Map双列集合的特点一次需要存一对数据分别为键和值键不能重复值可以重复键和值是一一对应的每一个键只能找到自己对应的值键 值这个整体称为键值对或键值对对象在 Java 中叫做 “Entry 对象”十八、Map 的通用 APIMap 是双列集合的顶层接口。put(K key, V value)—— 添加元素key 存在则覆盖 value返回旧 valuekey 不存在则新增返回 null注意key 一旦生成不能被 put 修改只能改 valueremove(Object key)—— 根据键删除键值对元素返回被删除的 valuekey 不存在返回 nullclear()—— 移除所有的键值对元素containsKey(Object key)—— 判断集合是否包含指定的键containsValue(Object value)—— 判断集合是否包含指定的值isEmpty()—— 判断集合是否为空size()—— 返回集合中键值对的个数十九、Map 的三种遍历方式键找值keySet先拿到所有 Key再逐个用 Key 取 Value。SetStringkeysmap.keySet();for(Stringkey:keys){Stringvaluemap.get(key);System.out.println(keyvalue);}特点只适合需要 Key 的场景。如果每次都要取 Value会多一次哈希查找效率略低。键值对entrySet—— 推荐直接把 Key 和 Value 打包成 Entry 对象一次性全拿出来。SetMap.EntryString,Stringentriesmap.entrySet();for(Map.EntryString,Stringentry:entries){Stringkeyentry.getKey();Stringvalueentry.getValue();System.out.println(keyvalue);}特点同时拿 Key 和 Value 时效率最高一次遍历全搞定。日常开发最常用。Lambda 表达式 forEachJava 8直接用 Map 自带的 forEach 方法配合 Lambda 简化代码。map.forEach((key,value)-{System.out.println(keyvalue);});特点代码最简洁配合 Stream 流式编程时非常方便。但遍历中不能删除元素会报并发修改异常。三种方式对比方式写法适用场景keySet先拿 Key 再 get(key)只需要 Key或偶尔取 ValueentrySet直接拿 Entry取 Key 和 Value需要同时用 Key 和 Value最推荐Lambda forEachmap.forEach((k,v) - {…})代码追求简洁配合 Stream 使用遍历时删除元素三种方式中只有迭代器Iterator能在遍历时安全删除。IteratorMap.EntryString,Stringitmap.entrySet().iterator();while(it.hasNext()){Map.EntryString,Stringentryit.next();if(条件){it.remove();// 安全删除}}增强 for 和 Lambda forEach 在遍历时删除都会报 ConcurrentModificationException。总结日常遍历用 entrySet 增强 for要删元素用迭代器要写流式代码用 Lambda forEach。二十、HashMap底层是哈希表结构和 HashSet 差不多依赖 hashCode 方法和 equals 方法保证键的唯一如果键存储的是自定义对象需要重写 hashCode 和 equals 方法如果只存储值自定义对象不需要重写这两个方法二十一、LinkedHashMap底层是哈希表数组 链表 红黑树 双向链表。特点有序按插入顺序、键不重复、值可重复、允许 null 键和 null 值。LinkedHashMap 是 HashMap 的子类底层完全一样只是多维护了一条双向链表把每个 Entry 按顺序串起来所以遍历时按插入顺序输出。具体分工哈希表 → 负责快速查找、去重跟 HashMap 一样双向链表 → 负责记录插入顺序LinkedHashMap 独有两种顺序模式默认 → 按插入顺序遍历构造传 true → 按访问顺序遍历每次 get/put 操作被访问的元素移到链表末尾性能比 HashMap 略慢多维护链表指针多占内存每个 Entry 多两个指针 before/after。使用场景需要保持插入顺序实现 LRU 缓存重写 removeEldestEntry开启访问顺序模式二十二、TreeMap底层是红黑树。特点Key 自动排序、键不重复、值可重复、不允许 null 键值允许 null。增删改查时间复杂度为 O(log n)。排序方式自然排序Key 实现 Comparable 接口String、Integer 默认就有比较器排序构造时传入 Comparator自定义排序规则与 HashMap 的区别特性HashMapTreeMap底层哈希表红黑树顺序无序Key 自动排序时间复杂度O(1)O(log n)是否允许 null 键允许不允许特有方法firstKey()/lastKey()→ 取最小 / 最大 KeylowerKey(key)/higherKey(key)→ 取小于 / 大于指定 Key 的最近 KeysubMap(fromKey, toKey)→ 截取从 fromKey 到 toKey 这一段使用场景需要 Key 有序取最小 Key / 最大 Key范围查找二十三、Collections 工具类Collections 是 Java 提供的一个操作集合的工具类里面全是 static 方法专门用来对 CollectionList、Set进行各种操作。注意它叫 Collections带 s和接口 Collection不带 s是两码事。排序sort(ListT list)—— 按自然顺序排序sort(ListT list, ComparatorT c)—— 按自定义比较器排序reverse(List? list)—— 反转顺序shuffle(List? list)—— 打乱顺序洗牌查找binarySearch(List? list, T key)—— 二分查找要求先排序max(Collection? coll)—— 取最大值min(Collection? coll)—— 取最小值frequency(Collection? c, Object o)—— 统计元素出现次数批量操作addAll(Collection? super T c, T... elements)—— 批量添加copy(List? super T dest, List? extends T src)—— 复制到另一个 Listfill(List? super T list, T obj)—— 全部填充为指定元素线程安全重点synchronizedList(ListT list)—— 把普通 List 转为线程安全的 ListsynchronizedSet(SetT set)—— 转为线程安全的 SetsynchronizedMap(MapK,V map)—— 转为线程安全的 Map不可变集合emptyList()/emptySet()/emptyMap()—— 返回空集合singletonList(T o)/singletonSet(T o)/singletonMap(K key, V value)—— 返回只有一个元素的集合unmodifiableList(List? extends T list)—— 返回只读 List不能增删改代码示例ListIntegerlistnewArrayList();list.add(3);list.add(1);list.add(2);Collections.sort(list);// [1, 2, 3]Collections.reverse(list);// [3, 2, 1]Collections.shuffle(list);// 随机打乱intmaxCollections.max(list);// 最大值intcountCollections.frequency(list,1);// 1 出现了几次// 转成线程安全的 ListListIntegersafeListCollections.synchronizedList(list);// 转成只读 ListListIntegerreadOnlyCollections.unmodifiableList(list);readOnly.add(4);// 抛异常 UnsupportedOperationException与 Arrays 工具类的区别特性CollectionsArrays操作对象CollectionList、Set数组常用方法sort、reverse、shuffle、binarySearchsort、fill、asList、toString一句话总结Collections 是集合的万能工具箱排序、打乱、取极值、转线程安全、转只读全都有。记住 sort、shuffle、synchronizedXxx 这三个最常用的就够了其他的用到再查。
