★ FEATURED ARTICLE 1. 集合框架的家底先从继承体系看起做Java开发的人工作里几乎天天跟集合打交道。我刚入行那会儿写代码就是一股脑new ArrayList()和new HashMap()至于为什么选它们、底层到底干了什么说实话是讲不清楚的。直到后来被面试官连着追问了几个为什么又自己动手翻了源码才真正把这俩家伙的底细摸透。很多人觉得集合就是一个能自动扩容的数组加一个能快速查找的字典这个印象方向是对的但离真正理解还差着十万八千里。我这次想做的事情就是把自己重新捋一遍集合框架的笔记整理成文重点放在ArrayList和HashMap这两员大将身上——一个是Collection系的代表一个是Map系的代表把它们的底层原理、设计取舍和实战陷阱全部过一遍。这篇文章适合刚学完Java基础、准备面试的朋友也适合写了好几年业务代码但没认真看过源码的老开发。1.1 Collection和Map两大阵营的分工逻辑Java集合框架的顶层接口就两个大方向Collection和Map。Collection管的是一组元素比如你有一堆学生对象、一堆订单号Map管的是键值对映射比如用身份证号查个人信息、用商品ID查库存。Collection下面又分了List、Set、Queue三个子接口。List的特点是有序、可重复元素按插入顺序排列可以按下标访问Set的特点是不可重复它内部的逻辑核心是如何判断两个元素相同Queue则是为队列场景设计的先进先出或者带优先级。Map不走Collection这条路它自成一体但面试和工作中最常被拿来和Collection对比——比如HashMap的keySet()返回的是一个Set视图values()返回的是一个Collection视图这俩阵营其实是打通的。从源码上看ArrayList继承自AbstractList实现了List接口HashMap继承自AbstractMap实现了Map接口。但真正干活的是它们内部持有的数据结构。我刚开始看这部分的时候有个误区老想着把所有接口方法背下来。后来才发现最重要的是理解每个类选用了什么数据结构以及为什么选它。1.2 为什么ArrayList和HashMap能成为默认选择业界有个不成文的习惯List默认选ArrayListMap默认选HashMap。这背后的原因值得琢磨。ArrayList的底层是连续内存的数组这意味着它的随机访问是 O(1)按索引拿元素快到飞起。对于绝大多数业务场景——遍历、按序号取值、尾部追加——它都是最优解。LinkedList虽然插入删除理论上更快但那是指在已知节点位置的前提下实际业务里你定位节点本身还得遍历反而更慢。所以除非你要实现一个频繁在头部插入删除的队列否则ArrayList几乎总是更合适。HashMap的底层是数组加链表加红黑树它的设计目标是让 get 和 put 的平均时间复杂度接近 O(1)。这个平均是有条件的后面我会详细讲 hash 冲突、负载因子和树化。总之当你需要一个根据某个键快速找到对应值的容器时HashMap是综合性能最强、最通用的选择。2. ArrayList源码级拆解动态数组的扩张与收缩ArrayList的底层就是一个Object[]数组它的所有操作都是对这个数组的封装。但细节藏在几个关键方法里构造、add、扩容、remove。我建议你打开IDE跟着我下面的分析把ArrayList.java的关键代码翻一遍。2.1 底层数组与默认容量那些事先看构造。ArrayList有三个构造方法无参构造、指定初始容量构造、传入集合构造。// 无参构造底层是一个空数组 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }这里有个容易忽略的细节无参构造创建出来的时候底层数组是空的不是10个容量。真正的默认容量10是在第一次add时才生效的。源码里add会调用ensureCapacityInternal通过calculateCapacity判断如果数组还是那个默认空数组就把容量计算为DEFAULT_CAPACITY也就是10。这个设计叫懒初始化好处是如果你创建一个ArrayList但一直没往里放元素就不会白白分配内存。指定初始容量的构造就直白多了public ArrayList(int initialCapacity) { if (initialCapacity 0) { this.elementData new Object[initialCapacity]; } else if (initialCapacity 0) { this.elementData EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } }注意这里传入0和传入负数是有区别的负数直接抛异常。这在源码里是很常见的防御式编程。2.2 add、remove、扩容三个高频操作的完整链路add的完整流程是这样的调用ensureCapacityInternal(size 1)确保数组够用。如果不够触发grow扩容。把新元素放到elementData[size]然后size。扩容的核心是grow方法private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) { newCapacity minCapacity; } return elementData Arrays.copyOf(elementData, newCapacity); }oldCapacity 1是右移一位相当于除以2。所以新容量是旧容量的1.5倍。为什么是1.5倍而不是2倍因为扩容需要Arrays.copyOf把老数组全部拷贝到新数组这是一个 O(n) 操作。扩容倍数越大扩容次数越少但浪费的内存空间越多1.5倍是在减少拷贝次数和控制内存浪费之间取的平衡。如果你能预估数据量最好在构造时就指定初始容量比如new ArrayList(1000)这样能省掉好几次数组拷贝。remove的逻辑以前踩过坑得单独说。按索引删除的流程是public E remove(int index) { rangeCheck(index); modCount; E oldValue elementData(index); int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; return oldValue; }这里最要命的细节是删除中间元素时后面的元素需要整体向前移动一位。你删除第0个元素和删除最后一个元素的开销完全不一样前者要把后面 n-1 个元素全部搬一次后者只需要把size-1位置置空。所以如果你有大量按条件删除的需求从后往前遍历删除能避免元素搬移性能提升非常明显。2.3 为什么用ArrayList不要随便remove还是倒序remove我想说一个反直觉的结论很多性能问题不是ArrayList的锅是你用它的姿势不对。举一个真实场景一个列表里有 100 万个元素你要删除其中满足某种条件的一半。如果正序遍历每删一个元素后面所有元素都要往前挪时间复杂度是 O(n²)。如果你倒序遍历从最后一个元素往前判断每次都删除末尾附近的元素搬移的元素数量少了很多。更优的做法是用Iterator.remove()它在遍历时通过it.remove()删除当前元素ArrayList内部的Itr类实现了这一点它和modCount的校验逻辑配合能在遍历过程中安全删除而不是等遍历完再删。ListString list new ArrayList(Arrays.asList(a, b, c, b)); // 错误示范for循环 list.remove()会漏删 for (int i 0; i list.size(); i) { if (b.equals(list.get(i))) { list.remove(i); // 删完索引会错位 } } // 正确示范倒序删除 for (int i list.size() - 1; i 0; i--) { if (b.equals(list.get(i))) { list.remove(i); } } // 更推荐Iterator.remove() IteratorString it list.iterator(); while (it.hasNext()) { if (b.equals(it.next())) { it.remove(); } }我自己的习惯是如果只是删除符合条件的场景优先用Iterator.remove()语义最清晰如果还需要在遍历中做其他判断那就倒序。这两个方案都能避免漏删和错位。3. HashMap底层原理从hash散列到红黑树HashMap是集合框架里最复杂的类之一也是面试重灾区。我希望用最清晰的逻辑把它讲透。它的底层结构一句话概括一个数组数组的每个元素是链表头节点或红黑树根节点。这个数组叫table它的大小始终是 2 的整数次幂。为什么下面细说。3.1 hash计算与bucket定位当你调用put(key, value)时第一步是计算 key 的 hash 值第二步是用 hash 值定位到数组的某个下标。static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这里有个非常精妙的设计hashCode()返回的是一个 32 位的 int但table数组的容量一般是 16、32、64 这样的数直接取模的话只有低位参与了数组下标的计算。h 16把高16位右移到低16位再和原 hash 异或这样高位信息也混入了低位降低了冲突概率。这个操作叫扰动函数目的就是让 hash 值在数组长度很小的时候也能均匀分布。定位下标的代码在putVal里if ((p tab[i (n - 1) hash]) null) { tab[i] newNode(hash, key, value, null); }(n - 1) hash等价于hash % n但位运算更快。前提是 n 是 2 的幂次方因为n - 1的二进制全是低位1这样 hash能取到 hash 的低几位等价于取模。这就是为什么HashMap的容量必须是 2 的整数次幂——不是为了玄学是为了用位运算代替取模顺便保证分布均匀。3.2 链表转红黑树的阈值与触发条件同一个下标位置如果出现了多个 key它们的 hash 值换算出的下标相同就叫hash 冲突。冲突的元素以链表形式串联起来。链表太长get 的复杂度会退化成 O(n)所以 JDK 8 引入了红黑树优化。触发条件有两个必须同时满足链表的长度超过TREEIFY_THRESHOLD 8。table数组的容量大于等于MIN_TREEIFY_CAPACITY 64。源码里有一段注释解释为什么阈值是 8TreeNodes的占用空间大约是普通节点的两倍所以只有当链表足够长时树化的收益才值得付出内存代价。根据泊松分布在负载因子 0.75 下链表长度达到 8 的概率已经只有千万分之六所以这个阈值选得很讲究。如果你细心会发现 HashMap 里还有一个UNTREEIFY_THRESHOLD 6。扩容时如果红黑树节点被拆分后数量少于6会退化成链表。8 和 6 中间留了个缓冲防止链表和树在两个阈值之间反复横跳这也是工程上常见的滞回设计。3.3 扩容resize的全过程HashMap的扩容和ArrayList完全不同。ArrayList扩容就是简单地把数组变大、拷贝元素HashMap扩容后每个元素的下标位置可能会改变因为数组长度变了(n - 1) hash的结果也会变。扩容发生在putVal的最后判断条件是if (size threshold) { resize(); }threshold在初始化时是capacity * loadFactor默认负载因子是 0.75。举个例子默认容量 16threshold 就是 12。当你插入第 13 个元素时触发扩容。为什么负载因子是 0.75这是空间和时间的折中负载因子太小空间浪费严重太大冲突变多链表变长。0.75 是官方经过大量测试得出来的经验值日常使用不要轻易改。扩容时新的容量是旧容量的两倍。JDK 8 有个优化值得表扬旧链表上的节点在扩容后要么停留在原下标i要么转移到i oldCap。因为判断依据是(e.hash oldCap) 0如果为 0 就留在原位置否则移到i oldCap。这个技巧省去了重新计算 hash 的时间你看源码里resize有专门的两段链表逻辑处理这个事。我在项目里遇到过用 HashMap 存储大量数据导致 GC 压力增大的情况。排查下来发现是频繁扩容每次扩容都要重新分配数组并搬运节点触发多次 young gc。解决方式很简单预估容量构造时传入// 预估数据量是10000负载因子0.75那么初始容量要保证 threshold 够用 MapString, Object map new HashMap(10000 / 0.75 1);记住一个规矩initialCapacity 预估数据量 / 0.75 1别直接传预估量否则还没等你放完数据就开始扩容了。4. 实际开发中的选型对比与避坑清单看完了底层原理我再来梳理一下实际开发中怎么选型、有哪些最常见的坑。4.1 ArrayList vs LinkedList vs Vector很多初学者会在这三个类之间纠结。我给一个直接的结论ArrayList底层数组随机访问快尾部插入快中间插入删除慢。几乎总是首选。LinkedList底层双向链表头部插入删除快但按索引访问是 O(n)。只有在明确需要频繁队头队尾操作的场景才选它。而且LinkedList每个节点还要额外存储前后指针内存开销比ArrayList大不少。Vector历史遗留类所有方法都用 synchronized 修饰线程安全但性能差。现在完全可以用Collections.synchronizedList(new ArrayList())替代或者干脆用CopyOnWriteArrayList。我见过有人用LinkedList存了几万条数据然后疯狂get(i)遍历那个性能真的是灾难级别。反过来也有业务场景是永远只从头取、从头删这种才适合LinkedList。4.2 HashMap vs Hashtable vs ConcurrentHashMapHashtable和Vector一样是历史遗留所有方法加锁现在没人该用它。HashMap不是线程安全的多线程写入会导致数据错乱甚至 JDK 7 时代在扩容时会形成环形链表导致死循环——这个问题在 JDK 8 已经通过尾插法修复了但多线程下丢数据、覆盖值依然存在。正确的并发选择是ConcurrentHashMap。它采用 CAS synchronized 锁住单个桶或树根锁粒度比Hashtable细得多。我在高并发的缓存场景里用过它性能比Hashtable有数量级的提升。注意ConcurrentHashMap的 key 和 value 都不允许为 null而HashMap允许一个 null key 和任意多个 null value。源码注释里解释了原因——因为并发环境下无法区分值为null和不存在但具体原因你可以理解为如果允许 nullget返回 null 时你无法判断是 key 不存在还是 value 就是 null。4.3 真实项目中出现过的集合坑分享几个我真实踩过、或者帮同事排查过的坑。第一个坑HashMap 作为方法入参被调用方修改了结构。Java 是引用传递你把 map 传给另一个方法它在里面 put/remove外面的 map 也变了。如果不想这样要传副本MapString, Object copy new HashMap(original);第二个坑自定义对象作为 key没有重写 hashCode 和 equals。如果不重写HashMap 用Object的默认实现两个内容一样的对象会被当成两个不同的 key导致 put 进去的东西 get 不到。正确做法是重写这两个方法而且要注意重写的规范equals 相等的两个对象hashCode 必须相等。我用 Lombok 的Data或者手动写都行但千万别只重写 equals 不重写 hashCode那会直接破坏 HashMap 的查找逻辑。第三个坑遍历时修改结构抛 ConcurrentModificationException。这个和 ArrayList 的快速失败机制一样源于一个modCount计数器。任何结构性修改add/remove都会让 modCount 增加而迭代器在next()时检查 modCount 是否和预期一致不一致就抛异常。解决办法是用迭代器的remove方法或者遍历的时候先收集要删的 key遍历完再统一删。5. 面试高频问题与源码级追问最后这部分我把面试里反复出现、和这两个类相关的问题集中整理一遍每个问题我都给一个能过面试官这关的回答思路。这不是背八股而是检验你是不是真的理解了这个集合的设计初衷。5.1 为什么HashMap的容量是2的幂次方这个问题的标准答法分两层。第一层为了用位运算(n - 1) hash代替取模hash % n位运算效率更高。第二层当 n 是 2 的幂次方时n - 1的二进制是连续的 1与 hash 做与运算能完整保留 hash 的低位信息分布更均匀如果不是 2 的幂次方n - 1的二进制会有 0某些下标根本不可能出现导致数组空间浪费并且冲突加剧。追问还可能延伸到那为什么HashMap初始化时如果你传入一个不是 2 的幂次方的容量比如 17会发生什么答案是tableSizeFor会把容量调整为大于等于你传入值的最小 2 的幂次方17 会变成 32。这个方法在源码里是一连串的|和操作非常经典建议自己打开源码看一眼。5.2 modCount与fail-fast机制ArrayList、HashMap的迭代器都是快速失败的。modCount记录结构性修改次数迭代器构造时记录expectedModCount modCount每次迭代检查两者是否一致。如果不一致说明在迭代过程中有其他线程或同一线程的其他代码修改了集合结构此时继续迭代可能产生不可预知的结果所以直接抛ConcurrentModificationException。这里有个非常隐蔽的点set方法不会触发 modCount 增加因为 set 是替换元素不改变结构。所以迭代过程中允许set但不允许add和remove。面试官如果追问为什么修改元素不报错你能答出这点说明你确实是读过源码的。5.3 自定义对象作为key时要注意什么这个我在 4.3 里提过但面试值得展开。第一必须同时重写hashCode和equals且满足两个对象的 equals 相等时 hashCode 必须相等。第二key 对象不该是可变的。假设你用一个Person对象做 keyhashCode基于name字段计算放入 map 之后你把person.name改了hashCode 就变了但它在 map 里的 bucket 位置没变下次 get 时按新 hashCode 定位到别的 bucket就找不到了。这会导致内存泄漏——HashMap里那个旧 entry 永远无法通过这个 key 访问到但它占着空间。所以不可变类如String、Integer是天然的好 key。第三HashMap和ConcurrentHashMap对 null key 的态度不同这也是高频追问点。HashMap允许null作为 keyhash 方法里(key null) ? 0null 的 hash 是 0它被放在数组第 0 个位置。Hashtable和ConcurrentHashMap不允许 null key因为它们在并发场景下无法区分取到的 null 是 value 还是 key 不存在处理起来有歧义。我最后再分享一个个人体会源码读一遍记不住是正常的但你要学会带着问题去读。比如先想清楚HashMap 是怎么做到 O(1) 查找的然后去看它的 get 方法想清楚为什么扩容后性能会抖动再去看 resize 的逻辑。用问题驱动阅读比从头到尾翻一遍有效得多。集合这块的知识面试和工作是高度重叠的——你在生产环境里踩过的每一个性能坑、每一个并发错追根溯源都能回到这些底层设计。所以耐心把 ArrayList 和 HashMap 啃下来真的是一本万利的事情。
阅读完成 · 觉得有帮助？
