Java集合和时空复杂度是数据结构DAY1最该先建立的两个概念。很多人学数据结构喜欢上来就啃红黑树、跳表、B树的底层实现结果三天后心态崩溃。我带的经验是反过来把集合框架和时空复杂度作为第一天的主线先搞清现成工具怎么选、怎么用、快在哪、慢在哪再带着问题去读源码效率完全是两个量级。集合是什么它是Java里最常用的数据结构容器ArrayList、HashMap这些名字几乎每天出现在代码里时空复杂度则是衡量代码快慢、占用内存多少的尺子。今天这篇JAVA数据结构DAY1笔记就把这两件事串起来讲清楚集合怎么分类、怎么选型大O记号怎么读常用集合操作的时间、空间成本到底是多少。适合谁看刚接触数据结构的Java新手、准备面试但基础不牢的求职者以及平时写业务代码、很少关注性能的开发者。不需要前置知识打开任意一款你顺手的IDE跟着第五节的例子敲一遍效果比只看不练强十倍。1. 集合框架——先学会用再研究底层1.1 为什么第一课主线是集合而不是算法很多人把“数据结构”等同于“算法”一上来就刷题。但落到实处大多数业务代码里90%的数据操作是在给数据找一个合适的“容器”要按顺序存、要按值快速查、要保证不重复、要记录键值对应关系。Java的集合框架Collections Framework就是这些容器的标准答案它把接口、实现类、算法三者打包好直接用就行。更重要的是集合框架是学习时空复杂度的最佳载体。ArrayList查询快、插入慢LinkedList反过来HashSet去重快但打乱顺序TreeSet有序但插入变慢——这些“快慢差异”背后正是时间复杂度的具体体现。把集合用熟了复杂度概念就不再是数学公式而是你摸得着的体验。这门课真正难的地方不是记住某个类的名字而是在具体场景里判断“该用哪一个”这种判断力只能靠先建立整体地图、再逐个击破的路径来培养。1.2 集合框架的地图接口、实现类、选择口诀先给一张地图。集合框架最顶层的接口是Collection往下分三支List列表有序可重复、Set集合无序不可重复、Queue队列先进先出。Map不走Collection分支它单独成一个体系存键值对。记住一句话Collection存单列元素Map存双列映射。常用实现类可以浓缩成一张表接口常用实现类核心特点ListArrayList动态数组按下标访问O(1)尾部插入快ListLinkedList双向链表头尾增删快按下标访问慢SetHashSet基于哈希表查找/插入O(1)均摊无序SetLinkedHashSet在哈希基础上维护插入顺序SetTreeSet基于红黑树元素自动排序操作O(log n)MapHashMap哈希表键值存取O(1)均摊无序MapLinkedHashMap哈希链表保留插入顺序或访问顺序MapTreeMap红黑树键自动排序操作O(log n)选择口诀我总结为要下标快取用ArrayList头尾频繁增删用LinkedList去重用HashSet要排序用TreeSet/TreeMap要键值对且无序用HashMap要保留插入顺序的键值对用LinkedHashMap。先背口诀特例后面踩坑了再回来修正。注意这张表只是“默认答案”真实的选型还要结合读多还是写多、数据量多大、要不要并发等维度后面几天我们会逐个展开。2. 三大接口家族List、Set、Map 的取舍逻辑2.1 List有序可重复数组思维的延续List保存一组有序、可重复的元素允许下标访问。最常见的是ArrayList和LinkedList。ArrayList底层就是一个Object数组当元素个数超过容量时自动扩容新容量大约是原来的1.5倍源码里的计算是oldCapacity加上oldCapacity右移一位。因为底层是连续数组按下标get是O(1)直接根据下标算出内存地址就行但中间插入或删除时后面的元素要整体前移或后移是O(n)。尾部add则基本是O(1)只有触发扩容时才多一些拷贝开销所以叫“均摊O(1)”。LinkedList底层是节点链每个节点持有前驱、后继的引用。头尾add/remove是O(1)只需要改指针但按下标get(n)必须从头部或尾部逐节点走是O(n)。中间插入看起来也是O(1)前提是你已经拿到了那个位置的迭代器如果只按下标插入定位本身还是O(n)。实际开发里两者差异非常直观一万个元素的列表按下标遍历ArrayList毫秒级LinkedList可能慢几十倍。因为链表跳跃访问时缓存命中率很差真实世界的常数开销比理论上更大。所以别迷信“链表插入快”这句话它只对头尾操作成立。2.2 Set唯一性的背后是哈希与排序Set的核心语义是“不重复”。HashSet用哈希表实现add时先算hashCode定位桶再判断是否存在相同元素均摊O(1)正因为无序它不保证迭代顺序。LinkedHashSet在哈希基础上额外用链表记录插入顺序适合既要唯一性又要“按插入顺序遍历”的场景代价是多一点内存。TreeSet用红黑树实现元素按自然顺序或自定义比较器排列。add、contains都是O(log n)虽然比HashSet慢但好处是遍历时天然有序还能取头尾、查范围子集。面试里经常考的两个点要提前心里有数一是HashSet必须配合正确的equals和hashCode否则“去重”会失效二是TreeSet对元素要求要么实现Comparable、要么构造时传入Comparator否则add会抛ClassCastException。这里有个很典型的对比场景如果需求是“把用户ID去重并按ID从小到大输出”TreeSet一行搞定但同样的量级如果你只要求去重、不在乎顺序HashSet会快很多。顺序是有代价的这个代价就是O(1)和O(log n)的差距。2.3 Map键值对的三种形态与哈希的本质Map是键值对容器业务里在线用户状态、统计频次、配置缓存全是它。HashMap是默认选择底层是“数组链表”JDK8后链表过长会转红黑树通过key的hashCode定位桶均摊O(1)。负载因子默认0.75意思是元素个数达到容量×0.75时扩容翻倍。这个0.75是时间与空间的折中太小浪费内存太大碰撞变多、性能下降。LinkedHashMap在HashMap基础上加了双向链表可以保持插入顺序还支持“访问后调到末尾”的LRU行为做简单缓存很顺手。TreeMap则按键排序操作是O(log n)适合需要有序遍历或范围查询的键值场景。强调一个本质HashMap的O(1)建立在“哈希均匀”的前提上。如果key的hashCode写得稀烂所有元素挤到同一个桶JDK8之前最坏会退化到O(n)JDK8之后桶内转红黑树能压到O(log n)但已经是另一种量级了。所以自定义类做key时一定要重写hashCode和equals别偷懒。3. 时间复杂度——用数学眼光衡量程序快慢3.1 大O记号到底在说什么大O描述的是“当输入规模n足够大时操作次数随n增长的趋势”它不关心精确的执行时间只关心增长量级。因此有两个默认规则忽略常数项3n和100n都算O(n)忽略低阶项n1000、2nn都算O(n)。大O还默认讨论最坏情况因为最坏情况才是性能的兜底。判断方法很机械数代码里关键操作的重复次数。一次算术或一次比较算常数O(1)循环执行n次是O(n)两层嵌套循环每层都到n是O(n²)每一轮都把问题规模减半是O(log n)外层n次、内层减半是O(n log n)。一个容易混淆的点是“实际耗时”和“复杂度”的关系。复杂度告诉你的是增长趋势不是秒表读数。比如在n很小的时候O(n²)的冒泡排序可能比O(n log n)的归并排序更快因为常数小、实现简单但当n上到一万、十万趋势主导一切差值会呈指数级拉开。所以分析复杂度时想的应该是“n增大100倍会怎样”而不是“现在跑几毫秒”。3.2 五个常见复杂度级别的代码实例代码说话。O(1)数组按下标取元素无论数组多大都只是一次内存寻址。int[] arr {10, 20, 30}; System.out.println(arr[1]); // 固定一步和数组长度无关O(n)普通循环n个元素就做n次操作。int sum 0; for (int i 0; i n; i) { sum arr[i]; }O(log n)二分查找。每轮区间减半n到1大约需要log2(n)轮。int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) return mid; if (arr[mid] target) low mid 1; else high mid - 1; }O(n log n)经典的归并排序、快速排序平均情况就是这种结构外层对每个元素做一次处理每步又伴随log n级别的分治。O(n²)两层循环分别到n典型是冒泡排序的双重比较。for (int i 0; i n; i) { for (int j i 1; j n; j) { // 比较或者交换 } }初学最容易忽略的是常数差异O(n)和O(2n)本质都是O(n)但真实运行还是差两倍。大O是分类学不是计时器它帮你看趋势具体优化还要回到代码本身。3.3 常用集合操作的复杂度对照表把常见集合的关键操作汇总成一张表面试和日常选型都够用了数据结构按下标访问按值查找插入删除按值ArrayListO(1)O(n)尾部均摊O(1)中间O(n)O(n)LinkedListO(n)O(n)头尾O(1)中间O(n)O(n)HashSet-O(1)均摊O(1)均摊O(1)均摊TreeSet-O(log n)O(log n)O(log n)HashMap-O(1)均摊O(1)均摊O(1)均摊TreeMap-O(log n)O(log n)O(log n)有个细节值得单独说常说的“HashMap O(1)”是均摊意义下的因为哈希碰撞不可避免扩容时也要重新散列极端数据下可能有退化。而ArrayList“尾部插入O(1)”同样是均摊因为扩容偶尔发生。理解“均摊”这个词比背下复杂度数值更重要。4. 空间复杂度——容易被忽略的隐形账单4.1 空间复杂度的两种口径和计算方式空间复杂度衡量的是“程序运行时额外占用的内存规模随n的变化”同样用大O表示。计算时通常看三块基本变量常数、数组或容器跟n成正比、递归调用栈跟递归深度成正比。实际题目里更常说的是“额外空间”——即除了输入本身你新开辟了多少内存。举两个反转数组的例子。原地反转只用一个temp变量额外空间O(1)for (int i 0; i arr.length / 2; i) { int temp arr[i]; arr[i] arr[arr.length - 1 - i]; arr[arr.length - 1 - i] temp; }新建数组反转额外空间O(n)int[] copy new int[n]; for (int i 0; i n; i) { copy[i] arr[n - 1 - i]; }两者都解决同一问题但内存账单差一个量级。递归也容易踩空间坑深度为n的递归每次调用都要压栈额外空间O(n)n特别大时可能栈溢出。所以看到递归先想想深度别光盯着时间复杂度。4.2 集合对象背后真实的内存开销空间复杂度不只存在于算法题日常Java代码的内存膨胀很大一部分来自集合对象本身。ArrayList虽然逻辑上是一排元素底层数组容量经常大于元素个数扩容后可能留有空位LinkedList每个节点是一个Node对象除了数据还要存前驱、后继两个引用一个int的代价远不止4字节HashMap每个键值对一个节点加上table数组可能是容量的若干倍。包装类型也在偷偷吃内存。int是4字节Integer对象带上对象头可能16字节起步用HashMapInteger, Integer时每个键和值各自封箱成对象内存翻好几倍。数据量大时这个问题就是实打实的OOM风险。实用建议能估计规模就给集合指定初始容量能少封箱就少用包装类型能复用对象就复用别让GC替你还债。一条经验是宁可初始容量给大一点也不要频繁扩容。扩容不只是数组拷贝还涉及哈希类容器重新散列所有现有元素这是O(n)级别的操作。比如你预计要存一万个键值对直接new HashMap(10000 / 0.75f 1)这种写法比默认容量一路resize到够用要省下不少时间。5. 实操练习与踩坑记录5.1 三组适合第一天的入门练习第一组统计一段文本中单词出现次数体会HashMap的getOrDefault。String text apple banana apple orange banana apple; String[] words text.split( ); MapString, Integer counter new HashMap(); for (String word : words) { counter.put(word, counter.getOrDefault(word, 0) 1); } System.out.println(counter); // {apple3, banana2, orange1}第二组用TreeSet对数组去重并排序体会Set语义和自动排序。int[] data {5, 3, 8, 5, 1, 9, 3, 8}; SetInteger set new TreeSet(); for (int num : data) set.add(num); System.out.println(set); // [1, 3, 5, 8, 9]第三组用LinkedList当队列实现先进先出体会Queue接口的offer/poll。QueueString queue new LinkedList(); queue.offer(A); queue.offer(B); queue.offer(C); while (!queue.isEmpty()) { System.out.println(出队: queue.poll()); } // A B C三组代码分别覆盖Map、Set、Queue三条线复杂度不超过O(n log n)第一天的目标就是把API用顺、把复杂度感受建立起来。写完再回去看每个操作的复杂度会有“原来如此”的感觉。5.2 我踩过的几个典型坑第一个坑边遍历边删除集合元素报ConcurrentModificationException。foreach本质是迭代器遍历期间直接调用list.remove会破坏迭代状态。正确做法是iterator.remove()或者Java8后用removeIf。第二个坑自定义对象放进HashSet没重写equals和hashCode去重完全失效。HashSet判断重复先比hashCode命中再比equals两个都不实现等于在比对象引用内容相同的对象也会被当成不同元素。这个坑在面试里出现的频率极高。第三个坑用比较Integer。Java对-128到127的Integer有缓存这段范围内比较为true超出范围同样的写法返回false非常隐蔽。对象比较一律用equals。第四个坑循环里反复调用ArrayList的remove(i)。每次remove都要移动后续元素单次O(n)循环n次就是O(n²)数据量上万就肉眼可见地卡。要么倒序删除要么用removeIf要么先标记后统一删。5.3 常见问题速查表把上面的知识点压成一张查表写代码遇到问题时打开看一眼现象可能原因方案遍历中删除抛ConcurrentModificationException迭代器状态被破坏iterator.remove() / removeIfHashSet没有真正去重未重写equals/hashCode自定义类重写这两个方法Integer用比较结果不符合预期缓存范围外的比较用equalsHashMap查询突然变慢hashCode分布差碰撞过多重写更均匀的hashCode频繁扩容导致性能波动、内存大未设置初始容量按预估容量创建集合列表大量中间删除非常慢remove(i)循环导致O(n²)removeIf、倒序删、改用LinkedList最后说点个人感受。我见过很多同学把TreeMap的源码背得滚瓜烂熟但真让他写一个统计词频的程序第一反应还是数组加一堆if最后又乱又慢。这不是智力问题是对“容器”缺少直觉。第一天的集合和时空复杂度核心就是建立这种直觉看到需求想到容器看到容器想到它的时间空间账单。按这个思路学下去后面无论啃红黑树、B树还是并发容器你都会带着明确的问题去读源码而不是为了背而背。数据结构这门课真正的门槛从来不是记忆而是“选择”。