// 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);
    }
    
    // 數(shù)組復(fù)制：時間復(fù)雜度 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;
}

public class ArrayListExpansion {
    // 1. add() 方法觸發(fā)
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 確保容量
        elementData[size++] = e;
        return true;
    }
    
    // 2. addAll() 方法觸發(fā)
    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() 手動觸發(fā)
    public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }
}

public class ArrayListExpansionDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // 初始容量：10
        System.out.println("初始容量：" + getCapacity(list)); // 0（空數(shù)組）
        
        // 添加11個元素觸發(fā)擴容
        for (int i = 0; i < 11; i++) {
            list.add(i);
            if (i == 10) {
                System.out.println("第11個元素觸發(fā)擴容");
                System.out.println("擴容后容量：" + getCapacity(list)); // 15
            }
        }
        
        // 繼續(xù)添加元素
        for (int i = 11; i < 23; i++) {
            list.add(i);
            if (i == 15) {
                System.out.println("第16個元素觸發(fā)擴容");
                System.out.println("擴容后容量：" + getCapacity(list)); // 22
            }
            if (i == 22) {
                System.out.println("第23個元素觸發(fā)擴容");
                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;
        }
    }
}

public class ArrayListPerformance {
    /**
     * 擴容時間復(fù)雜度：O(n)
     * 涉及數(shù)組復(fù)制，元素越多復(fù)制成本越高
     */
    
    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");
    }
    
    /**
     * 擴容次數(shù)計算：
     * 10 → 15 → 22 → 33 → 49 → 73 → 109 → ...
     * 每次擴容復(fù)制舊數(shù)組，頻繁擴容影響性能
     */
}

數(shù)組索引: [0] -> 鏈表/紅黑樹
         [1] -> 鏈表/紅黑樹
         ...
         [n-1] -> 鏈表/紅黑樹

// 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. 創(chuàng)建新數(shù)組
    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) {
                    // 單個節(jié)點直接計算新位置
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof TreeNode) {
                    // 紅黑樹處理
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                } else {
                    // 鏈表處理（優(yōu)化點）
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 關(guān)鍵優(yōu)化：無需重新計算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;
}

public class HashMapExpansion {
    // put() 方法中的擴容檢查
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        // ...
        if (++size > threshold) {  // 關(guān)鍵判斷
            resize();
        }
        // ...
    }
    
    // putAll() 方法
    public void putAll(Map<? extends K, ? extends V> m) {
        // 可能會觸發(fā)擴容
        // ...
    }
}

/**
 * JDK 1.8 擴容優(yōu)化：無需重新計算hash
 * 
 * 舊容量: 16 (10000二進制)
 * 新容量: 32 (100000二進制)
 * 
 * 元素位置計算: hash & (capacity-1)
 * 
 * 擴容后元素要么在原位置，要么在"原位置+舊容量"位置
 * 判斷依據(jù): (hash & oldCapacity) == 0 ?
 * 
 * 示例：
 * hash = 18 (10010) & 15(01111) = 2
 * 擴容后: hash & 31(11111) = 18
 * 由于hash的第5位(從0開始)是1，所以新位置 = 2 + 16 = 18
 */

public class HashMapExpansionDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 初始狀態(tài)
        System.out.println("初始容量：16，閾值：12");
        
        // 添加元素觸發(fā)擴容
        for (int i = 0; i < 13; i++) {
            map.put("key" + i, i);
            if (i == 12) {
                System.out.println("第13個元素觸發(fā)擴容");
                // 容量變?yōu)?2，閾值變?yōu)?4
            }
        }
        
        // 繼續(xù)添加觸發(fā)二次擴容
        for (int i = 13; i < 25; i++) {
            map.put("key" + i, i);
            if (i == 24) {
                System.out.println("第25個元素觸發(fā)擴容");
                // 容量變?yōu)?4，閾值變?yōu)?8
            }
        }
    }
}

public class HashMapTreeify {
    /**
     * 樹化條件：
     * 1. 鏈表長度 >= TREEIFY_THRESHOLD(8)
     * 2. 數(shù)組長度 >= MIN_TREEIFY_CAPACITY(64)
     * 
     * 鏈化條件：
     * 紅黑樹節(jié)點 <= UNTREEIFY_THRESHOLD(6)
     */
    
    public static void demonstrateTreeify() {
        HashMap<BadHashKey, Integer> map = new HashMap<>();
        
        // 創(chuàng)建大量hash沖突的key
        for (int i = 0; i < 100; i++) {
            map.put(new BadHashKey(i), i);
            // 當鏈表長度達到8且數(shù)組長度>=64時，鏈表轉(zhuǎn)為紅黑樹
        }
    }
    
    static class BadHashKey {
        int value;
        
        BadHashKey(int value) {
            this.value = value;
        }
        
        // 故意制造hash沖突
        @Override
        public int hashCode() {
            return value % 10; // 只有10個不同的hash值
        }
    }
}

public class ArrayListOptimization {
    // 1. 預(yù)分配容量（最有效優(yōu)化）
    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釋放內(nèi)存
    public void optimization3() {
        ArrayList<Integer> list = new ArrayList<>(1000);
        // 添加100個元素后
        list.trimToSize(); // 釋放多余空間
    }
}

public class HashMapOptimization {
    // 1. 預(yù)分配容量，考慮負載因子
    public void optimization1() {
        // 預(yù)期存儲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);
        
        // 寫多讀少：提高負載因子（減少擴容次數(shù)）
        HashMap<String, Integer> writeHeavyMap = new HashMap<>(16, 0.9f);
    }
    
    // 3. 實現(xiàn)良好的hashCode和equals
    public void optimization3() {
        class GoodKey {
            String id;
            
            @Override
            public int hashCode() {
                // 良好的分布
                return id.hashCode();
            }
            
            @Override
            public boolean equals(Object obj) {
                // 正確實現(xiàn)
                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) {
                // 實現(xiàn)LRU緩存
                return size() > 100;
            }
        };
    }
}

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個元素觸發(fā)擴容: %d -> %d%n", 
                    i + 1, oldCapacity, newCapacity);
            }
        }
    }
    
    public static void monitorHashMap() {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 使用反射監(jiān)控內(nèi)部狀態(tài)
        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個元素觸發(fā)擴容: 容量 %d->%d, 閾值 %d->%d%n",
                        i + 1, oldCapacity, newCapacity, oldThreshold, newThreshold);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

public class ConcurrentExpansion {
    /**
     * HashMap在并發(fā)擴容時可能導(dǎo)致死循環(huán)（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<>();
    }
}

public class BigDataProcessing {
    /**
     * 處理大數(shù)據(jù)時的優(yōu)化策略
     */
    
    public void processLargeData() {
        // 場景：從數(shù)據(jù)庫讀取100萬條記錄
        
        // 錯誤做法：頻繁擴容
        ArrayList<Record> badList = new ArrayList<>();
        // 每次add都可能觸發(fā)擴容
        
        // 正確做法：預(yù)分配+分批處理
        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()只清空元素，不改變?nèi)萘?
            }
        }
    }
}

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        // 設(shè)置初始容量和負載因子
        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應(yīng)小于初始容量×負載因子，避免put時擴容
     * 2. accessOrder=true開啟訪問順序
     */
}

// ArrayList 擴容次數(shù)估算
int expansions = 0;
int capacity = 10;
while (capacity < requiredSize) {
    capacity = capacity + (capacity >> 1); // ×1.5
    expansions++;
}

// HashMap 擴容次數(shù)估算
int expansions = 0;
int capacity = 16;
while (capacity * 0.75 < requiredSize) {
    capacity <<= 1; // ×2
    expansions++;
}