☰
Java数组与集合认证考点:HashMap树化与ArrayList扩容复盘
2026/11/4 18:42:30 网站建设 项目流程

公司内部的技术能力测评,历来有个反直觉的规律:真正拉开分数的往往不是那些看着唬人的框架原理题,而是数组和集合这种"每天在用、从没认真想过"的地基知识。我前后参与过两轮 Java 方向的专业力认证,第一轮就栽在一道关于 HashMap 的判断题上——题目给了初始容量和待插入元素个数,问会不会触发树化,我当时凭印象答了"会",错得很干净,因为漏掉了"table 数组长度必须达到 64"这个前置条件。那之后我把 Java 数组与集合这两块从头翻了一遍,第二轮才把分数提上来。这篇内容就是那次复盘的结果:讲这类认证考什么、背后对应哪些源码事实、哪些地方最容易翻车,以及怎么把这些考点顺手变成写代码时的肌肉记忆。不管你是准备应试,还是单纯想把 Java 基础补扎实,下面这些应该都用得上。

1. 这类认证考什么:数组与集合在能力测评里的真实权重

1.1 出题人偏爱的四类题型

翻过几套真题卷子你会发现,出题思路其实高度收敛,基本就四种套路。第一类是概念辨析,比如"ArrayList 和 LinkedList 谁更适合频繁插入",看着像送分题,实际上四个选项里往往有两个在特定条件下都成立,考的是你有没有想过"插入位置在头部还是中间""数据量有多大"这些前提。第二类是源码细节,典型问法是"ArrayList 无参构造后第一次 add 时容量是多少",答案是 10,但如果你答"构造时就是 10"就错了,JDK 8 里构造阶段拿到的是共享的空数组,扩容发生在第一次写入。第三类是行为预测,给一段代码问输出什么、抛不抛异常,比如在 for-each 里 remove 元素。第四类是工程选型,给一个业务场景让你挑容器,这类题没有标准答案,但评分点在于你能不能说清取舍理由。

这四类题的难度是递增的。前两类靠背书和看源码能拿下,后两类必须真的写过、踩过,才答得稳。我在第二轮备考时把重心全放在了第三、四类上,因为前两类属于"投入产出比高但天花板低"的部分,大家都背得会,拉不开差距。

1.2 为什么这两块内容天然是分水岭

道理不复杂。数组是 Java 里唯一一种"语言级"的聚合结构,它的行为由 JVM 规范直接定义,跟任何类库无关;集合框架则是 JDK 用纯 Java 代码搭出来的一整套抽象,从接口分层到具体实现的每一层优化,都写着设计者的取舍。前者考的是你对语言底层的理解是否精确,后者考的是你对数据结构与工程权衡的认知深度。这两样东西恰好是"培训班出来"和"真的写过项目"之间最容易暴露差距的地方。

我见过不少工作两三年的开发者,写业务代码时 List、Map 用得飞快,但一问HashMap的默认负载因子为什么是 0.75、为什么容量一定是 2 的幂,就答不上来。这不是能力问题,是从来没人逼着他们往下挖一层。认证考试的价值就在这里——它用一种不太舒服的方式,把你从 API 调用者的舒适区拽出来。

1.3 我自己排的复习顺序

顺序这事很关键,排错了会反复返工。我的做法是:数组 → List → Map → Set → 工具类 → 并发容器。先把数组吃透,因为集合的底层存储、扩容拷贝、toArray转换全都建立在数组之上;再攻 List,因为ArrayList的扩容逻辑是理解"容量"这个概念的最佳样本;然后才是 Map,HashMap一拿下,HashSet就是顺带的(它内部就是一个HashMap,value 是共享的常量对象);工具类放后面,因为Arrays和Collections里大量方法的行为依赖于前面几块的理解;并发容器放最后,属于加分项,考得不多但答出来很显功底。

这个顺序我用下来感觉最顺手,因为它符合"从具体到抽象、从单线程到并发"的认知梯度,不会出现"学着后面忘了前面"的情况。

2. 数组:三分钟学完语法,三年踩不完的坑

2.1 定长这个约束,决定了后面所有行为

数组最本质的特征只有一个:长度在创建那一刻就固定了,之后永远不变。这一个约束推导出了后面几乎所有考点。因为长度不可变,所以"扩容"这件事在数组层面根本不存在,你只能新建一个更大的数组,再把旧数据拷过去——ArrayList的grow()干的正是这件事,Arrays.copyOf()干的也是这件事。因为长度不可变,所以数组没有任何add、remove方法,所有"增删"在数组语境下都是"覆盖"或"搬运"。

还有几个容易被忽略的事实:数组是对象,继承自Object,所以你可以对它调用getClass()、hashCode()、clone();数组的长度是字段length而不是方法length(),字符串才是方法,这一点在笔试填空题里被坑过的人不在少数;数组创建后元素有默认值,int是 0、boolean是false、char是'\u0000'、引用类型是null,这个默认值规则和成员变量一致,但和局部变量必须显式初始化完全不同。

类型默认值备注
byte / short / int / long0数值零值
float / double0.0注意是 0.0 不是 0
char'\u0000'打印出来是不可见字符,不是空格
booleanfalse只有两个值
引用类型null包括 String、数组本身

另一个高频点是数组协变。String[]是Object[]的子类型,所以Object[] arr = new String[3];这行代码能编译通过。但如果你往里塞一个Integer,编译期也不报错,运行时直接抛ArrayStoreException。这是 Java 数组设计上的一个历史遗留问题(为了早期泛型缺失时能用),而泛型恰恰相反,是不变的:List<String>不是List<Object>的子类型,这行代码根本编译不过。这个"数组协变、泛型不变"的对比,几乎每套卷子都会出现。

2.2 二维数组不是矩阵,是"数组的数组"

很多人脑子里把int[][]想成一个矩形表格,这个心智模型会在关键时刻骗你。Java 的二维数组本质是一维数组,每个元素又是一个一维数组的引用。所以int[][] a = new int[3][4]是先创建一个长度 3 的数组,再分别为三个位置各创建一个长度 4 的数组。而int[][] b = new int[3][];同样合法,此时外层数组有 3 个 null 槽位,每行需要你单独new。

这就引出了不规则数组的概念:每一行的长度可以不一样。

int[][] ragged = new int[3][]; ragged[0] = new int[]{1}; ragged[1] = new int[]{2, 3}; ragged[2] = new int[]{4, 5, 6};

如果你按"矩形"的思维去写ragged[0][2],运行时会抛ArrayIndexOutOfBoundsException。而ragged.length拿到的是 3(行数),ragged[0].length拿到的是 1(第一行的列数),这两个值在不规则数组里没有任何固定关系。考试里常见的陷阱题是让你遍历一个不规则二维数组却用a[0].length当列数上限,第二行开始就越界了。

顺带说一个性能相关的点:因为是"数组的数组",内存上每一行是独立分配的对象,在堆上并不保证连续。所以对二维数组做整体遍历时,按行遍历(外层行、内层列)比按列遍历缓存友好得多,这个差异在数据量大时非常明显,属于典型的"能跑和跑得快"的区别。

2.3 Arrays 里那几个"名字像、行为不像"的方法

java.util.Arrays是个宝藏工具类,但里面几个方法的行为差异极大,考试爱考,实际开发中也爱出错。

先说Arrays.asList()。它返回的不是java.util.ArrayList,而是Arrays的一个私有静态内部类,叫Arrays$ArrayList。这个类继承AbstractList,内部直接持有传进来的数组引用,所以它是定长的:调用add、remove、clear会抛UnsupportedOperationException,但set可以正常用(因为它只是改数组元素)。更隐蔽的坑是:它和原数组共享同一份存储,你改数组,List 里的值跟着变,反过来也一样。还有一个经典事故是传基本类型数组进去:Arrays.asList(new int[]{1,2,3})得到的不是三个元素的 List,而是一个只含一个元素的 List,那个元素就是整个int[],因为泛型只能接引用类型,int[]被当成了一个Object。要用包装类型数组才符合预期。

再说Arrays.sort()。它对基本类型数组用的是双轴快速排序(Dual-Pivot Quicksort),不稳定;对对象数组用的是 TimSort,稳定。这个差异是故意的:基本类型没有"相等但不同"的概念,稳定性没意义,用快排更快;对象类型排序时相同的 key 保持原有相对顺序往往有业务含义,所以要稳定。考试里如果问"排序后相等元素的顺序会不会变",你得先看数组是什么类型。

Arrays.binarySearch()有个硬性前提:数组必须已经升序排好,否则结果未定义(注意是"未定义",不是"返回 -1")。它的返回值也很有特点:找到了返回索引,没找到返回-(插入点) - 1,这个设计是为了让你能通过-(返回值) - 1直接算出应该插入的位置,同时保证"找不到"时返回值一定是负数,不会和索引 0 混淆。

Arrays.copyOf和System.arraycopy也常被拿来对比。前者返回一个新数组,长度可以比原数组长(多出来的位置填默认值)或短(截断),底层其实调用的就是后者;后者是把源数组的一段拷到已存在的目标数组的指定位置,返回 void。要扩容或缩容,用copyOf;要在已有的大数组里填充一段,用arraycopy。

2.4 可变参数与数组之间那层隐式转换

Object...这种写法编译器会给你转成Object[],所以本质上它就是个数组,这也意味着两件事。第一,方法签名里foo(String[] arr)和foo(String... arr)是同一个方法,不能重载。第二,传参时的行为有微妙差异。

public static void demo(Object... args) { System.out.println(args.length); } demo(1, 2, 3); // 3,自动装箱成 Integer[] demo(new Integer[]{1, 2}); // 2,直接当作数组 demo(new int[]{1, 2}); // 1!整个 int[] 被当成一个 Object

最后一行是很多人想不到的:int[]是引用类型,是Object的子类,所以它作为一个整体被塞进了Object[]里,长度自然是 1。这个坑在日志框架、String.format一类的 API 里都真实出现过。解决办法要么显式装箱成Integer[],要么别用基本类型数组接可变参数。

另外,可变参数如果传null,会有一个警告级的歧义:demo(null)到底是"传一个 null 元素"还是"传一个 null 数组",编译器只能提示你加类型转换。这个细节在代码审查里经常被指出来。

3. 集合框架:先认清分层,再谈选型

3.1 Collection 与 Map 是两条互不相交的血脉

初学者容易把Map当成Collection的一种,这是错的。JDK 里Collection和Map是两个完全独立的顶层接口,没有任何继承关系。之所以看起来像一家人,是因为Map的keySet()、values()、entrySet()返回的视图都是Collection的子类型。

Collection下面分三支:List(有序、可重复、有索引)、Set(不重复,HashSet无序、LinkedHashSet保插入序、TreeSet保排序)、Queue/Deque(队列语义,ArrayDeque做栈比Stack更好,因为Stack继承自Vector,所有方法都加了同步,单线程下纯属浪费)。Map则独立成树:HashMap、LinkedHashMap、TreeMap、Hashtable、ConcurrentHashMap,各自解决不同问题。

搞清楚这个分层之后,很多题目就好答了。比如问"HashSet怎么保证元素不重复",答案不在HashSet里——它内部就一个HashMap,add(e)实际是map.put(e, PRESENT),靠HashMap的 key 唯一性实现。再问"LinkedHashMap怎么保持顺序",它继承HashMap,只是在节点上加了before/after两个指针串成双向链表,插入时维护链表即可;而且构造参数accessOrder=true时,每次get也会把节点挪到链表尾部,这就是一个现成的 LRU 骨架。

3.2 ArrayList 的扩容曲线与 fail-fast 的真实边界

ArrayList的容量增长是 1.5 倍,源码里就一行:int newCapacity = oldCapacity + (oldCapacity >> 1);。用位移代替除以 2,是早期 JVM 上的一点微优化,现在 JIT 早就把这个差异抹平了,但代码保留了下来。为什么选 1.5 而不是 2?因为 2 倍增长在多次扩容后空间浪费会累积得很快,1.5 倍在"拷贝次数"和"空间浪费"之间取了个折中,还能让释放的旧空间有机会被后续分配复用。

JDK 8 里有个容易被忽略的细节:无参构造时elementData被赋值为共享的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA,真正的 10 容量是在第一次add时才分配的。这个懒初始化设计是为了省内存——大量创建却从不写入的空列表不再各占一个 10 元素数组。所以"new ArrayList<>()之后容量是多少"这个问题,严格答案是"0,第一次添加后变 10"。

modCount与ConcurrentModificationException这对组合也是必考点。ArrayList内部维护一个修改计数器,每次结构性修改(增、删)都会modCount++;迭代器创建时把当前值存进expectedModCount,每次next()前检查两者是否相等,不等就抛异常。这里有两个关键认知:一是fail-fast 是"尽力而为"的检测机制,不保证一定触发,规范里明说了它只能用来发现 bug,不能用来做并发正确性保障;二是只有迭代器自己的remove()/add()会同步更新expectedModCount,直接调集合的remove()不会,所以前者安全、后者抛异常。

3.3 LinkedList 的性能传说,得靠实测戳破

"频繁插入删除用LinkedList"这句话几乎是 Java 圈的都市传说,但它的成立条件窄得惊人。LinkedList是双向链表,插入删除本身确实是 O(1),可问题在于你得先找到那个位置。add(int index, E e)内部会调用node(index)定位节点,虽然用了折半查找(索引小于一半从头找,否则从尾找),复杂度仍然是 O(n)。

我做过一个简单的对照实验,往头部、中部、尾部分别插入 10 万条数据:

操作位置ArrayList 耗时(相对值)LinkedList 耗时(相对值)
头部插入极慢(每次全量搬移)快
中部随机插入慢慢(定位成本占主导)
尾部追加快(均摊 O(1))快
随机 get(i)快(O(1))极慢(O(n))

结论很清楚:LinkedList只在头部插入和已有迭代器位置上的插入删除这两个场景有优势,其余情况几乎全面落后。再加上每个节点要多维护两个引用、对象头开销也大,内存占用可能是ArrayList的两三倍,而且链表节点在堆上分散,缓存命中率极差。所以在实际项目里,我基本只在需要Deque语义(当队列或栈用)时才选它,ArrayDeque反而是更常见的首选。

3.4 HashMap 的扰动、扩容与树化三重门

HashMap是集合部分考得最深的一块,得拆成三层看。

第一层是哈希扰动。put时不是直接拿key.hashCode()当哈希值,而是走了一步h = key.hashCode(); h ^= (h >>> 16);,把高 16 位异或到低 16 位上。为什么要多这一步?因为定位桶用的是(n - 1) & hash,当数组长度不大时(比如 16,n-1是 0b1111),只有哈希值的低 4 位参与运算,高位完全浪费。扰动之后,高位信息被"折叠"进低位,哈希分布更均匀,冲突率明显下降。

第二层是扩容。默认容量 16、负载因子 0.75、阈值 12,这三个数字要一起记。容量必须是 2 的幂,因为只有这样(n-1) & hash才等价于取模,而位运算比取模快得多。0.75 这个值是空间与时间的折中,源码注释里提到过,在泊松分布假设下,负载因子 0.75 时桶内节点数达到 8 的概率约为千万分之六,这正是树化阈值定在 8 的依据之一。JDK 8 的扩容做了个漂亮的优化:不需要重新计算哈希,因为容量翻倍后元素的新位置要么在原索引j,要么在j + oldCap,只需看hash & oldCap是否为 0,据此把原链表拆成 lo、hi 两条链直接挂过去,避免了 JDK 7 里每个节点重算索引的开销。

第三层是树化。链表长度达到 8 时,treeifyBin会被调用,但它内部会先检查 table 长度是否达到 64,没达到就只做一次 resize 而不树化。这个前置条件是最高频的失分点,我第一轮就是栽在这。反过来,树节点数量减少到 6 时会退化回链表,留出 7 这个缓冲带是为了避免在 7、8 之间反复震荡。另外 JDK 8 把插入方式从头插改成了尾插,顺带修掉了 JDK 7 并发扩容时链表成环导致 CPU 打满的老问题——虽然HashMap本来就不是线程安全的,但至少不会死循环了。

4. 笔试现场最容易翻车的几处细节

4.1 equals 与 hashCode 不配对:查不到、删不掉

HashMap判断两个 key 相等用的是两步:先比哈希值,哈希相同再调equals。如果你自定义类只重写了equals没重写hashCode,两个"逻辑相等"的对象哈希值不同,会被分到不同的桶里,map.get(new Key(...))直接返回 null,map.remove(...)也删不掉,但map.size()还在涨。这个 bug 极隐蔽,因为集合本身不报错,只是行为"诡异"。

反过来只重写hashCode不重写equals,默认的equals是引用比较,两个哈希相同的不同对象仍然不相等,只是会堆在同一个桶里形成链表,性能退化但结果"看起来正常",更难发现。

我习惯的做法是:只要这个类会作为 Map 的 key 或放进 Set,就用 IDE 生成成对的equals和hashCode,或者用Objects.equals和Objects.hash手写。另外参与计算的字段必须是不可变的,如果对象放进HashSet之后又改了参与哈希的字段,这个元素就永远找不回来了,因为它被"锁"在了旧的桶里。

4.2 遍历中删元素:三种正确姿势和一种经典错误

for-each 里删元素是考试和线上的双料常客:

// 错误示范:必抛 ConcurrentModificationException for (String s : list) { if (s.startsWith("a")) list.remove(s); }

正确姿势有三种。一是用迭代器,Iterator.remove()会同步更新expectedModCount;二是用removeIf,JDK 8 引入,内部就是迭代器实现,写起来最干净:list.removeIf(s -> s.startsWith("a"));;三是倒序普通 for 循环,从size()-1往 0 遍历,删除后不会影响未遍历部分的下标。顺带提醒,正序普通 for 循环边遍历边删也是错的,会漏元素,而且不抛异常,属于"静默错误",比抛异常更危险。

值得补充的是,CopyOnWriteArrayList在遍历时删除不会抛异常,因为它遍历的是创建迭代器那一刻的快照,你删掉的是新数组里的元素,迭代器根本看不见。这个特性适合读多写极少的场景(比如监听器列表),但绝不适合频繁写,因为每次写都要复制整个数组。

4.3 泛型擦除:编译期过得去,运行期炸得响

泛型在编译后会被擦除成原始类型,List<String>和List<Integer>在运行时是同一个Class,new ArrayList<String>().getClass() == new ArrayList<Integer>().getClass()返回true。由此衍生出一串限制:不能new T[](运行时不知道 T 是什么),不能对泛型做instanceof(o instanceof List<String>编译不过),静态成员不能用类的类型参数,基本类型不能当类型参数(List<int>非法,只能List<Integer>)。

重载上的坑更隐蔽:void f(List<String> a)和void f(List<Integer> b)不能共存,因为擦除后签名完全一样,编译器直接报"名称冲突"。而List<String>和List作为参数却可以共存,因为一个是泛型一个是原始类型,擦除后签名不同。

4.4 自动装箱缓存与 == 的边界

Integer a = 127, b = 127; System.out.println(a == b); // true,命中缓存 Integer c = 128, d = 128; System.out.println(c == d); // false,超出缓存

Integer.valueOf会缓存 -128 到 127 之间的实例,这个区间是 JLS 强制要求的,上限可以通过启动参数-XX:AutoBoxCacheMax调大,但下限固定。所以==比较包装类型的行为依赖数值范围,这属于典型的"看似对、其实错"。Long也是 -128 到 127,Boolean只有两个常量,Character是 0 到 127。结论很简单:包装类型一律用equals或Objects.equals比较,==只拿来判 null。

还有一个容易忽略的:Integer和int混合运算时会发生拆箱,如果此时Integer是null,直接NullPointerException。三元表达式里混用包装和基本类型也会触发拆箱,这类空指针在线上查起来相当费劲。

5. 把考点变成工程习惯:容量、不可变与选型表

5.1 初始化容量怎么算才不浪费

ArrayList很简单,预估元素个数 n 就直接new ArrayList<>(n),避免多次扩容拷贝。HashMap则有个容易算错的地方:构造参数传的是容量,但真正生效前会被tableSizeFor向上取整到 2 的幂,而阈值是容量的 0.75 倍。所以如果你的目标是"存 n 个元素且一次都不扩容",正确算法是:

int initialCapacity = (int) (n / 0.75f) + 1; Map<String, String> map = new HashMap<>(initialCapacity);

举个具体例子。要存 100 条数据,100 / 0.75 ≈ 133,加 1 得 134,tableSizeFor(134)返回 256,阈值变成 192,够用且不扩容。如果偷懒写new HashMap<>(100),tableSizeFor(100)返回 128,阈值只有 96,第 97 个元素进来就触发一次扩容,前面预分配的意义全没了。这个小细节在性能敏感的批处理代码里差别不小。

5.2 不可变集合与防御性拷贝

Collections.unmodifiableList(list)返回的是视图,不是副本,原列表改动会同步反映到不可变视图上,所以它挡得住"通过视图修改",挡不住"通过原引用修改"。真正的防御性拷贝得用new ArrayList<>(list)再包一层,或者直接用List.copyOf(list)(JDK 10+)——后者会做一次真正的复制,且返回的结果不可变。

List.of()、Set.of()、Map.of()这几个工厂方法也是常用选择,但有两个硬性限制:不接受 null 元素(传 null 直接 NPE),不允许重复元素(Set.of("a","a")抛IllegalArgumentException)。Arrays.asList()反而允许 null,定位不同,别混用。

返回集合给外部时,我现在的习惯是:能返回不可变集合就返回不可变的,必须可变的话就返回拷贝。这个习惯是被一次线上问题逼出来的——某个 getter 直接返回了内部List,调用方顺手clear()了一下,结果整个缓存都空了。

5.3 一张能直接抄的选型决策表

需求场景首选实现关键理由
绝大多数有序集合,随机访问多ArrayList连续内存、索引 O(1)、遍历缓存友好
拿它当队列或栈用ArrayDeque比LinkedList内存更省,比Stack少了同步开销
需要去重,不关心顺序HashSet底层 HashMap,均摊 O(1)
需要去重且保留插入顺序LinkedHashSet额外维护双向链表,代价是每个元素多两个指针
需要按 key 排序遍历TreeMap红黑树,O(log n),支持范围查询
想做 LRU 缓存LinkedHashMap+accessOrder=true重写removeEldestEntry即可
单线程键值存储HashMap综合性能最好
多线程读多写少ConcurrentHashMapJDK 8 用 CAS + 桶头加锁,粒度细
读极多写极少,且要遍历安全CopyOnWriteArrayList写时复制,遍历不加锁

这张表我在实际评审代码时常用,大部分"选错容器"的问题对照一遍就能定位。

5.4 两周的备考节奏怎么排

最后说说时间安排,这块是我踩过坑的地方——第一轮我花了一周死磕源码,结果真题一套没做,上了考场发现题目考的角度和我想的完全不一样。

调整后的节奏是:前 5 天过知识面,数组 1 天、List 1 天、Map 2 天、Set 和工具类 1 天,每天配合手写代码验证,比如自己实现一个简易的HashMapput 流程,比看十遍源码管用。中间 4 天刷题,重点刷行为预测类和源码细节类,错题必须回源码定位,不能只记答案。后 3 天做整卷,掐时间,模拟考场状态,把答题速度练出来。剩下 2 天机动,专门补错题本上反复出错的点。

还有个我觉得特别有效的方法:把每个知识点讲给别人听一遍。讲不通的地方就是没懂的地方。我当时拉着一个刚入行的同事,每天下班前花二十分钟给他讲一块内容,讲HashMap树化条件那次,讲到一半自己卡住了,回头翻源码才发现漏了 table 长度 64 的前置判断——那个知识点后来再没忘过。

最后再分享一个小技巧:做题时遇到"以下说法正确的是"这类多选题,凡是出现"一定""必然""总是"这种绝对化措辞的选项,先打个问号。Java 集合的行为大量依赖前置条件,绝对化描述十有八九是陷阱。这个判断习惯帮我捡回了不少分。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询