行业知识
Android 性能为王时代SparseArray和HashMap一争高下
2026-10-30 20:08:31
来源：互联网转载
文章目录
- 一、`SparseArray` 源码分析
- 1. **类定义和构造函数**
- 2. **基本方法**
- 2.1 `put(int key, E value)`
- 2.2 `get(int key)`
- 2.3 `delete(int key)`
- 2.4 `removeAt(int index)`
- 2.5 `gc()`
- 2.6 `size()`
- 2.7 `keyAt(int index)` 和 `valueAt(int index)`
- 3. **辅助方法**
- 3.1 `binarySearch()`
- 二、使用示例
- 三、详细实现分析
- 3.1 `ContainerHelpers` 类
- 3.2 `GrowingArrayUtils` 类
- 四、优缺点
- 4.1 优点
- 4.2 缺点
- 五、使用场景
- 5.1 适用场景
- 5.2 不适用场景
- 六、实际使用示例
- 七、总结
SparseArray 是 Android 中一种高效的数据结构，用于将整数键映射到对象。它与 HashMap 类似，但为了节省内存，使用两个并行数组来存储键和值，并采用二分搜索进行查找。以下是对 SparseArray 源码的详细分析。
一、SparseArray 源码分析
1. 类定义和构造函数
SparseArray 是一个泛型类，继承自 Object。
public class SparseArray implements Cloneable { private static final Object DELETED = new Object(); private boolean mGarbage = false; private int[] mKeys; private Object[] mValues; private int mSize; public SparseArray() { this(10); // 默认初始容量为10 } public SparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { mKeys = new int[initialCapacity]; mValues = new Object[initialCapacity]; } mSize = 0; }}2. 基本方法
2.1 put(int key, E value)
将键值对插入 SparseArray 中。
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 = mKeys.length) { gc(); i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}2.2 get(int key)
通过键获取值，如果不存在则返回默认值 null。
public E get(int key) { return get(key, null);}public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i2.3 delete(int key)
删除键值对。
public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } }}2.4 removeAt(int index)
删除指定索引处的键值对。
public void removeAt(int index) { if (mValues[index] != DELETED) { mValues[index] = DELETED; mGarbage = true; }}2.5 gc()
垃圾回收，清理被标记删除的元素。
private void gc() { int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i2.6 size()
返回键值对的数量。
public int size() { if (mGarbage) { gc(); } return mSize;}2.7 keyAt(int index) 和 valueAt(int index)
通过索引获取键或值。
public int keyAt(int index) { if (mGarbage) { gc(); } return mKeys[index];}public E valueAt(int index) { if (mGarbage) { gc(); } return (E) mValues[index];}3. 辅助方法
3.1 binarySearch()
二分搜索，用于在有序数组中查找元素。
public static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo final int mid = (lo + hi) >> 1; final int midVal = array[mid]; if (midVal value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present}二、使用示例
以下是SparseArray的简单使用示例：
SparseArray sparseArray = new SparseArray();sparseArray.put(1, "One");sparseArray.put(2, "Two");sparseArray.put(3, "Three");// 获取值String value = sparseArray.get(2); // "Two"// 删除值sparseArray.delete(3);// 获取键和值for (int i = 0; i
通过这种方式，我们可以高效地管理键为整数的键值对，特别适用于性能敏感的应用场景。
继续深入分析SparseArray的实现细节，并探讨其优缺点和使用场景。
三、详细实现分析
3.1 ContainerHelpers 类
ContainerHelpers 提供了 SparseArray 使用的二分搜索功能。
public class ContainerHelpers { public static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo final int mid = (lo + hi) >> 1; final int midVal = array[mid]; if (midVal value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present }}该方法通过二分查找在一个有序整数数组中定位特定值的位置。如果找到匹配值，则返回其索引；否则返回插入点的反码（即 ~lo）。
3.2 GrowingArrayUtils 类
GrowingArrayUtils 用于在数组中插入元素并自动扩展数组容量。
public class GrowingArrayUtils { public static int[] insert(int[] array, int currentSize, int index, int element) { if (currentSize + 1 > array.length) { int[] newArray = new int[growSize(currentSize)]; System.arraycopy(array, 0, newArray, 0, index); newArray[index] = element; System.arraycopy(array, index, newArray, index + 1, currentSize - index); return newArray; } else { System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } } public static T[] insert(T[] array, int currentSize, int index, T element) { if (currentSize + 1 > array.length) { @SuppressWarnings("unchecked") T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), growSize(currentSize)); System.arraycopy(array, 0, newArray, 0, index); newArray[index] = element; System.arraycopy(array, index, newArray, index + 1, currentSize - index); return newArray; } else { System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } } private static int growSize(int currentSize) { return currentSize private SparseArray sessionSparseArray = new SparseArray sessionSparseArray.put(sessionId, session); } public Session getSession(int sessionId) { return sessionSparseArray.get(sessionId); } public void removeSession(int sessionId) { sessionSparseArray.delete(sessionId); } public int getSessionCount() { return sessionSparseArray.size(); } // 清理被标记删除的会话 public void cleanUpSessions() { for (int i = 0; i在这个示例中，SessionManager 使用 SparseArray 存储和管理用户会话。通过addSession、getSession、removeSession等方法，可以高效地管理会话数据。cleanUpSessions 方法演示了如何清理过期会话，同时展示了删除标记和垃圾回收机制。
七、总结
SparseArray 是 Android 提供的一个高效数据结构，用于整数键值对的存储和查找。它通过优化内存使用和查找性能，特别适合在性能敏感和内存有限的应用中使用。通过理解其实现原理和优缺点，可以在适当的场景中充分利用其优势。
SparseArray 是一种优化的稀疏数组，适用于键为整数的场景。它的实现通过两个并行数组和二分搜索来提高查找和存储的效率，避免了使用HashMap可能带来的内存开销。
- 存储：使用两个并行数组分别存储键和值。
- 查找：通过二分搜索快速定位键的位置。
- 垃圾回收：延迟删除机制，通过标记删除和垃圾回收减少数组重新分配次数。
- 性能优化：通过ViewHolder模式和减少对象分配，SparseArray 在大量数据操作时性能表现良好。
欢迎点赞|关注|收藏|评论，您的肯定是我创作的动力
上一篇：云服务器发放时间怎么算?
下一篇：记性不好怎么打灯光?
