开题先说实话：ArrayList和HashMap这两个类，我在给团队做代码评审时几乎每次都会见到，自己写业务代码时也几乎每天都在用。但你要是随便拉住一个写了三五年Java的人，问他“HashMap put一个键值对到底经历了哪几步”“ArrayList扩容为什么要乘1.5而不是2”，大概率能卡住一半。之所以想“从头到尾”再捋一遍，是因为这两个类就是Java集合框架的两根柱子，理解了它们，再看LinkedList、HashSet、LinkedHashMap、ConcurrentHashMap都会顺很多。这篇文章就围绕这两个高频类展开，把底层数据结构、扩容逻辑、操作复杂度、常见坑一次性讲透，既不灌水，也不堆面试八股，适合正在学集合框架的初中级开发者，也适合准备面试或者想系统过一遍源码的同行。
顺便说一句，“集合”这个词在不同的上下文里含义差很远，数学里的集合、数据库里的集合、Java里的Collection完全是三码事，我这次只讨论Java集合框架，别的领域先放一边。
1. 先看全貌：集合框架到底在解决什么问题
1.1 数组不够用，集合才登场
回顾一下数组的痛点：一个int[] arr = new int[10]，长度定了就不能改，插一个元素到中间，你得手工把后面的元素全部后移，删一个元素同理，所有代码都得自己写。更难受的是，数组只能按索引访问，根本谈不上什么“按内容查找”“去重”“排序”这些业务上天天要用的能力。Java集合框架本质上就是把数据结构这门课里讲过的顺序表、链表、二叉树、散列表，全部封装成了开箱即用的类，让你不用每次从零造轮子。
ArrayList本质上就是数据结构里的“顺序表”，底层用数组实现动态扩容；HashMap本质上是一张“散列表”，用哈希函数把键映射到数组桶里。两者正好代表了集合框架里两条不同的设计路线：一条讲究有序存储和索引访问，一条讲究键值映射和常数级查找。这也是为什么我在讲集合时总把这两个类放在一起说，因为它们一对比，你对整个框架的设计哲学就有感觉了。
1.2 Collection和Map两条主线
Java集合框架顶层分两条线，这个必须先分清：
- Collection线：强调“一组元素”。下面又分List（有序、可重复）、Set（不可重复）、Queue（队列语义）。ArrayList就是List的典型实现，HashSet底层其实包了一个HashMap，所以理解HashMap后，HashSet几乎不用学。
- Map线：强调“键值映射”。每一个元素都是key-value对，key不能重复。HashMap是Map的典型实现，TreeMap、LinkedHashMap、ConcurrentHashMap都是它的变体。
两条线的接口设计也不一样。Collection有add(E e)、remove(Object o)、iterator()这一套方法；Map则是put(K key, V value)、get(Object key)、containsKey(Object key)这一套。很多新手容易犯的错，是把Map当成List去遍历，或者试图通过for-each直接遍历Map，实际上Map要遍历的是entrySet()、keySet()或者values()。这个设计差异从根上讲，就是因为“装一堆元素”和“装一堆键值对”的使用方式完全不同，所以接口才分道扬镳。
从这一层往下，接口下面还有AbstractList、AbstractMap这些抽象类，它们把通用逻辑抽出来，减少各实现类的重复代码。比如AbstractList已经实现了iterator()和removeIf()这类公共方法，ArrayList只需要专注数组操作本身。这就是典型的“接口定义规范，抽象类承担默认实现，具体类只保留个性”的分层设计，读源码时顺着这条线走，你会发现结构比想象的清晰很多。
2. ArrayList：最常用的动态数组，你真的了解它吗
2.1 底层就一个数组，但初始化细节不少
ArrayList的底层就是一个Object[] elementData，所有方法都在操作这个数组。但这个数组的初始化方式在不同JDK版本里是有讲究的。JDK 8及以后，通过new ArrayList()创建时，底层指向的是一个共享的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也就是说，你没有真正分配数组容量。直到第一次add时，才走ensureCapacityInternal去扩容成默认容量10。
这个细节很多人不知道，但它在特定场景下是有意义的：如果你创建了一堆ArrayList但很多都没往里放数据，那些对象不会白白占用10个元素的堆内存。JDK 7及以前是直接初始化成10的，后来才改成懒加载，这个改动就是为了省内存。知道这个，面试时被问“new ArrayList()底层数组是几”就不容易答错——答案是空数组，第一次add后才变成10。
如果你一开始就知道要存1000个元素，建议直接new ArrayList<>(1000)，把初始容量传进去。这样能省去扩容搬移的开销，后面我会算这笔账。
2.2 扩容机制：1.5倍到底是怎么算出来的
看源码，扩容核心在grow(int minCapacity)方法，逻辑可以简化成下面的代码：
int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 即1.5倍 if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } elementData = Arrays.copyOf(elementData, newCapacity);oldCapacity >> 1就是把容量右移一位，相当于除以2，所以新容量等于旧容量 + 旧容量/2，也就是1.5倍。为什么选1.5而不是2倍呢？如果扩容倍数太小，比如1.1倍，那扩容很频繁，每次都要把旧数组元素复制到新数组，搬移成本太高；如果直接翻倍，空间又容易浪费，比如你只需要100个容量，它给你扩到256，多出来的内存就白占了。1.5倍是时间和空间上的一个平衡点，这也是JDK开发者多年优化下来的经验值。
另外有一处细节：当容量已经接近Integer.MAX_VALUE时，ArrayList会走hugeCapacity，如果minCapacity超过MAX_ARRAY_SIZE（约21亿），会直接抛OutOfMemoryError。正常情况下没人能存这么多元素，但如果你在做海量数据批量插入，需要知道这个极限值的存在。
还要提醒一点：扩容是“扩容到现在所需的最小容量”还是“直接扩1.5倍”？实际是按两者的较大值来。比如原来容量10，插入后需要11，1.5倍是15，所以扩到15。但如果你一次addAll插入大量元素，假设需要容量200，1.5倍只有15，那就会直接扩到200，所以增长曲线是“按需取最大值”，极端场景下容量会跳着走。
2.3 增删查改的时间和性能账
ArrayList各操作的时间复杂度，我在讲课时会让新人整理成一个速查表：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
get(index) | O(1) | 数组按下标直接访问，这是ArrayList最大的优势 |
add(元素) | 均摊O(1) | 尾部追加，偶尔触发扩容搬移，所以是“均摊” |
add(index, 元素) | O(n) | 需要把index及之后的元素全部后移 |
remove(index) | O(n) | 需要把index之后的元素全部前移 |
remove(元素) | O(n) | 先线性查找，再前移 |
contains(元素) | O(n) | 线性扫描 |
这张表背后是一笔很实在的账。业务代码里最常见的一个坑，就是用ArrayList做高频头部插入或删除，比如维护一个“最近浏览”列表，每次塞到第0位。add(0, x)每次都触发全数组移动，数据量一旦过万，延迟会肉眼可见地上升。正确做法是换LinkedList，或者干脆用ArrayDeque，再或者反转存储顺序，只在尾部操作。
另外，如果确实一次要插入大量数据，最好先ensureCapacity(n)把容量一次性扩到位，否则ArrayList会在一顿批量插入中反复扩容。假设你要插入100万条数据，初始容量是10，不预先扩容，中间可能扩容十几二十次，每次都是一次Arrays.copyOf全量搬移，总耗时要比一次扩到位高好几倍。这个优化成本极低，收益却非常明显。
2.4 使用ArrayList最容易踩的三个坑
第一个坑：remove(int index)和remove(Object o)混用。ArrayList是重载了两个remove方法的，但你传一个整数时，会走remove(int)按索引删，而不是删除那个“值为几”的对象。比如list.remove(3)，你以为删掉“3”这个数字，结果实际删掉的是第4个元素。要删值为3的元素，得用list.remove(Integer.valueOf(3))。这个坑几乎每个团队都有人踩过，而且极易在代码评审里被漏掉。
第二个坑：subList返回的不是“新的列表”，而是原列表的视图。也就是说，你对subList做修改，会直接反映到原List上。而且只要subList存在期间你修改了原List的结构，再操作subList就会抛ConcurrentModificationException。很多人以为subList和Arrays.copyOf一样是复制一份，这是误解。
第三个坑：遍历时删除元素。下面的代码看着没问题，但会漏删：
for (int i = 0; i < list.size(); i++) { if (list.get(i).equals(target)) { list.remove(i); } }因为每次remove后，后面的元素会往前挪，索引i直接跳过了原来的i+1位置。解决方法是用Iterator.remove()，或者从后往前遍历删除，再或者用Java 8的removeIf。这一点，我可以说，几乎每隔几个月就能在某个PR里见到一次。
3. HashMap：从put到get，彻底理解“散列表”
3.1 put一个键值对，底层发生了什么
HashMap是Java集合里面试问得最深的一个类，因为它的底层结构涉及哈希、位运算、链表、树化、扩容，一环扣一环。先看整体结构：JDK 1.8之后的HashMap，数据结构是“数组 + 链表 + 红黑树”。数组叫table，每个数组位置称为一个“桶”（bucket），桶里可能只有一个Node，也可能是一条链表，也可能是一棵红黑树。
一个标准的put(key, value)流程是这样的：
- 对key做
hash()计算。如果key为null，hash值为0；否则取h = key.hashCode()，再执行h ^ (h >>> 16)，这是JDK 8引入的“扰动函数”，目的是让高位也参与低位运算，降低哈希碰撞概率。 - 通过
(n - 1) & hash计算桶下标，n是table当前长度。 - 如果该桶为空，直接放入新Node。
- 如果该桶不为空，检查首节点是否命中了同一个key（用
hash相等且equals为true判断），是则覆盖value。 - 没命中，就继续遍历链表/红黑树查找。链表里没找到就追加到链表尾部；如果命中就覆盖。
- 追加完后，如果链表长度达到树化阈值8，并且table长度达到64，就把这条链表转换成红黑树。
- 最后，如果整个map的元素数量超过
threshold（容量x负载因子），触发扩容。
对应的伪代码可以看下面这个简化版：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; int n, i; if ((tab = table) == null || (n = tab.length) == 0) { n = (tab = resize()).length; } if ((p = tab[i = (n - 1) & hash]) == null) { tab[i] = new Node(hash, key, value, null); } else { // 链表或红黑树节点的插入逻辑 // 找到则替换，没找到则新增 } ++modCount; if (++size > threshold) { resize(); } }很多人背了流程但是不理解，我换个说法帮助记：HashMap就是“先用散列定位到桶，再用equals解决冲突”。散列定位快，但散列冲突无法完全避免，一旦冲突，就退化到在桶内部做线性或树形查找。性能好不好，很大程度上取决于key的散列分布均不均匀。
3.2 为什么容量必须是2的幂
HashMap的初始容量默认是16，并且要求容量必须是2的幂。就算你构造时传进去一个不是2的幂的数，比如new HashMap(10)，它也会在内部通过tableSizeFor给你向上取整到最近的2的幂——这里就是16。所以new HashMap(10)和new HashMap(16)实际效果一样。
为什么一定得是2的幂？因为取模运算可以用位运算代替。正常情况下，要算出hash % n，直接取模，但取模的效率不如位运算。当n是2的幂时，hash % n等价于(n - 1) & hash，这一点在一次次put里被高频调用，能省一点是一点。比如n=16，那么n-1=15的二进制是1111，hash & 1111直接就保留了hash的低4位，结果范围正好是0到15，完美落在数组下标范围内。
还有一个更深的原因：扩容更简单。HashMap扩容是翻倍，比如16变成32，这时候n-1从1111变成11111，多了一个“高位1”。元素在新数组中的位置，取决于原hash对应的那一位是0还是1。如果是0，位置不变；如果是1，新位置就是“原位置+16”。这一步不需要重新计算所有元素的hash和下标，只需要看新增的那一位。所以在JDK 1.8的源码里，你能看到(e.hash & oldCap) == 0这个判断，就是干这个用的。位运算让“扩容重散列”的成本从O(n)降到了接近O(1)的判定级别的操作，这是哈希表工程优化的精髓。
如果读者是初学者，这里可以做个生活化类比：16个抽屉，每个抽屉下面有一个编号，元素进来先根据hash低4位选抽屉；抽屉数量翻倍到32，相当于编号多了一位，旧抽屉里的东西要么留在原编号，要么挪到“原编号+16”的新抽屉，规则简单清晰。
3.3 链表和红黑树：8/6/64这几个数字怎么来的
HashMap在JDK 1.8引入红黑树，是为了解决极端情况下“大量key落到同一个桶，链表退化成线性查找”的问题。链表查找是O(n)，红黑树是O(log n)，当链表长度到8时查询性能就会有明显差距。但树化也不是免费的，红黑树的节点结构更复杂，占用内存更多，所以JDK设计了一套触发规则：
- 链表长度达到8时，尝试树化；
- 但同时要求table长度不小于64，否则不树化，只做扩容；
- 链表的长度降到6时，红黑树会退化成链表。
为什么是8？源码注释里给了一个统计学依据：在随机哈希函数下，同一个桶内的节点数遵循泊松分布，链表长度达到8的概率大约是千万分之六，已经是非常小的概率了。设置8，是为了让“正常情况几乎不会树化”，只有哈希函数被恶意构造、或者大量key正好同hash的极端场景才触发。而6和8之间留了1个数的缓冲，是为了避免“长度在7/8附近反复横跳”，导致链表和红黑树频繁转换，白白消耗性能。这就是工程上的“滞回”思想，跟温控器避免频繁开关机是一个道理。
64这个数字也很好理解：如果table长度小于64，说明整个map还没多大，与其树化，不如直接扩容——扩容后所有元素都重新散列，大概率冲突会明显改善。所以HashMap优先用扩容来解决冲突，而不是一上来就上红黑树。
3.4 负载因子0.75和扩容的触发时机
HashMap默认负载因子是0.75，这个值代表了时间和空间的折中。负载因子越大，比如0.9或1.0，说明能装更多元素再扩容，空间利用率高，但哈希冲突概率增大，查询效率下降；负载因子越小，比如0.5，冲突少、性能更好，但更早扩容、浪费更多空间。0.75是JDK在大量测试之下的平衡点。
扩容的触发条件是size > capacity * loadFactor，这个乘积就是threshold。比如默认容量16，负载因子0.75，那么threshold是12。也就是说，HashMap在放入第13个键值对时就会扩容到32，然后阈值变成24。以此类推。
扩容时，旧数组的所有元素要被重新分配到新数组。前面已经说过，新位置要么在原位置，要么在原位置加oldCap。执行时，先把链表拆成低位链表和高位链表两条，分别放入newTab[j]和newTab[j + oldCap]，这样即使链表很长，也没必要按个重哈希。这个细节也解释了为什么HashMap扩容效率并不像很多人想象的那样“全员重新散列”，大部分时候它就是一次数组拷贝加链表拆分。
3.5 自定义对象作为key时必须知道的规则
用String和Integer作为key，几乎不会有问题，因为它们已经重写了hashCode()和equals()，并且是不可变的。但一旦用自定义对象当key，下面这条规则就必须刻进脑子里：重写equals()一定要重写hashCode()，而且两个对象equals相等时，hashCode必须相等；反过来不要求相等，但hashCode相等而equals不相等，会引发哈希冲突，也就是多个对象落到同一个桶里，影响性能但不会出错。
更隐蔽的坑是：用可变对象做key，并且在放进HashMap之后修改了它的字段。比如放进去时某个Person对象的hashCode是100，HashMap已经把它放到第100号桶，随后你又把这个对象的名字改了，导致它的hashCode变成200，下次get的时候，HashMap依据新hash算出它在第200号桶，自然怎么都找不到。这就是为什么工程上强烈建议key用不可变对象，比如String、Integer，或者你自己做一个内部不可变的类。我见过不止一次线上bug，就是有人用可变对象做key，埋雷埋了大半年才炸。
4. 面试和工作中高频遇到的问题总结
4.1 fail-fast机制与ConcurrentModificationException
ArrayList和HashMap都不是线程安全的，但任何线程在迭代过程中，如果发现集合被其他线程修改了结构，会快速抛ConcurrentModificationException，这就是fail-fast机制。源码里，AbstractList和HashMap都有一个modCount字段，每次结构性修改（add、remove、clear等）都会让它加一。迭代器创建时记下当前modCount，每次调用next()时检查是否一致，不一致就立刻抛异常。
有人问：“既然是为了检测并发修改，那我单线程下遍历时自己修改结构，会不会抛异常？”答案是会。比如：
for (String s : list) { if (s.equals("a")) { list.remove(s); } }这段代码在遍历过程中通过list本身去remove，modCount变了，迭代器很快就校验不过，直接抛ConcurrentModificationException。新版JDK里，这种错误通常会首先表现为“遍历到一半的某个元素诡异消失”，然后才是异常——因为某些操作可能恰好躲过了检查。所以正确的写法是用Iterator.remove()，它会把迭代器自身的expectedModCount同步更新，不会触发校验失败。
4.2 ArrayList和HashMap线程不安全的具体表现
ArrayList在多线程下同时add，可能出现一种严重问题：两个线程同时判断“容量够用”，同时在elementData[size] = element处写入，其中一个写的位置可能覆盖另一个，或者数组越界。这不是理论推演，我在压测环境里确实复现过。解决办法，单线程场景不用管；多线程读多写少用CopyOnWriteArrayList；普通互斥场景用Collections.synchronizedList(list)。
HashMap的多线程问题更经典。JDK 1.7时代，扩容时使用头插法，并发扩容可能形成环形链表，一旦形成，get一个不存在的key就可能无限循环，CPU直接打满。JDK 1.8改成尾插法，环形链问题没根治但不再因为顺序翻转而产生；不过并发put仍然可能丢失数据，因为两个线程同时命中同一个空桶，会各自创建一个Node放到同一个位置，后写的覆盖先写的，数据就丢了。所以在并发热点路径上，永远不要裸用HashMap，直接上ConcurrentHashMap，分桶加锁或者CAS，把并发的复杂度交给JDK处理。
4.3 并发热点路径的选型建议
说到选型，给一张我平时在团队里会贴出来的速查表：
| 场景 | 推荐类 | 理由 |
|---|---|---|
| 读多写少、遍历频繁 | CopyOnWriteArrayList | 读不加锁，写时复制副本，适合缓存、监听器列表 |
| 多线程写多 | ConcurrentHashMap | 分段桶粒度加锁，并发度远高于Hashtable |
| 需要线程安全的普通List | Collections.synchronizedList | 简单粗暴，但锁粒度过粗，并发低 |
| 只需要线程安全Map且不追求并发度 | Hashtable或Collections.synchronizedMap | 简单，但整表锁，不适合高并发 |
注意，CopyOnWriteArrayList写成本很高，因为每次写都复制整个底层数组，所以它只适合“读远超写”的场景。如果写也很频繁，别用它。ConcurrentHashMap在JDK 1.8后，锁的粒度是单个桶或链表头，不再是分段锁，但大多数业务场景直接用就对了，别自己再包一层Collections.synchronizedMap，那是把高并发实现退化成了整表锁。
4.4 容量设置的经验值和延伸操作
最后一个非常实际的问题，也是我评审代码常说的：别让HashMap在业务高峰反复扩容。一次扩容要重散列所有已有元素，如果你知道大概会存100万条数据，不设初始容量，从16一路扩到100多万，要扩容十几次。提前设好容量，这个开销直接省掉。
HashMap初始容量怎么给合适？直接的目标容量除以负载因子，再向上凑整到2的幂。比如你预计存100万条：
int expectedSize = 1_000_000; Map<String, Object> map = new HashMap<>((int) (expectedSize / 0.75f) + 1);这个+1是为了避免刚好卡在扩容边界上。其实JDK在扩容时也会对空表判断是否做一次最小化分配，但提前设好总归更稳。
延伸一个很实用的扩展是LinkedHashMap。它继承了HashMap，内部维护了一条双向链表记录插入顺序。只要复写removeEldestEntry，就能实现一个最简单的LRU缓存：
class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxSize; LRUCache(int maxSize) { super(maxSize, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }这段代码不复杂，但它能串起HashMap的哈希桶、LinkedHashMap的双链表、负载因子、capacity这些概念，比对着源码硬啃轻松得多。我每次带新人，都会让他们动手写一个这样的LRU，比看十篇分析文章都管用。
最后聊一点我自己的感受。很多人觉得看源码很难，但真正难的不是代码，而是没有带着“为什么这么设计”的问题去读。ArrayList和HashMap是很好的入门样本：一个结构简单、扩容逻辑清晰，一个涉及散列、冲突、树化、扩容四个设计点。把它们读透，再回头看LinkedList、TreeMap、ConcurrentHashMap，你会发现很多相似的模式在重复出现。工程开发里，真正决定代码性能的往往就是集合那几行调用，这功夫值得花。
