第二章JAVA集合框架Java集合框架是面试绝对重点尤其是 HashMap、ConcurrentHashMap 的源码级理解。2.1 ArrayList vs LinkedList2.1.1 ArrayList 扩容机制ArrayList 的扩容是面试高频考点// ArrayList扩容源码JDK 8// 默认初始容量10JDK7是懒初始化new ArrayList()时是空数组首次add才扩容到10privatestaticfinalintDEFAULT_CAPACITY10;privatestaticfinalObject[]EMPTY_ELEMENTDATA{};privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA{};publicbooleanadd(Ee){ensureCapacityInternal(size1);elementData[size]e;returntrue;}privatevoidgrow(intminCapacity){intoldCapacityelementData.length;// 扩容1.5倍oldCapacity oldCapacity 1intnewCapacityoldCapacity(oldCapacity1);if(newCapacity-minCapacity0)newCapacityminCapacity;if(newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity);// Arrays.copyOf 底层调用 System.arraycopynative方法深拷贝数组elementDataArrays.copyOf(elementData,newCapacity);}// 示例容量变化// add第1个元素: 0 → 10// add第11个元素: 10 → 15 (1010/2)// add第16个元素: 15 → 22 (1515/222)// 扩容开销每次扩容需要将旧数组的元素复制到新数组时间复杂度O(n)2.2 HashMap超级重点⚠️ HashMap 是中厂面试最高频的考点没有之一需要达到源码级掌握。2.2.1 JDK7 vs JDK8 数据结构差异JDK7数组 链表头插法JDK8数组 链表 红黑树尾插法当链表长度 ≥ 8 且数组长度 ≥ 64链表转为红黑树红黑树退化为链表的条件当红黑树节点数 ≤ 6 时退化为链表中间差 7 是为了避免频繁转换的缓冲2.2.2 HashMap put 流程必须背熟finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;// 步骤1数组为空 → 初始化resizeif((tabtable)null||(ntab.length)0)n(tabresize()).length;// 步骤2计算下标该位置为空 → 直接放入// 下标计算i (n-1) hashif((ptab[i(n-1)hash])null)tab[i]newNode(hash,key,value,null);else{NodeK,Ve;Kk;// 步骤3该位置有节点且key相同 → 覆盖旧值if(p.hashhash((kp.key)key||(key!nullkey.equals(k))))ep;// 步骤4该位置是红黑树节点 → 插入树中elseif(pinstanceofTreeNode)e((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);// 步骤5该位置是链表节点 → 遍历链表else{for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 链表长度 ≥ 8TREEIFY_THRESHOLD→ 转为红黑树if(binCountTREEIFY_THRESHOLD-1)treeifyBin(tab,hash);break;}// 找到相同key → 跳出if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))break;pe;}}// 步骤6e ! null 说明key已存在覆盖旧值if(e!null){VoldValuee.value;if(!onlyIfAbsent||oldValuenull)e.valuevalue;afterNodeAccess(e);// LinkedHashMap用returnoldValue;}}modCount;// 步骤7size threshold → 扩容if(sizethreshold)resize();afterNodeInsertion(evict);returnnull;}2.2.3 HashMap 扩容机制finalNodeK,V[]resize(){// ... 省略部分代码// 新容量 旧容量 * 2// 新阈值 旧阈值 * 2// JDK8 的优化rehash不需要重新计算hash// 扩容后节点要么在原位置 j要么在原位置 j oldCap// 原理下标 hash (newCap-1)newCap-1 比 oldCap-1 多了一位高位bit// 如果 hash 中该高位bit0 → 位置不变// 如果 hash 中该高位bit1 → 位置变为 j oldCapdo{nexte.next;// (e.hash oldCap) 0 → 位置不变if((e.hasholdCap)0){if(loTailnull)loHeade;elseloTail.nexte;loTaile;}// (e.hash oldCap) ! 0 → 位置变为 j oldCapelse{if(hiTailnull)hiHeade;elsehiTail.nexte;hiTaile;}}while((enext)!null);}2.2.4 高频面试问题汇总Q1: 为什么负载因子是 0.75空间利用率和时间效率的折中。负载因子越大空间利用率越高但冲突概率增加负载因子越小冲突概率越低但空间浪费增多。根据泊松分布0.75时链表长度达到8的概率约为0.00000006是统计学上的平衡点。Q2: 为什么容量是 2 的幂●1. 方便取模运算hash % n 等价于 hash (n-1)位运算效率远高于取模●2. 扩容时数据迁移更高效不需要重新计算 hash只需判断 (e.hash oldCap)●3. 使元素分布更均匀2的幂-1 的二进制全是1与 hash 做 运算能均匀分布Q3: 为什么红黑树阈值是 8根据泊松分布统计在负载因子 0.75 时链表长度达到 8 的概率不到千万分之一。但一旦出现如被恶意攻击构造大量 hash 冲突链表查询退化到 O(n)转红黑树后可保证 O(log n)。这也是为什么 Redis、Nginx 等也选择 8 作为转树阈值。Q4: JDK7 扩容为什么可能导致死循环CPU 100%JDK7 采用头插法在多线程同时扩容时可能导致链表形成环形造成 get() 时死循环和 CPU 100%。JDK8 改为尾插法解决了死循环问题但 HashMap 仍然不是线程安全的可能丢数据、size 不准确多线程场景应使用 ConcurrentHashMap。Q5: HashMap 的 hash 函数为什么这样设计// hashCode 的高16位与低16位做异或增加低位的随机性staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}// 原因计算下标时是 (n-1) hash当 n 较小时如16n-11500001111// 只使用 hash 的低4位高位无法参与运算。通过高16位异或低16位// 将高位的影响扩散到低位使散列更均匀。2.3 ConcurrentHashMap⚠️ ConcurrentHashMap 是并发编程面试的核心考点必须清楚 JDK7 分段锁和 JDK8 CASsynchronized 的区别。2.3.1 JDK7 分段锁机制JDK7 的 ConcurrentHashMap 采用分段锁Segment机制默认 16 个 Segment每个 Segment 内部是一个独立的 HashMap。不同 Segment 可以并发操作并发度为 16。// JDK7 结构示意// ConcurrentHashMap// ├── Segment[0] (继承 ReentrantLock)// │ ├── HashEntry → HashEntry → ... (链表)// │ └── ...// ├── Segment[1]// │ └── ...// └── Segment[15]// └── ...// put 流程publicVput(Kkey,Vvalue){inthashhash(key);intsegmentIndex(hashsegmentShift)segmentMask;// 定位SegmentSegmentK,VsegmentensureSegment(segmentIndex);returnsegment.put(key,hash,value,false);}// Segment.put() 内部先 lock()然后执行类似于 HashMap 的 put 流程2.3.2 JDK8 CAS synchronized 机制JDK8 完全重构了 ConcurrentHashMap放弃了分段锁改用更细粒度的锁策略●数组为空时CAS 初始化数组●桶位置为空时CAS 插入节点无锁●桶位置不为空时synchronized 锁住该桶的头节点链表头/树根●扩容时多线程协作扩容每个线程分配一段区间迁移数据// JDK8 put 核心逻辑finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){// 1. 计算hashspread() 使hash为正数(负数有特殊含义)inthashspread(key.hashCode());// 2. 死循环 CASfor(NodeK,V[]tabtable;;){// 3. 数组为空 → CAS初始化数组只有一个线程成功if(tabnull){// CAS操作 initTable()}// 4. 桶位置为空 → CAS放入节点无锁elseif((ftabAt(tab,i(n-1)hash))null){if(casTabAt(tab,i,null,newNodeK,V(hash,key,value)))break;}// 5. Moved节点 → 帮助扩容elseif((fhf.hash)MOVED){tabhelpTransfer(tab,f);}// 6. 桶位置有节点 → synchronized锁住头节点else{synchronized(f){// 如果节点是链表 → 遍历链表// 如果节点是树 → 遍历树// size1}}}}2.3.3 ConcurrentHashMap 的 sizeCtl 含义●sizeCtl 0默认值表示数组未初始化●sizeCtl -1表示正在初始化数组●sizeCtl 0 且数组为null初始化容量●sizeCtl 0 且数组已初始化下次扩容的阈值●sizeCtl -1-(1 扩容线程数)如 -3 表示有 2 个线程在扩容2.4 HashSet / TreeSet / LinkedHashMap2.4.1 HashSetHashSet 底层基于 HashMap 实现元素作为 HashMap 的 keyvalue 是一个固定的虚拟对象PRESENT new Object()。// HashSet 本质publicclassHashSetE{privatetransientHashMapE,Objectmap;privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;// 利用HashMap的key不重复特性}publicbooleancontains(Objecto){returnmap.containsKey(o);}publicbooleanremove(Objecto){returnmap.remove(o)PRESENT;}}2.4.2 TreeSetTreeSet 底层基于 TreeMap红黑树元素有序自然排序或 Comparator 排序查询时间复杂度 O(log n)。2.4.3 LinkedHashMapLinkedHashMap 继承 HashMap在其基础上添加了双向链表来维护元素的插入顺序或访问顺序。这是实现 LRU 缓存的基础。// LinkedHashMap 的核心自定义的 Entry 节点staticclassEntryK,VextendsHashMap.NodeK,V{EntryK,Vbefore,after;// 双向链表的前后指针Entry(inthash,Kkey,Vvalue,NodeK,Vnext){super(hash,key,value,next);}}// accessOrder true按访问顺序排序LRU缓存的核心配置// accessOrder false按插入顺序排序默认LinkedHashMapString,IntegermapnewLinkedHashMap(16,0.75f,true);