跳到主要内容 Android 常用数据结构原理与性能分析 | 极客日志
Java 大前端 java 算法
Android 常用数据结构原理与性能分析 Android 开发中常用的五种数据结构：ArrayList、LinkedList、HashMap、SparseArray 和 ArrayMap。重点阐述了它们的底层实现原理（如动态数组、双向链表、哈希表 + 红黑树等）、扩容机制及时间复杂度特性。通过对比随机访问、插入删除效率及内存占用，提供了不同场景下的选型建议，帮助开发者优化应用性能。
樱花落尽 发布于 2026/3/22 更新于 2026/4/17 1. ArrayList 原理
ArrayList 是基于动态数组实现的，适合随机访问和顺序添加，扩容机制保证了动态增长，但插入和删除效率较低，且不是线程安全的。理解其实现原理有助于在实际开发中合理选择和使用。
1.1 数据结构
ArrayList 是基于动态数组实现的 List。其核心字段如下：
transient Object[] elementData;
private
int
elementData 是一个 Object 数组，存储所有元素。size 表示当前 ArrayList 中的有效元素数量。
1.2 构造方法
ArrayList()：默认初始容量为 0。ArrayList(int initialCapacity)：指定初始容量。ArrayList(Collection<? extends E> c)：用集合初始化。
private static final int DEFAULT_CAPACITY = 10 ;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList (int initialCapacity) {
if (initialCapacity > 0 ) {
this .elementData = new Object [initialCapacity];
} else if (initialCapacity == 0 ) {
this .elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException ("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList () {
this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList (Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0 ) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this .elementData = EMPTY_ELEMENTDATA;
}
}
1.3 扩容机制 当我们使用 ArrayList 的无参构造的时候：
ArrayList<Integer> arrayList = new ArrayList <>();
从构造方法中可以看出，无参构造方法构造 ArrayList 的时候，初始化的 ArrayList 的大小为 0。那什么时候初始化 ArrayList 大小的呢？看一下 add 方法：
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);
}
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)：用集合初始化链表，依次添加元素。
public LinkedList () { }
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 处节点，然后插入。
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++;
}
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++;
}
public void addLast (E e) {
linkLast(e);
}
2.3.2 删除元素
remove() / removeFirst() / removeLast()：删除头/尾节点。remove(Object o)：遍历查找并删除第一个匹配元素。remove(int index)：定位到 index 处节点并删除。
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 核心成员
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ;
static final int MAXIMUM_CAPACITY = 1 << 30 ;
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;
int threshold = table.length * loadFactor
3.1.2 Node 数组
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 );
}
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？
为了让哈希后的结果更加均匀
等价于 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 方法执行过程整体如下：
判断键值对数组 table[i] 是否为空或为 null，否则执行 resize() 进行扩容；
根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加；
判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value；
判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对；
遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；
插入成功后，判断实际存在的键值对数量 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 构造方法
public SparseArray () {
this (10 );
}
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 对应位置。
如果 mValues 数组 index 位置的数据已经删除，则直接插入；
如果 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 性能特征
插入与删除 ：插入时，先查找 key 是否存在。存在则直接更新 value，不存在则插入新 key/value。删除时，不立即移除元素，而是将对应的 value 标记为 DELETED，并设置 mGarbage = true。延迟垃圾回收 ：删除后不会立刻移动数组，而是等到数组扩容或访问 size/keyAt/valueAt 时，才通过 gc() 方法一次性清理所有被标记为 DELETED 的项，提升性能。空间效率 ：由于 key 是 int 类型，避免了 HashMap 的装箱（auto-boxing）和额外的 Entry 对象，节省内存。适合 key 分布稀疏、元素数量不大的场景。有序性 ：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 数据结构
mHashes：int[]，存储每个 key 的 hashCode，始终有序。
mArray：Object[]，交替存储 key 和 value（即 [key0, value0, key1, value1, ...]）。
mSize：当前实际存储的键值对数量。
这样做的好处就是它避免了为每个加入到 map 的实体构造额外的对象。在 ArrayMap 大小增长的时候，我们也只需要复制两个数组的实体，而不需要重新构建一个 hash map。
我们需要注意的是这种数据结构不适合包含大量数据项的数据结构，因为它内部使用的是数组，对数组进行插入和删除操作效率比较低。
5.2 构造方法
public ArrayMap () {
this (0 , false );
}
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 为冲突数）。
存在则直接覆盖 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 特性特征
内存优化 ：
ArrayMap 通过静态缓存池（如 BASE_SIZE、CACHED_HASHES、CACHED_ARRAYS）复用小数组，减少频繁分配和回收内存的开销。
由于采用数组存储，避免了 HashMap 的 Entry 对象和装箱操作，极大节省内存。
扩容与收缩 ：
当容量不足时，ArrayMap 会扩容为当前容量的 1.5 倍（growSize）。
删除大量元素后，若剩余元素很少，会自动收缩数组以节省内存。
有序性 ：
mHashes 始终有序，遍历时 key/value 顺序与插入顺序无关，而是按 hashCode 升序。
适用场景 ：
适合 key/value 数量较少（几十以内）、对内存敏感的场景。
大量数据时，插入/删除/查找性能不如 HashMap。
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
