Android 常用数据结构原理与性能分析

1.3 扩容机制

当我们使用 ArrayList 的无参构造的时候：

ArrayList<Integer> arrayList = new ArrayList<>();

从构造方法中可以看出，无参构造方法构造 ArrayList 的时候，初始化的 ArrayList 的大小为 0。那什么时候初始化 ArrayList 大小的呢？看一下 add 方法：

/**
 * Appends the specified element to the end of this list.
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the number of elements specified.
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    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;
}

在每次调用 add 方法向 ArrayList 内添加元素时候，容器都会调用 ensureCapacityInternal 方法确保此时容量可以容纳这个元素，如果不能容下，则去扩容。如果此时容量为 0，则扩容到 10。如果此时容量不是 0，扩容为当前容量的 1.5 倍，同时我们知道了它的极限容量是 2147483647。确定好扩容的容量以后具体是如何实现扩容呢？

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

由此可知扩容时，容器重新创建了一个数组，容量为当前计算出来的容量，然后调用 JDK 底层的 C++ 代码完成批量数组复制操作。

1.4 性能特性

• 随机访问快：底层是数组，get/set 时间复杂度 O(1)。
• 插入/删除慢：插入/删除时需要移动元素，时间复杂度 O(n)。
• 扩容有开销：扩容时需要分配新数组并复制数据，性能有波动。
• ArrayList 不是线程安全的。多线程环境下需外部加锁或使用线程安全的集合（如 CopyOnWriteArrayList）。

针对 ArrayList 删除/插入慢的特性，就有了 LinkedList 的出现，接下来我们看一下 LinkedList 的实现。

2. LinkedList

LinkedList 基于双向链表实现，适合插入/删除频繁的场景，支持队列和栈操作，但随机访问性能较差，空间开销大。理解其实现原理有助于在实际开发中合理选择和使用。

• LinkedList 是一个继承于 AbstractSequentialList 的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，能对它进行队列操作。
• LinkedList 实现 Deque 接口，即能将 LinkedList 当作双端队列使用。
• LinkedList 实现了 Cloneable 接口，即覆盖了函数 clone()，能克隆。
• LinkedList 实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。
• LinkedList 是非同步的。

为什么要继承自 AbstractSequentialList？AbstractSequentialList 实现了 get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index) 这些骨干性函数。降低了 List 接口的复杂度。

此外，我们若需要通过 AbstractSequentialList 自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。

2.1 数据结构

LinkedList 是基于双向链表实现的，是双向链表但不是双向循环链表。其核心数据结构如下：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

• 每个 Node 节点包含数据（item）、前驱（prev）、后继（next）指针。
• first 指向链表头节点，last 指向链表尾节点。
• size 记录链表元素个数。

LinkedList 底层的数据结构是基于双向链表的。

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息。

2.2 构造方法

• LinkedList()：创建一个空链表。
• LinkedList(Collection<? extends E> c)：用集合初始化链表，依次添加元素。

/**
 * Constructs an empty list.
 */
public LinkedList() { }

/**
 * Constructs a list containing the elements of the specified collection.
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.3 核心操作

2.3.1 添加操作

• add(E e)：默认在链表尾部添加元素，调用 linkLast(e)。
• addFirst(E e) / addLast(E e)：分别在头部/尾部插入。
• add(int index, E element)：在指定位置插入，内部会定位到 index 处节点，然后插入。

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

/**
 * Inserts the specified element at the beginning of this list.
 */
public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

/**
 * Appends the specified element to the end of this list.
 */
public void addLast(E e) {
    linkLast(e);
}

2.3.2 删除元素

• remove() / removeFirst() / removeLast()：删除头/尾节点。
• remove(Object o)：遍历查找并删除第一个匹配元素。
• remove(int index)：定位到 index 处节点并删除。

/**
 * Removes and returns the first element from this list.
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null;
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

2.4 性能特征

• 插入/删除效率高：O(1)（已知节点时），在任意位置插入/删除只需修改指针。
• 随机访问慢：O(n)，需遍历链表定位节点。
• 空间开销大：每个元素需额外存储前后指针。
• LinkedList 是线程不安全的，多线程环境需外部加锁或使用并发集合。

到这里我们是不是就思考有没有删除/添加快、查找也快的数据结构呢？那就要看 HashMap 的了。

3. HashMap

3.1 数据结构

从数据结构的角度来看：HashMap 是：数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）的数据结构。

3.1.1 核心成员

// 默认初始容量 (数组默认大小):16，2 的整数次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，装载因子用来衡量 HashMap 满的程度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树边界
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转离链表边界
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希桶数组
transient Node<K,V>[] table;
// 实际存储的元素个数
transient int size;
// 当 map 里面的数据大于这个 threshold 就会进行扩容
int threshold = table.length * loadFactor

3.1.2 Node 数组

/**
 * Basic hash bin node, used for most entries.
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    public final K getKey() { return key; }
    public final V getValue() { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
    public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; }
    public final boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true;
        }
        return false;
    }
}

Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，本质就是就是一个映射 (键值对)。

3.2 数据存储

3.2.1 哈希表来存储

HashMap 采用哈希表来存储数据。哈希表是根据关键码值 (Key value) 而直接进行访问的数据结构。

3.2.2 哈希函数

• put/get/remove 等操作，首先对 key 计算 hash 值。
• 通过 hash & (table.length - 1) 定位到桶数组的下标。
• 在该桶链表/树中查找目标 key。

// 添加操作
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 计算 hash 值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对 key 进行了 hashCode 运算，得到一个 32 位的 int 值 h，然后用 h 异或 h>>>16 位。在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的。(h = k.hashCode()) ^ (h >>> 16)。

这样做的好处是，可以将 hashcode 高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。

等于说计算下标时把 hash 的高 16 位也参与进来了，掺杂的元素多了，那么生成的 hash 值的随机性会增大，减少了 hash 碰撞。

备注：

• ^ 异或：不同为 1，相同为 0

• ：无符号右移：右边补 0

• & 运算：两位同时为'1'，结果才为'1，否则为 0

h & (table.length -1) 来得到该对象的保存位，而 HashMap 底层数组的长度总是 2 的 n 次方。

为什么槽位数必须使用 2^n？

1. 为了让哈希后的结果更加均匀
2. 等价于 length 取模

当 length 总是 2 的 n 次方时，h & (length-1) 运算等价于对 length 取模，也就是 h % length，但是 & 比 % 具有更高的效率。

最终目的还是为了让哈希后的结果更均匀的分布，减少哈希碰撞，提升 hashmap 的运行效率。

分析 HashMap 的 put 方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    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] = newNode(hash, key, value, null);
    else {
        Node<K,V> e;
        K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap 的 put 方法执行过程整体如下：

1. 判断键值对数组 table[i] 是否为空或为 null，否则执行 resize() 进行扩容；
2. 根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加；
3. 判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value；
4. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对；
5. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；
6. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

3.3 HashMap 总结

HashMap 底层结构？

基于 Map 接口的实现，数组 + 链表的结构，JDK 1.8 后加入了红黑树，链表长度>8 变红黑树，<6 变链表。

两个对象的 hashcode 相同会发生什么？

Hash 冲突，HashMap 通过链表来解决 hash 冲突。

HashMap 中 equals() 和 hashCode() 有什么作用？

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 (n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

HashMap 何时扩容？

put 的元素达到容量乘负载因子的时候，默认 16*0.75。

hash 的实现？

h = key.hashCode()) ^ (h >>> 16)，hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。

HashMap 线程安全吗？

HashMap 读写效率较高，但是因为其是非同步的，即读写等操作都是没有锁保护的，所以在多线程场景下是不安全的，容易出现数据不一致的问题，在单线程场景下非常推荐使用。

HashMap 采用的是空间换时间的方式，这样就会有大量的空间浪费，那么有没有增删改查都快，但是又不浪费空间的数据结构呢？那么 SparseArray 就应运而生。

4. SparseArray

SparseArray 采用时间换取空间的方式来提高手机 App 的运行效率，这也是其与 HashMap 的区别；HashMap 通过空间换取时间，查找迅速；HashMap 中当 table 数组中内容达到总容量 0.75 时，则扩展为当前容量的两倍。

• SparseArray 的 key 为 int，value 为 Object。
• 在 Android 中，数据长度小于千时，用于替换 HashMap。
• 相比于 HashMap，其采用 时间换空间 的方式，使用更少的内存来提高手机 APP 的运行效率。

4.1 数据结构

• 用两个数组存储数据：mKeys（int[]）保存所有 key，mValues（Object[]）保存所有 value。
• mSize 记录当前有效元素数量。

private int[] mKeys;
private Object[] mValues;
private int mSize;

4.2 构造方法

/**
 * Creates a new SparseArray containing no mappings.
 */
public SparseArray() {
    this(10);
}

/**
 * Creates a new SparseArray containing no mappings that will not require any additional memory allocation.
 */
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

SparseArray 构造方法中，创建了两个数组 mKeys、mValues 分别存放 int 与 Object，其默认长度为 10。

4.3 操作核心

4.3.1 put(int key, E value)

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        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++;
    }
}

• 因为 key 为 int，不存在 hash 冲突。
• mKeys 为有序列表，通过二分查找，找到要插入的 key 对应 mKeys 数组中的 index。
• 通过 key 对应 mKeys 数组中的 index，将 Value 插入到 mValues 数组的 index 对应位置。

插入数据过程中：

1. 如果 mValues 数组 index 位置的数据已经删除，则直接插入；
2. 如果 mValues 数组 index 位置存在有效数据，或者数组长度不足了，则需要查看 GrowingArrayUtils.insert 代码了。

package com.android.internal.util;

public final class GrowingArrayUtils {
    public static int[] insert(int[] array, int currentSize, int index, int element) {
        assert currentSize <= array.length;
        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
        int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }
}

• 如果 mValues 数组 index 位置存在有效数据，而且数组长度够。则将 mValues 数组 index 位置后的元素都向后移动一位，index 位置存入对应的 element。
• 如果长度不够，则扩容到原长度的两倍，并将其他数据复制到新数组中。

4.3.2 get(int key)

public E get(int key) {
    return get(key, null);
}

@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

每次调用 get，则需经过一次 mKeys 数组的二分查找，因此 mKeys 数组越大则二分查找的时间就越长，因此 SparseArray 在大量数据，千以上时，会效率较低。

4.3.3 ContainerHelpers.binarySearch(mKeys, mSize, key) 二分查找

package android.util;
class ContainerHelpers {
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return ~lo;
    }
}

通过二分查找（ContainerHelpers.binarySearch）在 mKeys 中定位 key 的索引，查找速度为 O(logN)。

4.4 性能特征

1. 插入与删除：插入时，先查找 key 是否存在。存在则直接更新 value，不存在则插入新 key/value。删除时，不立即移除元素，而是将对应的 value 标记为 DELETED，并设置 mGarbage = true。
2. 延迟垃圾回收：删除后不会立刻移动数组，而是等到数组扩容或访问 size/keyAt/valueAt 时，才通过 gc() 方法一次性清理所有被标记为 DELETED 的项，提升性能。
3. 空间效率：由于 key 是 int 类型，避免了 HashMap 的装箱（auto-boxing）和额外的 Entry 对象，节省内存。适合 key 分布稀疏、元素数量不大的场景。
4. 有序性：mKeys 始终保持升序，遍历时 key/value 顺序一致。

SparseArray 通过有序数组和延迟垃圾回收机制，在小规模稀疏映射场景下比 HashMap 更节省内存，但插入/删除/查找的性能略低于 HashMap（O(logN) vs O(1)）。

SparseArray 整体来说对于千内的数据量是比较高效的，但是 SparseArray 有个问题就是 key 必须是 int，这就有了局限性。那么为了解决这个问题 ArrayMap 就应运而生。

5. ArrayMap

ArrayMap 是 Android 平台为内存优化而设计的轻量级 Map 实现，主要用于 key/value 数量较少的场景。ArrayMap 和 SparseArray 有点类似；其中含有两个数组，一个是 mHashes（key 的 hash 值数组，为一个有序数组），另一个数组存储的是 key 和 value，其中 key 和 value 是成对出现的，key 存储在数组的偶数位上，value 存储在数组的奇数位上。

5.1 数据结构

ArrayMap 通过两个数组实现存储：

• mHashes：int[]，存储每个 key 的 hashCode，始终有序。
• mArray：Object[]，交替存储 key 和 value（即 [key0, value0, key1, value1, ...]）。
• mSize：当前实际存储的键值对数量。

这样做的好处就是它避免了为每个加入到 map 的实体构造额外的对象。在 ArrayMap 大小增长的时候，我们也只需要复制两个数组的实体，而不需要重新构建一个 hash map。

我们需要注意的是这种数据结构不适合包含大量数据项的数据结构，因为它内部使用的是数组，对数组进行插入和删除操作效率比较低。

5.2 构造方法

/**
 * Create a new empty ArrayMap.
 */
public ArrayMap() {
    this(0, false);
}

/**
 * Create a new ArrayMap with a given initial capacity.
 */
public ArrayMap(int capacity) {
    this(capacity, false);
}

public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;
    if (capacity < 0) {
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        allocArrays(capacity);
    }
    mSize = 0;
}

可以看到，这里就是对这两个数组以及这个 size 进行初始化，它定义了两个空数组，并且把大小置为 0。从上面可以看到，它并没有为数组分配空间，在要使用的时候才会分配空间，这也是 ArrayMap 比 HashMap 内存占用率低的一个原因。

5.3 核心操作

5.3.1 put(K key, V value)

@Override
public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        index = indexOf(key, hash);
    }
    
    if (index >= 0) {
        index = (index<<1) + 1;
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }
    
    index = ~index;
    
    if (osize >= mHashes.length) {
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        allocArrays(n);
        if (mHashes.length > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
        freeArrays(ohashes, oarray, osize);
    }
    
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }
    
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;
}

从上面的代码分析，插入操作最重要的是获取到了 index，index 决定了后续的操作，所以 index 的获取就比较重要，分析一下 index 的获取实现。

int indexOf(Object key, int hash) {
    final int N = mSize;
    if (N == 0) {
        return ~0;
    }
    int index = binarySearchHashes(mHashes, N, hash);
    if (index < 0) {
        return index;
    }
    if (key.equals(mArray[index<<1])) {
        return index;
    }
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }
    return ~end;
}

查找 key 时，先用二分查找在 mHashes 中定位 hashCode。如果有 hash 冲突（即 hashCode 相同），则在 mArray 中顺序比对 key 的 equals。查找复杂度为 O(logN)（二分查找）+ O(k)（冲突时的线性查找，k 为冲突数）。

插入时，先查找 key 是否存在。

• 存在则直接覆盖 value。
• 不存在则插入新 key/value，并保持 mHashes 有序（需要移动数组元素）。

特别强调的一点是 mHashes 是一个 int 数组，用于存储每个 key 的 hashCode，并且始终保持升序排列。mHashes 中的 hash 值可能会有连续重复的值，原因如下：

• 如果插入的多个 key 对象的 hashCode 相同，那么 mHashes 中就会出现连续的相同 hash 值。
• ArrayMap 的查找逻辑是先用二分查找定位 hashCode，再在冲突区间内用 equals 线性查找 key。

5.3.2 get(Object key)

@Override
public V get(Object key) {
    final int index = indexOfKey(key);
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

public int indexOfKey(Object key) {
    return key == null ? indexOfNull() : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

5.4 特性特征

1. 内存优化：
   • ArrayMap 通过静态缓存池（如 BASE_SIZE、CACHED_HASHES、CACHED_ARRAYS）复用小数组，减少频繁分配和回收内存的开销。
   • 由于采用数组存储，避免了 HashMap 的 Entry 对象和装箱操作，极大节省内存。
2. 扩容与收缩：
   • 当容量不足时，ArrayMap 会扩容为当前容量的 1.5 倍（growSize）。
   • 删除大量元素后，若剩余元素很少，会自动收缩数组以节省内存。
3. 有序性：
   • mHashes 始终有序，遍历时 key/value 顺序与插入顺序无关，而是按 hashCode 升序。
4. 适用场景：
   • 适合 key/value 数量较少（几十以内）、对内存敏感的场景。
   • 大量数据时，插入/删除/查找性能不如 HashMap。