北海市网站建设_网站建设公司_在线商城_seo优化

1. ArrayList 自动扩容机制

1.1 核心扩容原理

ArrayList 底层使用 Object[] 数组存储元素，当数组容量不足时自动扩容。

1.2 关键参数

• 默认初始容量：10

• 扩容因子：1.5倍（旧容量 + 旧容量右移1位）

• 最大容量：Integer.MAX_VALUE - 8（部分VM保留头部信息）

1.3 源码解析

// ArrayList 扩容核心方法 private void grow(int minCapacity) { int oldCapacity = elementData.length; // 核心扩容算法：新容量 = 旧容量 * 1.5 int newCapacity = oldCapacity + (oldCapacity >> 1); // 特殊情况处理 if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } // 数组复制：时间复杂度 O(n) elementData = Arrays.copyOf(elementData, newCapacity); } // 确定最大容量 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) { // 溢出 throw new OutOfMemoryError(); } return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

1.4 扩容触发时机

public class ArrayListExpansion { // 1. add() 方法触发 public boolean add(E e) { ensureCapacityInternal(size + 1); // 确保容量 elementData[size++] = e; return true; } // 2. addAll() 方法触发 public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // 确保容量 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } // 3. ensureCapacity() 手动触发 public void ensureCapacity(int minCapacity) { if (minCapacity > elementData.length) { grow(minCapacity); } } }

1.5 扩容过程示例

public class ArrayListExpansionDemo { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); // 初始容量：10 System.out.println("初始容量：" + getCapacity(list)); // 0（空数组） // 添加11个元素触发扩容 for (int i = 0; i < 11; i++) { list.add(i); if (i == 10) { System.out.println("第11个元素触发扩容"); System.out.println("扩容后容量：" + getCapacity(list)); // 15 } } // 继续添加元素 for (int i = 11; i < 23; i++) { list.add(i); if (i == 15) { System.out.println("第16个元素触发扩容"); System.out.println("扩容后容量：" + getCapacity(list)); // 22 } if (i == 22) { System.out.println("第23个元素触发扩容"); System.out.println("扩容后容量：" + getCapacity(list)); // 33 } } } // 反射获取ArrayList实际容量（仅供演示） private static int getCapacity(ArrayList<?> list) { try { Field field = ArrayList.class.getDeclaredField("elementData"); field.setAccessible(true); Object[] elementData = (Object[]) field.get(list); return elementData.length; } catch (Exception e) { return -1; } } }

1.6 扩容性能分析

public class ArrayListPerformance { /** * 扩容时间复杂度：O(n) * 涉及数组复制，元素越多复制成本越高 */ public static void testAddPerformance() { int size = 1000000; // 方式1：不指定初始容量（多次扩容） long start1 = System.currentTimeMillis(); ArrayList<Integer> list1 = new ArrayList<>(); for (int i = 0; i < size; i++) { list1.add(i); } long end1 = System.currentTimeMillis(); System.out.println("不指定容量耗时：" + (end1 - start1) + "ms"); // 方式2：指定初始容量（无扩容） long start2 = System.currentTimeMillis(); ArrayList<Integer> list2 = new ArrayList<>(size); for (int i = 0; i < size; i++) { list2.add(i); } long end2 = System.currentTimeMillis(); System.out.println("指定容量耗时：" + (end2 - start2) + "ms"); } /** * 扩容次数计算： * 10 → 15 → 22 → 33 → 49 → 73 → 109 → ... * 每次扩容复制旧数组，频繁扩容影响性能 */ }

2. HashMap 自动扩容机制

2.1 核心扩容原理

HashMap 使用数组+链表/红黑树结构，当元素数量超过阈值时触发扩容。

2.2 关键参数

• 默认初始容量：16

• 默认负载因子：0.75

• 扩容阈值：容量 × 负载因子

• 扩容因子：2倍

• 树化阈值：链表长度 ≥ 8 且数组长度 ≥ 64

• 链化阈值：红黑树节点 ≤ 6

2.3 数据结构演进

数组索引: [0] -> 链表/红黑树 [1] -> 链表/红黑树 ... [n-1] -> 链表/红黑树

2.4 源码解析

// HashMap 扩容核心方法 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 1. 计算新容量 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 核心：新容量 = 旧容量 × 2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { newThr = oldThr << 1; // 新阈值也×2 } } // 2. 初始化阈值 else if (oldThr > 0) { newCap = oldThr; } else { newCap = DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12 } // 3. 创建新数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; threshold = newThr; // 4. 重新哈希（rehash）所有元素 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) { // 单个节点直接计算新位置 newTab[e.hash & (newCap - 1)] = e; } else if (e instanceof TreeNode) { // 红黑树处理 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); } else { // 链表处理（优化点） Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 关键优化：无需重新计算hash，只需判断新增bit位 if ((e.hash & oldCap) == 0) { // 位置不变 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 位置 = 原位置 + oldCap if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

2.5 扩容触发时机

public class HashMapExpansion { // put() 方法中的扩容检查 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ... if (++size > threshold) { // 关键判断 resize(); } // ... } // putAll() 方法 public void putAll(Map<? extends K, ? extends V> m) { // 可能会触发扩容 // ... } }

2.6 扩容优化：高位判断

/** * JDK 1.8 扩容优化：无需重新计算hash * * 旧容量: 16 (10000二进制) * 新容量: 32 (100000二进制) * * 元素位置计算: hash & (capacity-1) * * 扩容后元素要么在原位置，要么在"原位置+旧容量"位置 * 判断依据: (hash & oldCapacity) == 0 ? * * 示例： * hash = 18 (10010) & 15(01111) = 2 * 扩容后: hash & 31(11111) = 18 * 由于hash的第5位(从0开始)是1，所以新位置 = 2 + 16 = 18 */

2.7 扩容过程示例

public class HashMapExpansionDemo { public static void main(String[] args) { HashMap<String, Integer> map = new HashMap<>(); // 初始状态 System.out.println("初始容量：16，阈值：12"); // 添加元素触发扩容 for (int i = 0; i < 13; i++) { map.put("key" + i, i); if (i == 12) { System.out.println("第13个元素触发扩容"); // 容量变为32，阈值变为24 } } // 继续添加触发二次扩容 for (int i = 13; i < 25; i++) { map.put("key" + i, i); if (i == 24) { System.out.println("第25个元素触发扩容"); // 容量变为64，阈值变为48 } } } }

2.8 树化与链化

public class HashMapTreeify { /** * 树化条件： * 1. 链表长度 >= TREEIFY_THRESHOLD(8) * 2. 数组长度 >= MIN_TREEIFY_CAPACITY(64) * * 链化条件： * 红黑树节点 <= UNTREEIFY_THRESHOLD(6) */ public static void demonstrateTreeify() { HashMap<BadHashKey, Integer> map = new HashMap<>(); // 创建大量hash冲突的key for (int i = 0; i < 100; i++) { map.put(new BadHashKey(i), i); // 当链表长度达到8且数组长度>=64时，链表转为红黑树 } } static class BadHashKey { int value; BadHashKey(int value) { this.value = value; } // 故意制造hash冲突 @Override public int hashCode() { return value % 10; // 只有10个不同的hash值 } } }

3. 扩容性能对比与优化

3.1 性能对比表

3.2 优化建议

ArrayList 优化：

public class ArrayListOptimization { // 1. 预分配容量（最有效优化） public void optimization1() { // 已知需要10000个元素 ArrayList<Integer> list = new ArrayList<>(10000); // 避免多次扩容：10→15→22→33→49→73→109→... } // 2. 批量添加使用addAll public void optimization2() { ArrayList<Integer> list = new ArrayList<>(); List<Integer> toAdd = Arrays.asList(1, 2, 3, 4, 5); // 一次性扩容到位 list.addAll(toAdd); // 只检查一次容量 // 而不是： // for (Integer i : toAdd) { // list.add(i); // 可能多次检查扩容 // } } // 3. 适时trimToSize释放内存 public void optimization3() { ArrayList<Integer> list = new ArrayList<>(1000); // 添加100个元素后 list.trimToSize(); // 释放多余空间 } }

HashMap 优化：

public class HashMapOptimization { // 1. 预分配容量，考虑负载因子 public void optimization1() { // 预期存储100个元素 int expectedSize = 100; float loadFactor = 0.75f; // 计算初始容量 = expectedSize / loadFactor + 1 int initialCapacity = (int) (expectedSize / loadFactor) + 1; HashMap<String, Integer> map = new HashMap<>(initialCapacity, loadFactor); } // 2. 使用合适的负载因子 public void optimization2() { // 读多写少：降低负载因子（减少哈希冲突） HashMap<String, Integer> readHeavyMap = new HashMap<>(16, 0.5f); // 写多读少：提高负载因子（减少扩容次数） HashMap<String, Integer> writeHeavyMap = new HashMap<>(16, 0.9f); } // 3. 实现良好的hashCode和equals public void optimization3() { class GoodKey { String id; @Override public int hashCode() { // 良好的分布 return id.hashCode(); } @Override public boolean equals(Object obj) { // 正确实现 if (this == obj) return true; if (!(obj instanceof GoodKey)) return false; return id.equals(((GoodKey) obj).id); } } } // 4. 使用LinkedHashMap保持插入顺序 public void optimization4() { LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { // 实现LRU缓存 return size() > 100; } }; } }

3.3 扩容监控与调试

public class ExpansionMonitor { public static void monitorArrayList() { ArrayList<Integer> list = new ArrayList<>(); // 记录扩容点 for (int i = 0; i < 1000; i++) { int oldCapacity = getCapacity(list); list.add(i); int newCapacity = getCapacity(list); if (newCapacity != oldCapacity) { System.out.printf("第%d个元素触发扩容: %d -> %d%n", i + 1, oldCapacity, newCapacity); } } } public static void monitorHashMap() { HashMap<String, Integer> map = new HashMap<>(); // 使用反射监控内部状态 try { Field tableField = HashMap.class.getDeclaredField("table"); tableField.setAccessible(true); Field thresholdField = HashMap.class.getDeclaredField("threshold"); thresholdField.setAccessible(true); for (int i = 0; i < 100; i++) { int oldThreshold = (int) thresholdField.get(map); Object[] oldTable = (Object[]) tableField.get(map); int oldCapacity = oldTable == null ? 0 : oldTable.length; map.put("key" + i, i); int newThreshold = (int) thresholdField.get(map); Object[] newTable = (Object[]) tableField.get(map); int newCapacity = newTable == null ? 0 : newTable.length; if (newCapacity != oldCapacity) { System.out.printf("第%d个元素触发扩容: 容量 %d->%d, 阈值 %d->%d%n", i + 1, oldCapacity, newCapacity, oldThreshold, newThreshold); } } } catch (Exception e) { e.printStackTrace(); } } }

4. 实际应用场景

4.1 高并发场景

public class ConcurrentExpansion { /** * HashMap在并发扩容时可能导致死循环（JDK 1.7之前） * 解决方案： * 1. 使用ConcurrentHashMap * 2. 使用Collections.synchronizedMap() * 3. 使用CopyOnWriteArrayList替代ArrayList */ // 线程安全的Map public void safeUsage() { // 方案1：ConcurrentHashMap（推荐） ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>(); // 方案2：同步包装 Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>()); // 方案3：CopyOnWriteArrayList（适合读多写少） CopyOnWriteArrayList<Integer> copyOnWriteList = new CopyOnWriteArrayList<>(); } }

4.2 大数据量处理

public class BigDataProcessing { /** * 处理大数据时的优化策略 */ public void processLargeData() { // 场景：从数据库读取100万条记录 // 错误做法：频繁扩容 ArrayList<Record> badList = new ArrayList<>(); // 每次add都可能触发扩容 // 正确做法：预分配+分批处理 int totalRecords = 1000000; int batchSize = 10000; ArrayList<Record> goodList = new ArrayList<>(batchSize); for (int i = 0; i < totalRecords; i++) { Record record = fetchRecord(i); goodList.add(record); // 分批处理 if (goodList.size() >= batchSize) { processBatch(goodList); goodList.clear(); // 重用ArrayList // 注意：clear()只清空元素，不改变容量 } } } }

4.3 缓存实现

public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxSize; public LRUCache(int maxSize) { // 设置初始容量和负载因子 super((int) (maxSize / 0.75f) + 1, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } /** * 扩容考虑： * 1. maxSize应小于初始容量×负载因子，避免put时扩容 * 2. accessOrder=true开启访问顺序 */ }

5. 总结

5.1 关键差异

5.2 最佳实践

1. 预分配容量：已知数据量时，初始化时指定合适容量

2. 监控扩容：大数据量时监控扩容频率，优化性能

3. 合理选择结构：根据使用场景选择合适的数据结构

4. 并发安全：多线程环境使用线程安全版本

5. 内存优化：适时释放未使用容量

5.3 扩容性能公式

// ArrayList 扩容次数估算 int expansions = 0; int capacity = 10; while (capacity < requiredSize) { capacity = capacity + (capacity >> 1); // ×1.5 expansions++; } // HashMap 扩容次数估算 int expansions = 0; int capacity = 16; while (capacity * 0.75 < requiredSize) { capacity <<= 1; // ×2 expansions++; }