Android专属集合 ⭐⭐

public class SparseArray<E> implements Cloneable {
    // 标记"已删除"的哨兵对象，后面延迟删除章节会详细讲
    private static final Object DELETED = new Object();
 
    // 是否存在被标记为 DELETED 但尚未物理清除的槽位
    private boolean mGarbage = false;
 
    // 存储 int 类型的 key，始终保持升序排列
    private int[] mKeys;
 
    // 存储对应的 value，mValues[i] 对应 mKeys[i]
    private Object[] mValues;
 
    // 当前实际存储的有效键值对数量（不含 DELETED 槽位）
    private int mSize;
}

// ========== HashMap<Integer, Object> 的内存布局 ==========
//
//  HashMap 对象
//  ┌─────────────────────────────┐
//  │ Node[] table (长度16+)       │
//  │ ┌───┬───┬───┬───┬───┬─···  │
//  │ │ 0 │ 1 │ 2 │ 3 │ 4 │     │  ← 每个槽位 4~8 bytes 指针
//  │ └─┬─┴───┴─┬─┴───┴───┴─··· │
//  └───┼───────┼────────────────┘
//      ↓       ↓
//   Node obj  Node obj               ← 每个 Node: 32~48 bytes
//   ┌──────┐  ┌──────┐
//   │hash  │  │hash  │
//   │key ──┼→ Integer(3)             ← Integer 包装: 16 bytes
//   │val ──┼→ "Alice"                ← 值对象
//   │next  │  │next  │
//   └──────┘  └──────┘
//
//  每个条目总开销 ≈ 指针(8) + Node(32) + Integer(16) = ~56 bytes 额外开销
//
//
// ========== SparseArray 的内存布局 ==========
//
//  SparseArray 对象
//  ┌──────────────────────────────────────┐
//  │ int[] mKeys     (原始int, 无装箱)     │
//  │ ┌─────┬─────┬─────┬─────┬─────┐     │
//  │ │  1  │  3  │  10 │  25 │  42 │     │  ← 每个 key 仅 4 bytes
//  │ └─────┴─────┴─────┴─────┴─────┘     │
//  │                                      │
//  │ Object[] mValues (直接引用)           │
//  │ ┌─────┬─────┬─────┬─────┬─────┐     │
//  │ │"Tom"│"Ali"│"Bob"│"Cat"│"Dog"│     │  ← 每个 value 仅 4~8 bytes 指针
//  │ └─────┴─────┴─────┴─────┴─────┘     │
//  │                                      │
//  │ mSize = 5                            │
//  └──────────────────────────────────────┘
//
//  每个条目总开销 ≈ int(4) + 指针(4~8) = ~8~12 bytes 额外开销

// 默认构造，初始容量为 10
public SparseArray() {
    this(10); // 默认分配 10 个槽位
}
 
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        // 容量为 0 时使用共享的空数组常量，避免分配
        mKeys = EmptyArray.INT;       // 静态共享的 int[0]
        mValues = EmptyArray.OBJECT;  // 静态共享的 Object[0]
    } else {
        // 根据指定容量分配两个等长数组
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length]; // key 数组与 value 数组等长
    }
    mSize = 0; // 初始元素数量为 0
}

// ContainerHelpers.java —— Android 容器工具类中的二分查找
static int binarySearch(int[] array, int size, int value) {
    int lo = 0;           // 搜索范围的左边界（包含）
    int hi = size - 1;    // 搜索范围的右边界（包含）
 
    while (lo <= hi) {
        // 无符号右移求中点，避免 (lo + hi) 整数溢出
        final int mid = (lo + hi) >>> 1;
        // 取中点处的 key 值
        final int midVal = array[mid];
 
        if (midVal < value) {
            // 目标值在右半区，收缩左边界
            lo = mid + 1;
        } else if (midVal > value) {
            // 目标值在左半区，收缩右边界
            hi = mid - 1;
        } else {
            // 找到了，直接返回索引（非负值）
            return mid;  // value found
        }
    }
    // 没找到，返回 ~lo（按位取反）
    // ~lo 一定是负数，表示"如果要插入，应该插在 lo 位置"
    return ~lo;  // value not present
}

// 使用示例：
int index = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
if (index >= 0) {
    // 找到了，index 就是 key 在 mKeys 中的位置
    return mValues[index];
} else {
    // 没找到，~index 就是应该插入的位置
    int insertPos = ~index;
    // 在 insertPos 处插入新的 key-value
}

// 假设当前 SparseArray 的状态：
// mKeys   = [1, 5, 10, 20, 50]
// mValues = [A,  B,  C,  D,  E]
// mSize   = 5
 
// === 场景1: 查找 key=10（存在） ===
// lo=0, hi=4
// mid=2, midVal=10 == 10 → 命中! 返回 2
// 结果: mValues[2] = "C" ✓
 
// === 场景2: 查找 key=15（不存在，应插在 index=3） ===
// lo=0, hi=4
//   mid=2, midVal=10 < 15 → lo=3
// lo=3, hi=4
//   mid=3, midVal=20 > 15 → hi=2
// lo=3 > hi=2 → 循环结束
// 返回 ~3 = -4（二进制取反）
// 调用方: ~(-4) = 3 → 插入位置是 index=3 ✓
 
// === 场景3: 查找 key=0（不存在，应插在 index=0） ===
// lo=0, hi=4
//   mid=2, midVal=10 > 0 → hi=1
// lo=0, hi=1
//   mid=0, midVal=1 > 0 → hi=-1
// lo=0 > hi=-1 → 循环结束
// 返回 ~0 = -1
// 调用方: ~(-1) = 0 → 插入位置是 index=0 ✓

public void put(int key, E value) {
    // 第一步：二分查找 key 的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
    if (i >= 0) {
        // 找到了相同的 key，直接覆盖 value（等价于 HashMap 的 put 覆盖语义）
        mValues[i] = value;
    } else {
        // 没找到，将负数索引还原为插入位置
        i = ~i;
 
        // 优化：如果插入位置恰好是一个 DELETED 槽位，直接复用
        // 这样就不需要移动数组元素了
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;     // 覆盖 key
            mValues[i] = value; // 覆盖 value
            return;             // 完成，无需调整 mSize
        }
 
        // 如果存在垃圾槽位且数组已满，先做一次压缩
        if (mGarbage && mSize >= mKeys.length) {
            gc(); // 压缩数组，清除所有 DELETED 槽位
 
            // gc() 之后数组布局变了，需要重新二分查找插入位置
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
 
        // 在位置 i 处插入新元素（可能触发数组扩容 + 元素后移）
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++; // 有效元素数 +1
    }
}

public E get(int key) {
    return get(key, null); // 默认 fallback 为 null
}
 
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    // 二分查找 key 的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
    // 没找到，或者找到的位置已被标记为 DELETED
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound; // 返回默认值
    } else {
        return (E) mValues[i]; // 找到了，强转返回
    }
}

// SparseArray 底层存储
int[]    keys;    // [10, 20, 30, 40, 50]  — 有序排列
Object[] values;  // [A,  B,  C,  D,  E ]  — 与 keys 一一对应

// 直接删除 key=30 → 需要数组搬移 (System.arraycopy)
// 删除前: [10, 20, 30, 40, 50]
//                  ↑ 删这个
// 删除后: [10, 20, 40, 50, __]
//                  ←←←←←← 后面全部左移

// SparseArray.java 源码
private static final Object DELETED = new Object(); // 全局唯一的"墓碑"标记

// SparseArray.delete() 源码简化
public void delete(int key) {
    // 用二分查找定位 key 在 keys[] 中的索引
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
    // 如果找到了（索引 >= 0）
    if (i >= 0) {
        // 不搬移数组！只是把 value 标记为 DELETED
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED; // 打上"墓碑"标记
            mGarbage = true;      // 设置"有垃圾需要清理"的标志位
        }
    }
}

// delete(30) 之后的内存状态
// keys:   [10,  20,  30,      40,  50]   ← key 还在原位！
// values: [ A,   B,  DELETED,  D,   E]   ← 只是 value 被替换了
//                     ^^^^^^^^
//                     墓碑标记，不是 null
// mGarbage = true  ← 标记"有垃圾待清理"
// mSize 不变       ← 逻辑大小暂时不变

SparseArray<String> sparse = new SparseArray<>();
 
sparse.put(1, "hello");  // 正常存值
sparse.put(2, null);     // 合法！用户主动存了一个 null
sparse.delete(1);        // 删除 key=1
 
// 此时内部状态：
// keys:   [1,       2   ]
// values: [DELETED, null ]
//          ↑ 已删除  ↑ 用户存的合法 null

// SparseArray.gc() 源码简化
private void gc() {
    int n = mSize;           // 当前逻辑大小（含 DELETED 的）
    int o = 0;               // 压缩后的写入指针，指向下一个有效位置
    int[] keys = mKeys;
    Object[] values = mValues;
 
    // 遍历所有元素
    for (int i = 0; i < n; i++) {
        Object val = values[i];
 
        // 只保留非 DELETED 的元素
        if (val != DELETED) {
            // 如果当前位置 i 和写入位置 o 不同，说明前面有空洞
            if (i != o) {
                keys[o] = keys[i];     // 把 key 搬到前面
                values[o] = values[i]; // 把 value 搬到前面
                values[i] = null;      // 清理旧位置，帮助 JVM GC
            }
            o++; // 写入指针前进
        }
    }
 
    mGarbage = false; // 清理完毕，重置标志位
    mSize = o;        // 更新真实大小
}

// gc() 压缩过程演示
// 假设连续删除了 key=20 和 key=40
 
// gc() 之前:
// index:  [0]  [1]      [2]  [3]      [4]
// keys:   [10, 20,      30,  40,      50]
// values: [A,  DELETED, C,   DELETED, E ]
// mSize = 5, mGarbage = true
 
// ---- gc() 开始遍历 ----
// i=0: values[0]=A (有效) → keys[0]=10, values[0]=A, o=1
// i=1: values[1]=DELETED  → 跳过
// i=2: values[2]=C (有效) → keys[1]=30, values[1]=C, o=2  ← 搬移！
// i=3: values[3]=DELETED  → 跳过
// i=4: values[4]=E (有效) → keys[2]=50, values[2]=E, o=3  ← 搬移！
 
// gc() 之后:
// index:  [0]  [1]  [2]  [3]    [4]
// keys:   [10, 30,  50,  (40),  (50) ]  ← 后面是残留数据，不影响
// values: [A,  C,   E,   null,  null ]  ← 旧位置已清 null
// mSize = 3, mGarbage = false

// 1. size() — 需要返回精确的元素个数
public int size() {
    if (mGarbage) {
        gc(); // 必须先压缩，才能得到真实 size
    }
    return mSize;
}
 
// 2. keyAt(index) / valueAt(index) — 按索引访问
// 需要确保索引对应的是有效元素，而非 DELETED 空洞
public int keyAt(int index) {
    if (mGarbage) {
        gc(); // 先压缩，保证索引连续
    }
    return mKeys[index];
}
 
// 3. put() 中发现需要插入新元素且数组已满
// 在扩容之前先 gc()，看看压缩后是否还需要扩容
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 
    if (i >= 0) {
        // key 已存在，直接覆盖 value
        mValues[i] = value;
    } else {
        i = ~i; // 取反得到插入位置
 
        // 关键优化：如果插入位置恰好是 DELETED 槽位，直接复用！
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value; // 废物利用，零成本插入
            return;
        }
 
        // 如果有垃圾且数组满了，先 gc() 再决定是否扩容
        if (mGarbage && mSize >= mKeys.length) {
            gc();
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); // 重新定位
        }
 
        // 插入新元素（可能需要数组搬移）
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

// 槽位复用场景演示
SparseArray<String> sparse = new SparseArray<>();
sparse.put(10, "A");
sparse.put(20, "B");
sparse.put(30, "C");
 
// 内部: keys=[10, 20, 30], values=[A, B, C]
 
sparse.delete(20);
// 内部: keys=[10, 20, 30], values=[A, DELETED, C]
//                ↑ 这个位置被标记为 DELETED
 
sparse.put(20, "X");
// 二分查找 key=20 → 命中 index=1
// 发现 values[1] == DELETED → 直接复用！
// 内部: keys=[10, 20, 30], values=[A, X, C]
// 没有触发 gc()，没有数组搬移，O(log n) 完成！

// 场景：在一个 size=500 的 SparseArray 中连续删除 100 个元素
 
// ❌ 直接删除策略（假设的）
// 每次删除都要 System.arraycopy
// 最坏情况：500 + 499 + 498 + ... + 401 = 约 45,000 次元素搬移
// 时间复杂度：O(n × k)，其中 k 是删除次数
 
// ✅ 延迟删除策略（SparseArray 实际实现）
// 100 次 delete()：每次只做二分查找 + 赋值 = O(log n) × 100
// 最后触发一次 gc()：O(n) 的线性扫描
// 总计：O(k × log n + n) ≈ O(k × log n)，远优于直接删除

SparseArray<String> cache = new SparseArray<>();
 
// ① 初始填充
cache.put(100, "alpha");   // keys=[100], values=[alpha]
cache.put(200, "beta");    // keys=[100,200], values=[alpha,beta]
cache.put(300, "gamma");   // keys=[100,200,300], values=[alpha,beta,gamma]
cache.put(400, "delta");   // keys=[100,200,300,400], values=[alpha,beta,gamma,delta]
 
// ② 延迟删除
cache.delete(200);         // values[1] = DELETED, mGarbage = true
cache.delete(300);         // values[2] = DELETED, mGarbage = true
// 内部状态: keys=[100,200,300,400], values=[alpha,DELETED,DELETED,delta]
// 注意：mSize 仍然是 4！
 
// ③ 槽位复用
cache.put(200, "epsilon"); // 二分查找命中 index=1，发现 DELETED → 直接复用
// 内部状态: keys=[100,200,300,400], values=[alpha,epsilon,DELETED,delta]
 
// ④ 触发 gc()
int size = cache.size();   // size() 检测到 mGarbage=true → 触发 gc()
// gc() 压缩后: keys=[100,200,400], values=[alpha,epsilon,delta]
// mSize = 3, mGarbage = false
// size 返回 3

SparseArray<String> sparse = new SparseArray<>();
sparse.put(1, "A");
sparse.put(2, "B");
sparse.put(3, "C");
sparse.delete(2);
sparse.delete(3);
sparse.put(2, "D");
// 此时调用 sparse.size() = ?

// 一个 int 基本类型：4 bytes，就这么简单
int key = 42;
 
// 一个 Integer 对象的内存布局（64位 JVM，开启指针压缩）：
// ┌─────────────────────────────────────────────┐
// │ Object Header (Mark Word)     : 8 bytes     │  // 锁状态、GC 年龄、hashCode 等
// │ Object Header (Klass Pointer) : 4 bytes     │  // 指向 Integer.class 的压缩指针
// │ int value 字段                 : 4 bytes     │  // 实际存储的 int 值
// │ Padding (对齐填充)             : 0 bytes     │  // 已经是 8 的倍数，无需填充
// ├─────────────────────────────────────────────┤
// │ 合计                           : 16 bytes    │  // 是 int 的 4 倍！
// └─────────────────────────────────────────────┘

// Integer 缓存机制源码简化
public static Integer valueOf(int i) {
    // 只有 -128 ~ 127 范围内的值会复用缓存对象
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    // 超出范围？每次都 new 一个新对象，产生 GC 压力
    return new Integer(i);
}

HashMap 内部结构（每存一个键值对的开销）
 
┌──────────────────────────────────────────────────────────┐
│                    HashMap 对象本身                        │
│  table (Node[] 数组引用)          : 4 bytes               │
│  size, threshold, loadFactor...  : ~20 bytes              │
│  ─────────────────────────────────────────────            │
│  Node[] table 数组               : 16 + 4*capacity bytes  │
│  (数组对象头 + 每个槽位的引用)                               │
└──────────────────────────────────────────────────────────┘
 
┌──────────────────────────────────────────────────────────┐
│              每个 Entry (HashMap.Node)                     │
│  Object Header                   : 12 bytes               │
│  int hash (缓存的哈希值)          : 4 bytes                │
│  Object next (链表下一个节点)     : 4 bytes                │
│  Object key (指向 Integer 对象)   : 4 bytes                │
│  Object value (指向 value 对象)   : 4 bytes                │
│  Padding                         : 4 bytes                │
│  ────────────────────────────────────────────             │
│  合计                             : 32 bytes per entry    │
└──────────────────────────────────────────────────────────┘

// HashMap 存储一个 int->Object 映射的内存成本估算
// Integer key 对象       : 16 bytes   // 装箱产生的包装对象
// HashMap.Node 对象      : 32 bytes   // Entry 节点本身
// Node[] 中的槽位引用     : ~4 bytes   // 数组中指向 Node 的指针（均摊）
// ──────────────────────────────────
// 合计约                  : ~52 bytes  // 每个键值对的总开销

SparseArray 内部结构
 
┌──────────────────────────────────────────────────────┐
│                 SparseArray 对象                       │
│  int[] mKeys     ──→ [3, 10, 42, 100, ...]           │
│                       每个元素 4 bytes，无装箱          │
│                                                       │
│  Object[] mValues ──→ [valA, valB, valC, valD, ...]   │
│                       每个元素 4 bytes (对象引用)       │
│                                                       │
│  int mSize        : 4 bytes                           │
└──────────────────────────────────────────────────────┘
 
每个键值对的内存成本：
  int key (在 int[] 中)       : 4 bytes    // 原始类型，零额外开销
  Object ref (在 Object[] 中) : 4 bytes    // 仅一个引用
  ─────────────────────────────────────
  合计约                       : ~8 bytes   // 每个键值对

┌─────────────────────┬──────────────────┬──────────────────┐
│       开销项目       │    HashMap       │   SparseArray    │
├─────────────────────┼──────────────────┼──────────────────┤
│ Key 存储            │ 500 × 16B = 8KB  │ 500 × 4B = 2KB  │
│ (Integer 对象)      │ (装箱对象)        │ (int[] 原始数组)  │
├─────────────────────┼──────────────────┼──────────────────┤
│ Entry/Node 对象     │ 500 × 32B = 16KB │ 0 (无 Entry)     │
├─────────────────────┼──────────────────┼──────────────────┤
│ 桶数组 (table)      │ ~4KB             │ 0 (无桶)          │
│ (capacity=1024)     │                  │                   │
├─────────────────────┼──────────────────┼──────────────────┤
│ Value 引用          │ (含在 Node 中)    │ 500 × 4B = 2KB   │
├─────────────────────┼──────────────────┼──────────────────┤
│ 总计 (约)           │ ~28 KB           │ ~4 KB             │
├─────────────────────┼──────────────────┼──────────────────┤
│ 内存节省            │ 基准              │ 节省约 85%        │
└─────────────────────┴──────────────────┴──────────────────┘

// 存储 500 个映射时，堆上的对象数量对比
 
// HashMap 方案：
// 1 个 HashMap 对象
// 1 个 Node[] 数组
// 500 个 HashMap.Node 对象
// 500 个 Integer 对象（假设都超出缓存范围）
// ──────────────────
// 合计：约 1002 个对象    ← GC 需要遍历和标记这些对象
 
// SparseArray 方案：
// 1 个 SparseArray 对象
// 1 个 int[] 数组（基本类型数组，内部无对象引用）
// 1 个 Object[] 数组
// ──────────────────
// 合计：约 3 个对象       ← GC 几乎无额外负担

┌──────────────────┬────────────────────────┬────────────────────────┐
│     操作          │      HashMap           │     SparseArray        │
├──────────────────┼────────────────────────┼────────────────────────┤
│ put / get        │ O(1) 均摊              │ O(log n) 二分查找       │
│                  │ 哈希计算 + 数组定位      │ 查找快，但插入可能搬移   │
├──────────────────┼────────────────────────┼────────────────────────┤
│ delete           │ O(1) 均摊              │ O(log n) 查找           │
│                  │                        │ + O(1) 标记 DELETED     │
├──────────────────┼────────────────────────┼────────────────────────┤
│ 插入（中间位置）  │ O(1) 均摊              │ O(n) 数组搬移           │
│                  │                        │ 最坏情况需移动所有元素    │
├──────────────────┼────────────────────────┼────────────────────────┤
│ 遍历             │ 需跳过空桶，不保序       │ 天然有序，顺序遍历高效    │
│                  │ 缓存不友好              │ 数组连续内存，缓存友好    │
├──────────────────┼────────────────────────┼────────────────────────┤
│ 哈希冲突         │ 链表/红黑树退化风险      │ 不存在（无哈希机制）      │
└──────────────────┴────────────────────────┴────────────────────────┘

// ========== HashMap 方案 ==========
// 泛型要求 key 必须是 Integer，触发自动装箱
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1001, "Alice");    // 1001 被装箱为 new Integer(1001)
hashMap.put(2002, "Bob");      // 2002 被装箱为 new Integer(2002)
 
// 取值时，传入的 int 也会被装箱为 Integer，再调用 equals() 比较
String name = hashMap.get(1001);  // int 1001 → Integer.valueOf(1001) → equals()
 
// 遍历需要通过 entrySet()，每个 Entry 都是堆上的独立对象
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
    int key = entry.getKey();       // Integer → int，触发拆箱
    String value = entry.getValue();
}
 
// ========== SparseArray 方案 ==========
// key 直接是 int，value 是泛型，无任何装箱
SparseArray<String> sparse = new SparseArray<>();
sparse.put(1001, "Alice");    // 直接存入 int[] keys，零装箱
sparse.put(2002, "Bob");      // 同上
 
// 取值时直接用 int 做二分查找，无装箱、无 equals()
String name2 = sparse.get(1001);  // 纯 int 比较，高效
 
// 遍历通过 index 访问，无中间对象
for (int i = 0; i < sparse.size(); i++) {
    int key = sparse.keyAt(i);       // 直接从 int[] 读取
    String value = sparse.valueAt(i); // 直接从 Object[] 读取
    // 无 Entry 对象，无 Iterator 对象，GC 友好
}

// SparseArray 不是 java.util.Map 的实现类
// 以下代码会编译报错：
// Map<Integer, String> map = new SparseArray<>();  // ✗ 编译错误
 
// 这意味着：
// 1. 不能传给接受 Map 参数的方法
// 2. 不能用 Collections 工具类操作
// 3. 不支持 Stream API（Java 8）
// 4. 不支持 putIfAbsent、compute 等 Map 默认方法
 
// 如果你的代码需要面向 Map 接口编程，HashMap 仍然是正确选择
// SparseArray 是 Android 平台的特化优化，不是 Map 的通用替代品

// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// 场景 1：View ID → View 引用的映射
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// Android 的 View ID 本质上就是 int（R.id.xxx 编译后是 int 常量）
// 这是 SparseArray 最经典的用武之地
SparseArray<View> viewCache = new SparseArray<>();
viewCache.put(R.id.text_title, findViewById(R.id.text_title));     // key 是 int 型资源 ID
viewCache.put(R.id.btn_submit, findViewById(R.id.btn_submit));     // 无装箱，直接存储
viewCache.put(R.id.img_avatar, findViewById(R.id.img_avatar));     // 内存紧凑
 
// 实际上 Android 的 ViewHolder 模式内部就大量使用 SparseArray
 
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// 场景 2：消息类型 → Handler 的映射
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// Message.what 是 int 类型，完美匹配 SparseArray
SparseArray<MessageHandler> handlers = new SparseArray<>();
handlers.put(MSG_LOAD_DATA, new DataLoadHandler());     // what = 1
handlers.put(MSG_UPDATE_UI, new UIUpdateHandler());     // what = 2
handlers.put(MSG_NETWORK_ERROR, new ErrorHandler());    // what = 3
 
// 收到消息时直接查找对应的 handler
public void handleMessage(Message msg) {
    MessageHandler handler = handlers.get(msg.what);    // O(log n) 查找
    if (handler != null) {
        handler.handle(msg);    // 分发处理
    }
}
 
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// 场景 3：状态码 → 描述信息的映射
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// HTTP 状态码、业务错误码等，天然是 int
SparseArray<String> statusMessages = new SparseArray<>();
statusMessages.put(200, "OK");                          // 成功
statusMessages.put(404, "Not Found");                   // 未找到
statusMessages.put(500, "Internal Server Error");       // 服务器错误
statusMessages.put(10001, "Token Expired");             // 自定义业务码

// 二分查找的比较次数 = log2(n)
// n = 100   → log2(100)  ≈ 7 次比较    ← 非常快
// n = 500   → log2(500)  ≈ 9 次比较    ← 依然很快
// n = 1000  → log2(1000) ≈ 10 次比较   ← 可以接受
// n = 5000  → log2(5000) ≈ 13 次比较   ← 查找本身还行
// n = 10000 → log2(10000)≈ 14 次比较   ← 查找还行，但插入搬移成本高
 
// 真正的瓶颈不在查找，而在插入时的数组搬移：
// 在 SparseArray 中间位置插入一个元素，需要将后面所有元素后移
// System.arraycopy(mKeys, insertPos, mKeys, insertPos + 1, mSize - insertPos);
// 当 n = 1000 时，最坏情况需要搬移 1000 个 int（约 4KB 数据）
// 当 n = 10000 时，最坏情况需要搬移 10000 个 int（约 40KB 数据）
// 这个 O(n) 的搬移操作才是大数据量下的性能杀手

// ✗ 场景 1：key 不是 int 类型
// String key、Long key、自定义对象 key → 只能用 HashMap
HashMap<String, User> userMap = new HashMap<>();  // key 是 String，无法用 SparseArray
 
// ✗ 场景 2：数据量很大（数万级别）
// 频繁插入删除时，数组搬移的 O(n) 成本太高
// 此时 HashMap 的 O(1) 优势会非常明显
HashMap<Integer, Record> bigDataMap = new HashMap<>(20000);
 
// ✗ 场景 3：需要线程安全
// SparseArray 没有任何同步机制，多线程下不安全
// 应使用 ConcurrentHashMap 或加锁的 HashMap
ConcurrentHashMap<Integer, Session> sessionMap = new ConcurrentHashMap<>();
 
// ✗ 场景 4：需要面向 Map 接口编程
// 框架层代码、库代码通常需要接受 Map 类型参数
public void processData(Map<Integer, String> data) {
    // SparseArray 无法传入这里
}
 
// ✗ 场景 5：需要 null key
// HashMap 允许一个 null key
// SparseArray 的 key 是 int，不存在 null 的概念

// Android 源码中的真实使用案例：
 
// 1. View.java — 存储 View 的 tag
// 每个 View 可以通过 setTag(int key, Object tag) 存储多个 tag
// 内部就是用 SparseArray 实现的
private SparseArray<Object> mKeyedTags;  // key 是 int 型的 tag ID
 
// 2. Activity.java — 管理 Fragment
// FragmentManager 内部用 SparseArray 存储 Fragment
SparseArray<Fragment> mActive;           // key 是 Fragment 的 index
 
// 3. Resources.java — 缓存已加载的资源
// 资源 ID (R.drawable.xxx) 是 int，用 SparseArray 缓存 Drawable
SparseArray<WeakReference<Drawable>> mDrawableCache;
 
// 4. PackageManager — 存储权限信息
// uid 是 int 类型，完美匹配
SparseArray<String[]> mPermissions;      // uid → 权限列表

┌────────────────────────────┬──────────────┬──────────────┐
│         判断条件            │  SparseArray │   HashMap    │
├────────────────────────────┼──────────────┼──────────────┤
│ Key 类型是 int              │     ✅       │     ✅       │
│ Key 类型是 String/Object    │     ✗        │     ✅       │
│ 数据量 < 几百               │     ✅ 首选   │     可用     │
│ 数据量 几百~1000            │     ✅ 推荐   │     可用     │
│ 数据量 > 1000               │     谨慎     │     ✅ 首选   │
│ 内存敏感（移动端）           │     ✅ 首选   │     次选     │
│ 需要 Map 接口兼容           │     ✗        │     ✅       │
│ 多线程并发                  │     ✗        │  ConcurrentHM│
│ 需要有序遍历（按 key 排序）  │     ✅ 天然   │  需 TreeMap  │
│ 高频随机插入删除             │     次选     │     ✅       │
└────────────────────────────┴──────────────┴──────────────┘

// 使用 SparseArray<Boolean> 存储布尔值
SparseArray<Boolean> flags = new SparseArray<>();
flags.put(1, true);  // true 被自动装箱为 Boolean.TRUE 对象
flags.put(2, false); // false 被自动装箱为 Boolean.FALSE 对象
// 虽然 Boolean.TRUE/FALSE 是缓存的，但 Integer 超出 -128~127 就会创建新对象

// === SparseBooleanArray 核心字段 ===
public class SparseBooleanArray implements Cloneable {
    private int[] mKeys;        // key 数组，与 SparseArray 完全一致
    private boolean[] mValues;  // value 数组：boolean 原始类型，1 byte 每个元素
    private int mSize;          // 当前有效元素数量
}
 
// === SparseIntArray 核心字段 ===
public class SparseIntArray implements Cloneable {
    private int[] mKeys;        // key 数组
    private int[] mValues;      // value 数组：int 原始类型，4 bytes 每个元素
    private int mSize;
}
 
// === SparseLongArray 核心字段 ===
public class SparseLongArray implements Cloneable {
    private int[] mKeys;        // key 数组
    private long[] mValues;     // value 数组：long 原始类型，8 bytes 每个元素
    private int mSize;
}

// SparseBooleanArray.delete() 源码简化
public void delete(int key) {
    // 二分查找定位 key 的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        // 立即搬移数组，将 i 之后的元素前移一位
        System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1));    // key 数组搬移
        System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1)); // value 数组搬移
        mSize--;  // 有效长度减一
    }
}

// ==================== SparseBooleanArray 使用示例 ====================
SparseBooleanArray checkedStates = new SparseBooleanArray();
 
// put：存入 key-value 对
checkedStates.put(0, true);    // position 0 被选中
checkedStates.put(3, false);   // position 3 未选中
checkedStates.put(7, true);    // position 7 被选中
 
// get：获取值，返回 boolean 原始类型，无装箱
boolean isChecked = checkedStates.get(0);          // 返回 true
boolean fallback  = checkedStates.get(99, false);  // key 不存在，返回默认值 false
 
// 遍历：通过 index 遍历
for (int i = 0; i < checkedStates.size(); i++) {
    int key = checkedStates.keyAt(i);       // 获取第 i 个 key
    boolean val = checkedStates.valueAt(i); // 获取第 i 个 value，无装箱
}
 
// ==================== SparseIntArray 使用示例 ====================
SparseIntArray scoreboard = new SparseIntArray();
 
scoreboard.put(1001, 95);   // 学号 1001 -> 分数 95
scoreboard.put(1002, 87);   // 学号 1002 -> 分数 87
scoreboard.put(1003, 72);   // 学号 1003 -> 分数 72
 
int score = scoreboard.get(1001);          // 返回 95，int 原始类型
int miss  = scoreboard.get(9999, -1);      // key 不存在，返回 -1
 
// ==================== SparseLongArray 使用示例 ====================
SparseLongArray timestamps = new SparseLongArray();
 
timestamps.put(1, System.currentTimeMillis());       // 事件 1 的时间戳
timestamps.put(2, System.currentTimeMillis() + 1000); // 事件 2 的时间戳
 
long time = timestamps.get(1);             // 返回 long 原始类型，无装箱
long none = timestamps.get(99, -1L);       // key 不存在，返回 -1L

// Android 框架源码 AbsListView 中的实际用法（简化）
public class AbsListView extends AdapterView<ListAdapter> {
    // 用 SparseBooleanArray 记录每个 position 的选中状态
    SparseBooleanArray mCheckStates;
 
    // 当用户点击某个 item 时
    boolean performItemClick(View view, int position, long id) {
        if (mChoiceMode == CHOICE_MODE_MULTIPLE) {
            // 读取当前状态并取反
            boolean checked = !mCheckStates.get(position, false);
            // 更新选中状态
            mCheckStates.put(position, checked);
            // ...
        }
    }
 
    // 获取所有选中的 position
    public SparseBooleanArray getCheckedItemPositions() {
        return mCheckStates;  // 直接返回，外部可遍历
    }
}

// ===== 方案一：HashMap<Integer, Boolean> =====
// 每个 Entry 对象：
//   对象头                    = 16 bytes
//   Integer key 对象          = 16 bytes (对象头) + 4 bytes (int值) + 4 bytes (对齐) = 24 bytes
//   Boolean value 对象        = 16 bytes (对象头) + 1 byte (boolean值) + 7 bytes (对齐) = 24 bytes
//   hash 字段                 = 4 bytes
//   next 引用                 = 8 bytes
//   key 引用                  = 8 bytes
//   value 引用                = 8 bytes
// 单个 Entry 合计             ≈ 16 + 24 + 24 + 4 + 8 + 8 + 8 = 92 bytes
// （注：Boolean.TRUE/FALSE 有缓存，实际可能共享，但 Integer 超出缓存范围则不共享）
//
// 500 个 Entry               ≈ 92 × 500 = 46,000 bytes
// table 数组 (容量 1024)      = 8 × 1024 = 8,192 bytes
// HashMap 对象本身             ≈ 48 bytes
// 总计                        ≈ 54,240 bytes ≈ 53 KB
 
// ===== 方案二：SparseBooleanArray =====
// int[] mKeys                 = 16 bytes (数组头) + 4 × 500 = 2,016 bytes
// boolean[] mValues           = 16 bytes (数组头) + 1 × 500 + 4 (对齐) = 520 bytes
// SparseBooleanArray 对象本身  ≈ 32 bytes
// 总计                        ≈ 2,568 bytes ≈ 2.5 KB

// 差异一：没有 DELETED 标记，delete 立即生效
SparseBooleanArray sba = new SparseBooleanArray();
sba.put(1, true);
sba.put(2, false);
sba.put(3, true);
sba.delete(2);
// 此时 mSize 立即变为 2，数组已经完成搬移
// 而 SparseArray.delete() 只是标记 DELETED，mSize 不变
 
// 差异二：get() 的默认返回值不同
SparseArray<Object> sa = new SparseArray<>();
Object obj = sa.get(999);          // 返回 null
 
SparseBooleanArray sba2 = new SparseBooleanArray();
boolean b = sba2.get(999);         // 返回 false（boolean 的默认值）
 
SparseIntArray sia = new SparseIntArray();
int i = sia.get(999);              // 返回 0（int 的默认值）
 
SparseLongArray sla = new SparseLongArray();
long l = sla.get(999);             // 返回 0L（long 的默认值）
 
// 差异三：不支持泛型，因此没有类型擦除问题
// SparseArray<E> 的 values 是 Object[]，取出时需要强转
// 三个变体的 values 是原始类型数组，取出即用，类型安全且零开销
 
// 差异四：不实现 Map 接口（与 SparseArray 一致）
// 三者都不能直接传给需要 Map 参数的方法
// 如需转换，需手动遍历构建

SparseIntArray errorCounts = new SparseIntArray();
// 假设 moduleId=5 从未记录过错误
int count = errorCounts.get(5);  // 返回 0
 
// 问题：0 到底是"没有错误"还是"从未记录过"？
// 两种含义被混淆了！
 
// 解决方案一：使用 indexOfKey 先判断是否存在
int index = errorCounts.indexOfKey(5);
if (index >= 0) {
    // key 存在，取出真实值
    int realCount = errorCounts.valueAt(index);
} else {
    // key 不存在，做相应处理
}
 
// 解决方案二：使用一个不可能出现的默认值
int count2 = errorCounts.get(5, -1);  // 用 -1 表示"不存在"
if (count2 == -1) {
    // key 不存在
}

// ArrayMap 内部核心字段
int[] mHashes;      // 哈希数组：存储每个 key 的 hashCode，按升序排列
Object[] mArray;     // 键值对数组：交替存储 key 和 value，长度是 mHashes 的 2 倍
int mSize;           // 当前存储的键值对数量

mHashes (int[]):
┌─────────┬─────────┬─────────┐
│  index 0│  index 1│  index 2│
│ hash=97 │hash=3059│hash=3373│
│ ("age") │("city") │("name") │
└─────────┴─────────┴─────────┘
     │          │          │
     │          │          │        映射关系: mArray[index * 2] = key
     ▼          ▼          ▼                   mArray[index * 2 + 1] = value
mArray (Object[]):
┌───────┬───────┬───────┬──────────┬───────┬──────────┐
│  [0]  │  [1]  │  [2]  │   [3]    │  [4]  │   [5]    │
│ "age" │  25   │"city" │"Shanghai"│"name" │  "Kiro"  │
│  key  │ value │  key  │  value   │  key  │  value   │
└───────┴───────┴───────┴──────────┴───────┴──────────┘

// ArrayMap.put() 核心逻辑（简化版）
public V put(K key, V value) {
    final int osize = mSize;           // 记录当前大小
    final int hash;                     // 用于存储 key 的 hashCode
    int index;                          // 用于存储查找到的索引位置
 
    // ① 计算 hash 并查找插入位置
    if (key == null) {
        hash = 0;                       // null key 的 hash 固定为 0
        index = indexOfNull();          // 专门查找 null key 的位置
    } else {
        hash = key.hashCode();         // 计算 key 的 hashCode
        index = indexOf(key, hash);    // 二分查找 + 线性探测定位
    }
 
    // ② 如果 key 已存在（index >= 0），直接覆盖 value
    if (index >= 0) {
        // index * 2 + 1 就是 value 在 mArray 中的位置
        index = (index << 1) + 1;      // 等价于 index * 2 + 1，位运算更快
        V old = (V) mArray[index];     // 取出旧值用于返回
        mArray[index] = value;         // 覆盖为新值
        return old;                     // 返回旧值
    }
 
    // ③ key 不存在，index 取反得到应插入的位置
    index = ~index;                    // indexOf 返回的负数取反 = 插入点
 
    // ④ 容量不足时扩容
    if (osize >= mHashes.length) {
        // 扩容策略：<4 → 4，<8 → 8，否则 × 1.5
        final int n = osize >= 8 ? (osize + (osize >> 1))
                     : (osize >= 4 ? 8 : 4);
        allocArrays(n);                // 分配新数组（可能命中缓存）
    }
 
    // ⑤ 如果插入位置不在末尾，需要搬移后续元素腾出空间
    if (index < osize) {
        // 在 mHashes 中，把 index 及之后的元素后移一位
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        // 在 mArray 中，把 index*2 及之后的元素后移两位（key+value 一对）
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1,
                         (mSize - index) << 1);
    }
 
    // ⑥ 写入新的键值对
    mHashes[index] = hash;            // 在哈希数组的正确位置写入 hash
    mArray[index << 1] = key;         // 写入 key
    mArray[(index << 1) + 1] = value; // 写入 value
    mSize++;                           // 元素计数 +1
 
    return null;                       // 新插入返回 null
}

// ArrayMap.indexOf() 核心逻辑（简化版）
int indexOf(Object key, int hash) {
    final int N = mSize;
 
    // 空集合直接返回 ~0 = -1，表示应插入到位置 0
    if (N == 0) {
        return ~0;
    }
 
    // ① 二分查找：在 mHashes 中找到 hash 值的位置
    int index = binarySearch(mHashes, N, hash);
 
    // ② 没找到该 hash，返回负数（取反后为插入点）
    if (index < 0) {
        return index;
    }
 
    // ③ 找到了 hash，检查对应的 key 是否真的 equals
    if (key.equals(mArray[index << 1])) {
        return index;                  // 完美匹配，直接返回
    }
 
    // ④ hash 冲突处理：从 index 向后线性探测
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) {
            return end;                // 在后方找到匹配的 key
        }
    }
 
    // ⑤ 从 index 向前线性探测
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) {
            return i;                  // 在前方找到匹配的 key
        }
    }
 
    // ⑥ hash 存在但 key 不匹配 → 返回 end 的取反值作为新插入点
    // 这样新元素会插入到同 hash 值区段的末尾
    return ~end;
}

// HashMap.Node 的内存布局（64位 JVM，压缩指针开启）
static class Node<K,V> implements Map.Entry<K,V> {
    // 对象头:           12 bytes (mark word 8 + klass pointer 4)
    // padding:           4 bytes (对齐到 16 的倍数)
    int hash;          // 4 bytes
    K key;             // 4 bytes (压缩引用)
    V value;           // 4 bytes (压缩引用)
    Node<K,V> next;    // 4 bytes (压缩引用)
    // ─────────────────────────
    // 合计:             32 bytes（每个 Node 对象）
}

═══════════════════════════════════════════════════════════════
                    HashMap vs ArrayMap 内存对比 (100 entries)
═══════════════════════════════════════════════════════════════
 
HashMap:
  ┌─ Node[] table (容量128, loadFactor=0.75)
  │    → 128 × 4 bytes (引用)              =   512 bytes
  │
  ├─ 100 个 Node 对象
  │    → 100 × 32 bytes                    = 3,200 bytes
  │
  ├─ HashMap 对象自身                       ≈    48 bytes
  │
  └─ 总计                                  ≈ 3,760 bytes
     （不含 key/value 对象本身）
 
ArrayMap:
  ┌─ int[] mHashes (容量100)
  │    → 数组头 16 bytes + 100 × 4 bytes   =   416 bytes
  │
  ├─ Object[] mArray (容量200)
  │    → 数组头 16 bytes + 200 × 4 bytes   =   816 bytes
  │
  ├─ ArrayMap 对象自身                      ≈    48 bytes
  │
  └─ 总计                                  ≈ 1,280 bytes
     （不含 key/value 对象本身）
 
───────────────────────────────────────────────────────────────
  内存节省: 3,760 - 1,280 = 2,480 bytes ≈ 节省 66%
═══════════════════════════════════════════════════════════════

// ArrayMap 扩容策略（伪代码）
if (currentSize < 4) {
    newCapacity = 4;       // 最小容量为 4
} else if (currentSize < 8) {
    newCapacity = 8;       // 第二档为 8
} else {
    newCapacity = currentSize + (currentSize >> 1);  // 1.5 倍增长
}

操作频率对比（插入 + 删除 N 个元素）:
═══════════════════════════════════════════════
  HashMap:
    对象创建: N 次 new Node()
    对象销毁: N 个 Node 等待 GC
    GC 压力:  高
 
  ArrayMap:
    对象创建: 0 次（仅数组扩容时）
    对象销毁: 0 个中间对象
    GC 压力:  极低
═══════════════════════════════════════════════

int[] mHashes     — 存储 hash 值
Object[] mArray   — 存储 key-value 交替对（长度 = mHashes.length * 2）

// 发送端：创建 Bundle（内部就是 ArrayMap）
Bundle args = new Bundle();       // 分配 mHashes + mArray
args.putString("id", "123");
fragment.setArguments(args);
 
// 接收端：读取后 Bundle 被 GC 回收   // 释放 mHashes + mArray

// ---- ArrayMap.java 源码（简化） ----
 
// 缓存池 1：专门缓存 BASE_SIZE（4）容量的数组
static Object[] mBaseCache;       // 链表头指针
static int mBaseCacheSize;        // 当前缓存数量
 
// 缓存池 2：专门缓存 BASE_SIZE*2（8）容量的数组
static Object[] mTwiceBaseCache;  // 链表头指针
static int mTwiceBaseCacheSize;   // 当前缓存数量
 
static final int BASE_SIZE = 4;          // 基础容量
static final int CACHE_SIZE = 10;        // 每个池最多缓存 10 组

// array[0] = 指向下一组缓存的 Object[] （即 next 指针）
// array[1] = 与之配对的 int[] hashes
// array[2..n] = 无意义（已清空）

mBaseCache (静态变量，链表头)
    │
    ▼
┌──────────────────────────────┐
│  Object[] array_A  (size=8)  │    ← 最近一次回收的数组
│  [0] ──► 指向 array_B (next) │
│  [1] ──► int[] hashes_A      │
│  [2] = null                  │
│  ...                         │
│  [7] = null                  │
└──────────────────────────────┘
    │  array_A[0]
    ▼
┌──────────────────────────────┐
│  Object[] array_B  (size=8)  │    ← 更早回收的数组
│  [0] ──► 指向 array_C (next) │
│  [1] ──► int[] hashes_B      │
│  [2] = null                  │
│  ...                         │
└──────────────────────────────┘
    │  array_B[0]
    ▼
┌──────────────────────────────┐
│  Object[] array_C  (size=8)  │    ← 最早回收的数组
│  [0] = null  (链表尾)        │
│  [1] ──► int[] hashes_C      │
│  ...                         │
└──────────────────────────────┘

// ---- ArrayMap.java 源码（简化注释版） ----
private static void freeArrays(
        final int[] hashes,   // 要回收的 hash 数组
        final Object[] array, // 要回收的 key-value 数组
        final int size         // 当前实际存储的元素数量
) {
    // 判断是否属于可缓存的规格
    if (hashes.length == (BASE_SIZE * 2)) {
        // ---- 容量为 8 的数组，放入 mTwiceBaseCache 池 ----
        synchronized (ArrayMap.class) {
            // 池未满（最多缓存 CACHE_SIZE=10 组）才放入
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                // 把 array 变成链表节点：
                array[0] = mTwiceBaseCache;  // [0] 指向原来的链表头（next 指针）
                array[1] = hashes;           // [1] 保存配对的 hashes 数组
 
                // 清空 [2..n]，防止内存泄漏（断开对 key/value 的强引用）
                for (int i = (size << 1) - 1; i >= 2; i--) {
                    array[i] = null;         // 逐个清空旧数据
                }
 
                mTwiceBaseCache = array;     // 新节点成为链表头
                mTwiceBaseCacheSize++;        // 计数 +1
            }
        }
    } else if (hashes.length == BASE_SIZE) {
        // ---- 容量为 4 的数组，放入 mBaseCache 池 ----
        synchronized (ArrayMap.class) {
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mTwiceBaseCache;  // 同样的链表串联逻辑
                array[1] = hashes;
                for (int i = (size << 1) - 1; i >= 2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++;
            }
        }
    }
    // 其他容量的数组：不缓存，直接交给 GC
}

// ---- ArrayMap.java 源码（简化注释版） ----
private void allocArrays(final int size) {
    // ---- 尝试从容量 8 的缓存池取 ----
    if (size == (BASE_SIZE * 2)) {
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) {
                // 命中缓存！
                final Object[] array = mTwiceBaseCache;       // 取出链表头节点
                mArray = array;                                // 直接复用为 mArray
                mTwiceBaseCache = (Object[]) array[0];         // 链表头后移（摘除当前节点）
                mHashes = (int[]) array[1];                    // 取出配对的 hashes 数组
 
                // 清理链表指针槽位（它们的使命已完成）
                array[0] = null;
                array[1] = null;
 
                mTwiceBaseCacheSize--;                         // 计数 -1
                return;                                        // 复用成功，直接返回
            }
        }
    }
    // ---- 尝试从容量 4 的缓存池取 ----
    else if (size == BASE_SIZE) {
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[]) array[0];
                mHashes = (int[]) array[1];
                array[0] = null;
                array[1] = null;
                mBaseCacheSize--;
                return;
            }
        }
    }
 
    // ---- 缓存未命中，只能 new ----
    mHashes = new int[size];            // 新分配 hash 数组
    mArray = new Object[size << 1];     // 新分配 key-value 数组（长度 = size * 2）
}

// ===== 第一轮：首次创建，缓存池为空 =====
ArrayMap<String, String> map1 = new ArrayMap<>();
// 默认初始容量 = 0，put 时触发扩容到 BASE_SIZE(4)
map1.put("a", "1");
// allocArrays(4) → mBaseCache == null → new int[4] + new Object[8]
 
map1.put("b", "2");
map1.put("c", "3");
map1.put("d", "4");
// 容量 4 已满，再 put 触发扩容到 BASE_SIZE*2(8)
map1.put("e", "5");
// allocArrays(8) → mTwiceBaseCache == null → new int[8] + new Object[16]
// freeArrays(旧的 int[4], Object[8], 4) → 放入 mBaseCache 池
// 此时：mBaseCacheSize = 1, mTwiceBaseCacheSize = 0
 
// ===== 第二轮：map1 被清空 =====
map1.clear();
// freeArrays(int[8], Object[16], 5) → 放入 mTwiceBaseCache 池
// 此时：mBaseCacheSize = 1, mTwiceBaseCacheSize = 1
 
// ===== 第三轮：新建 map2，命中缓存 =====
ArrayMap<String, String> map2 = new ArrayMap<>(4);
// allocArrays(4) → mBaseCache != null → 命中！复用之前 map1 扩容时释放的 int[4] + Object[8]
// 此时：mBaseCacheSize = 0（被取走了）
 
ArrayMap<String, String> map3 = new ArrayMap<>(8);
// allocArrays(8) → mTwiceBaseCache != null → 命中！复用之前 map1.clear() 释放的 int[8] + Object[16]
// 此时：mTwiceBaseCacheSize = 0

时间线：
 
map1.put("a")     map1.put("e")       map1.clear()      new map2(4)     new map3(8)
     │                  │                   │                  │               │
     ▼                  ▼                   ▼                  ▼               ▼
 new int[4]      new int[8]           ┌─────────┐        ┌─────────┐    ┌─────────┐
 new Object[8]   new Object[16]       │ 回收8容量 │        │ 复用4容量 │    │ 复用8容量 │
                 回收旧4容量数组        │ 到Twice池 │        │ 从Base池  │    │ 从Twice池 │
                 到Base池              └─────────┘        └─────────┘    └─────────┘
                      │                     │                  │               │
                      ▼                     ▼                  ▼               ▼
              mBaseCacheSize=1    mTwiceCacheSize=1    mBaseCacheSize=0  mTwiceCacheSize=0

// 这个锁只保护缓存池的读写，不保护 ArrayMap 实例本身的操作
synchronized (ArrayMap.class) {   // 类锁，全局唯一
    // 操作 mBaseCache / mTwiceBaseCache
}

// ArrayMap.allocArrays() 触发前的容量计算逻辑（简化自 AOSP 源码）
// oSize 为当前数组容量（即扩容前的 mHashes.length）
final int newSize;
if (oSize >= (BASE_SIZE * 2)) {
    // 当前容量 >= 8 时，扩容为原来的 1.5 倍
    // oSize >> 1 等价于 oSize / 2，所以 oSize + oSize/2 = 1.5 * oSize
    newSize = oSize + (oSize >> 1);
} else if (oSize >= BASE_SIZE) {
    // 当前容量 >= 4 且 < 8 时，直接扩容到 8
    // BASE_SIZE * 2 = 8
    newSize = BASE_SIZE * 2;  // 即 8
} else {
    // 当前容量 < 4 时（包括初始容量为 0 的情况），直接扩容到 4
    newSize = BASE_SIZE;      // 即 4
}

// 扩容执行过程（简化）
public V put(K key, V value) {
    // ... 省略查找逻辑 ...
 
    if (mSize >= mHashes.length) {
        // 按上述规则计算 newCapacity
        final int newCapacity = calculateNewCapacity(mSize);
 
        // 保存旧数组引用
        final int[] oldHashes = mHashes;
        final Object[] oldArray = mArray;
 
        // 分配新数组（这里会优先尝试从缓存池取，上一节已讲）
        allocArrays(newCapacity);
 
        // 将旧数据拷贝到新数组
        if (oldHashes.length > 0) {
            // 拷贝 hash 数组：长度为 mSize（实际元素数）
            System.arraycopy(oldHashes, 0, mHashes, 0, mSize);
            // 拷贝 key-value 数组：长度为 mSize * 2（每个元素占两个槽位）
            System.arraycopy(oldArray, 0, mArray, 0, mSize << 1);
        }
 
        // 旧数组归还到缓存池（如果大小为 4 或 8）
        freeArrays(oldHashes, oldArray, mSize);
    }
 
    // ... 在正确位置插入新元素 ...
}

// remove() 中的收缩判断逻辑（简化自 AOSP 源码）
public V remove(Object key) {
    int index = indexOfKey(key);
    if (index >= 0) {
        return removeAt(index);
    }
    return null;
}
 
public V removeAt(int index) {
    final int oldSize = mSize;
    final int newSize = oldSize - 1;
 
    // 判断是否需要收缩
    if (mHashes.length > (BASE_SIZE * 2)  // 当前容量 > 8
            && oldSize < mHashes.length / 3) {  // 元素数量不足容量的 1/3
        // 需要收缩！
        // 新容量 = 当前元素数量的 1.5 倍（留一些余量避免频繁扩缩）
        final int newCapacity = oldSize > (BASE_SIZE * 2)
                ? (oldSize + (oldSize >> 1))  // > 8 则取 1.5 倍
                : (BASE_SIZE * 2);            // 否则收缩到 8
 
        // 分配新的更小的数组
        final int[] oldHashes = mHashes;
        final Object[] oldArray = mArray;
        allocArrays(newCapacity);
 
        // 拷贝 index 之前的元素
        if (index > 0) {
            System.arraycopy(oldHashes, 0, mHashes, 0, index);
            System.arraycopy(oldArray, 0, mArray, 0, index << 1);
        }
        // 拷贝 index 之后的元素（跳过被删除的那个）
        if (index < newSize) {
            System.arraycopy(oldHashes, index + 1,
                    mHashes, index, newSize - index);
            System.arraycopy(oldArray, (index + 1) << 1,
                    mArray, index << 1, (newSize - index) << 1);
        }
 
        // 旧数组归还缓存池
        freeArrays(oldHashes, oldArray, oldSize);
    } else {
        // 不需要收缩，只做元素移动
        if (index < newSize) {
            System.arraycopy(mHashes, index + 1,
                    mHashes, index, newSize - index);
            System.arraycopy(mArray, (index + 1) << 1,
                    mArray, index << 1, (newSize - index) << 1);
        }
        // 清空末尾槽位，帮助 GC
        mArray[newSize << 1] = null;      // key 置 null
        mArray[(newSize << 1) + 1] = null; // value 置 null
    }
 
    mSize = newSize;
    return (V) oldValue;
}

// 模拟 ArrayMap 的扩缩生命周期
ArrayMap<Integer, String> map = new ArrayMap<>();
 
// === 扩容阶段 ===
// 连续插入 20 个元素
for (int i = 0; i < 20; i++) {
    map.put(i, "val_" + i);
}
// 容量变化: 0 → 4 → 8 → 12 → 18 → 27
// 最终: mSize=20, capacity=27
 
// === 收缩阶段 ===
// 删除 15 个元素，只剩 5 个
for (int i = 0; i < 15; i++) {
    map.remove(i);
}
// 当 mSize 降到 8 时: 8 < 27/3(=9)? → YES → 触发收缩
// 新容量: 8 + 8/2 = 12? 不对，8 > 8 为 false，所以新容量 = 8
// 收缩后: mSize=5, capacity=8

// 震荡防护示意
// 假设当前: capacity=27, mSize=9
// 删除 1 个元素: mSize=8, 8 < 27/3=9 → 触发收缩
// 收缩后: capacity=8(因为 8 <= 8), mSize=8
// 此时数组刚好满载
 
// 如果再 put 1 个: mSize=9 > capacity=8 → 触发扩容
// 扩容后: capacity=12(因为 8 >= BASE_SIZE*2, 所以 8+8/2=12)
// 现在: capacity=12, mSize=9
 
// 如果再 remove 1 个: mSize=8, 8 < 12/3=4? → NO → 不收缩
// 稳定了！不会再震荡

// HashMap 的内部结构
// 1. HashMap 对象本身: 约 48 bytes (对象头 + 字段)
// 2. Node[] table 数组: 默认容量 16，负载因子 0.75
//    实际容量 = 大于 N/0.75 的最小 2 的幂
//    数组本身: 16 + capacity * 4 bytes (压缩指针)
// 3. 每个 Node 对象: 32 bytes
//    - 对象头: 12 bytes
//    - int hash: 4 bytes
//    - Object key: 4 bytes (压缩指针)
//    - Object value: 4 bytes (压缩指针)
//    - Node next: 4 bytes (压缩指针)
//    - 对齐填充: 4 bytes
// 4. 每个 Integer key (自动装箱): 16 bytes
//    - 对象头: 12 bytes
//    - int value: 4 bytes
 
// 存储 N=10 个元素:
// table 容量 = 16 (大于 10/0.75=13.3 的最小 2 的幂)
// 总内存 ≈ 48 + (16 + 16*4) + 10*(32 + 16) = 48 + 80 + 480 = 608 bytes

// ArrayMap 的内部结构
// 1. ArrayMap 对象本身: 约 36 bytes
// 2. int[] mHashes 数组: 16 + capacity * 4 bytes
// 3. Object[] mArray 数组: 16 + capacity * 2 * 4 bytes (压缩指针)
// 4. 没有 Node 包装对象！key 和 value 直接存在 mArray 中
// 5. Integer key 仍然需要装箱: 16 bytes each
//    (但如果 key 是 int 且用 SparseArray，连这个都省了)
 
// 存储 N=10 个元素 (假设容量刚好为 12，经过 4→8→12 扩容):
// 总内存 ≈ 36 + (16 + 12*4) + (16 + 24*4) + 10*16
//        = 36 + 64 + 112 + 160 = 372 bytes

// 查找性能对比
// HashMap: O(1) 平均时间复杂度
//   hash → bucket index → 链表/红黑树遍历
//   最坏情况 O(log n)（红黑树）
 
// ArrayMap: O(log n) 二分查找
//   hash → binarySearch(mHashes) → 找到 index → mArray[index*2] 取 key
//   即使 hash 命中，还可能需要线性探测处理 hash 冲突

// 插入性能对比
// HashMap: O(1) 平均
//   计算 hash → 定位桶 → 头插/尾插
//   扩容时 O(n) rehash，但均摊后仍为 O(1)
 
// ArrayMap: O(n) 最坏情况
//   二分查找插入位置: O(log n)
//   System.arraycopy 移动后续元素: O(n)
//   这是数组结构的固有缺陷——中间插入必须移动元素

// 删除性能对比
// HashMap: O(1) 平均
//   定位桶 → 从链表/红黑树中移除节点
 
// ArrayMap: O(n) 最坏情况
//   二分查找定位: O(log n)
//   System.arraycopy 移动后续元素: O(n)
//   可能触发收缩: 额外的数组拷贝

// HashMap 存储 100 个元素产生的对象数量:
// 1 个 HashMap 对象
// 1 个 Node[] 数组对象
// 100 个 Node 对象
// 100 个 Integer 对象 (key 装箱)
// 总计: 202 个对象
 
// ArrayMap 存储 100 个元素产生的对象数量:
// 1 个 ArrayMap 对象
// 1 个 int[] 数组对象
// 1 个 Object[] 数组对象
// 100 个 Integer 对象 (key 装箱)
// 总计: 103 个对象
 
// 对象数量减少了约 49%！
// 如果 key 是 int 且改用 SparseArray，还能再省掉 100 个 Integer 对象

// 不同数据量下 ArrayMap vs HashMap 的性能表现（示意）
// 数据来源: Android 官方性能测试 & 社区 benchmark
 
// N = 100:
//   ArrayMap.get()  ≈ HashMap.get()   (差距在纳秒级，可忽略)
//   ArrayMap.put()  略慢于 HashMap    (arraycopy 开销很小)
//   内存节省: ~40%
 
// N = 1000:
//   ArrayMap.get()  比 HashMap 慢 ~2-3x  (10次比较 vs 1次hash)
//   ArrayMap.put()  比 HashMap 慢 ~5-10x (arraycopy 开始明显)
//   内存节省: ~30-40%
 
// N = 10000:
//   ArrayMap.get()  比 HashMap 慢 ~5-10x
//   ArrayMap.put()  比 HashMap 慢 ~50-100x (arraycopy 成为瓶颈)
//   内存节省: ~30%，但性能代价太大

// 场景 1: Bundle 的底层实现
// Android 的 Bundle 内部就使用了 ArrayMap
// Bundle 通常用于 Activity/Fragment 间传递少量参数
// 传递的参数通常不超过几十个，完美匹配 ArrayMap 的设计
Bundle args = new Bundle();
args.putString("user_name", "Kiro");
args.putInt("user_age", 25);
// Bundle 内部调用的就是 ArrayMap.put()
 
// 场景 2: Intent 的 extras
// Intent 传递数据同样基于 Bundle → ArrayMap
Intent intent = new Intent(this, DetailActivity.class);
intent.putExtra("item_id", 1001);       // 通常只有几个 extra
intent.putExtra("item_title", "Hello");
 
// 场景 3: Fragment 的 arguments
// Google 官方推荐用 Bundle 传参，而非构造函数
public static MyFragment newInstance(int id) {
    MyFragment fragment = new MyFragment();
    Bundle args = new Bundle();  // ArrayMap 支撑
    args.putInt("id", id);
    fragment.setArguments(args);
    return fragment;
}

// 场景 4: SharedPreferences 的内存缓存
// SharedPreferencesImpl 内部使用 ArrayMap 缓存所有键值对
// 一个 SP 文件通常存储几十到几百个配置项，非常适合 ArrayMap
SharedPreferences prefs = getSharedPreferences("config", MODE_PRIVATE);
// 底层读取 XML 后，数据存入 ArrayMap
 
// 场景 5: ViewHolder 的临时数据映射
// RecyclerView 的 Adapter 中，经常需要为每个 item 维护少量状态
ArrayMap<String, Object> itemState = new ArrayMap<>();
itemState.put("expanded", false);    // 是否展开
itemState.put("selected", true);     // 是否选中
itemState.put("progress", 0.75f);    // 下载进度
// 每个 item 最多几个状态，ArrayMap 完美胜任
 
// 场景 6: 自定义 View 的属性缓存
// 自定义 View 解析 XML 属性后，缓存到 Map 中
// 属性数量通常在个位数到几十个之间
ArrayMap<String, Integer> attrCache = new ArrayMap<>();
attrCache.put("cornerRadius", 8);
attrCache.put("strokeWidth", 2);
attrCache.put("shadowElevation", 4);

// 场景 7: Android Framework 内部的大量使用
// ActivityManagerService 中管理 Activity 的各种映射
// WindowManagerService 中管理窗口属性
// PackageManagerService 中管理权限映射
// 这些场景的共同特点：
//   - 映射关系数量有限（通常远小于 1000）
//   - 系统服务对内存极度敏感
//   - 需要频繁遍历（ArrayMap 遍历性能优于 HashMap）

// ❌ 反面场景 1: 大数据量的缓存
// 图片 URL → Bitmap 的映射，可能有上万条
// 应该使用 HashMap 或 LruCache（内部也是 LinkedHashMap）
HashMap<String, Bitmap> imageCache = new HashMap<>(256);
 
// ❌ 反面场景 2: 高频写入的日志收集
// 每秒可能有数百次 put 操作
// ArrayMap 的 arraycopy 开销会成为性能瓶颈
HashMap<Long, LogEntry> logBuffer = new HashMap<>();
 
// ❌ 反面场景 3: 需要线程安全的并发场景
// ArrayMap 不是线程安全的，且没有 ConcurrentArrayMap 这种东西
// 应该使用 ConcurrentHashMap
ConcurrentHashMap<String, Session> sessions = new ConcurrentHashMap<>();
 
// ❌ 反面场景 4: 非 Android 平台
// ArrayMap 是 android.util 包下的类，标准 Java 中不存在
// AndroidX 提供了 androidx.collection.ArrayMap，但在服务端没有使用的必要