Android 性能为王时代SparseArray和HashMap一争高下

SparseArray 是 Android 中一种高效的数据结构，用于将整数键映射到对象。它与 HashMap 类似，但为了节省内存，使用两个并行数组来存储键和值，并采用二分搜索进行查找。以下是对 SparseArray 源码的详细分析。

一、SparseArray 源码分析

1. 类定义和构造函数

SparseArray 是一个泛型类，继承自 Object。

public class SparseArray<E> 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 < 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++;}
}

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 (i < 0 || mValues[i] == DELETED) {return valueIfKeyNotFound;} else {return (E) mValues[i];}
}

2.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; i < n; i++) {Object val = values[i];if (val != DELETED) {if (i != o) {keys[o] = keys[i];values[o] = val;values[i] = null;}o++;}}mGarbage = false;mSize = o;
}

2.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 <= 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; // value found}}return ~lo;  // value not present
}

二、使用示例

以下是SparseArray的简单使用示例：

SparseArray<String> 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.size(); i++) {int key = sparseArray.keyAt(i);String val = sparseArray.valueAt(i);Log.d("SparseArray", "Key: " + key + ", Value: " + val);
}

通过这种方式，我们可以高效地管理键为整数的键值对，特别适用于性能敏感的应用场景。

继续深入分析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 <= 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; // 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> 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 <= 4 ? 8 : currentSize * 2;}
}

该类提供了向数组中插入元素的方法，如果数组已满，则会扩展数组容量。growSize 方法根据当前大小决定扩展大小。

四、优缺点

4.1 优点

1. 内存效率高：SparseArray 使用并行数组，避免了 HashMap 中对象封装导致的内存开销，特别适合键是整数的情况。
2. 高效查找：通过二分查找在键数组中定位元素，查找时间复杂度为 O(log N)。
3. 自动扩展：GrowingArrayUtils 确保数组在需要时自动扩展，减少手动管理数组大小的麻烦。
4. 避免自动装箱：与 HashMap<Integer, Object> 不同，SparseArray 直接使用 int 类型键，避免了自动装箱的开销。

4.2 缺点

1. 不适合频繁删除操作：删除操作只是将值标记为 “已删除”，需要额外的垃圾回收步骤，这可能影响性能。
2. 键必须是整数：只能用于整数键的情况，不够通用。
3. 固定容量扩展：数组扩展是按固定策略进行的（当前大小的倍数扩展），在某些极端情况下可能导致不必要的内存浪费。

五、使用场景

5.1 适用场景

1. 大量键值对：适用于需要存储大量键值对且键为整数的场景，如缓存、映射关系等。
2. 高性能要求：适合内存敏感的应用，如低端设备上的应用、实时应用等。
3. 稀疏数据集：特别适用于键值对稀疏分布的场景。

5.2 不适用场景

1. 频繁插入删除：如果应用需要频繁插入和删除操作，SparseArray 的性能可能不如 HashMap。
2. 非整数键：如果键不是整数，SparseArray 无法使用。

六、实际使用示例

下面是一个实际应用场景中的示例，用于存储和查找用户会话数据：

public class SessionManager {private SparseArray<Session> sessionSparseArray;public SessionManager() {sessionSparseArray = new SparseArray<>();}public void addSession(int sessionId, Session session) {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 < sessionSparseArray.size(); i++) {int key = sessionSparseArray.keyAt(i);Session session = sessionSparseArray.get(key);if (session.isExpired()) {sessionSparseArray.removeAt(i);}}}
}class Session {private long creationTime;private long expiryTime;public Session(long creationTime, long expiryTime) {this.creationTime = creationTime;this.expiryTime = expiryTime;}public boolean isExpired() {return System.currentTimeMillis() > expiryTime;}
}

在这个示例中，SessionManager 使用 SparseArray 存储和管理用户会话。通过addSession、getSession、removeSession等方法，可以高效地管理会话数据。cleanUpSessions 方法演示了如何清理过期会话，同时展示了删除标记和垃圾回收机制。

七、总结

SparseArray 是 Android 提供的一个高效数据结构，用于整数键值对的存储和查找。它通过优化内存使用和查找性能，特别适合在性能敏感和内存有限的应用中使用。通过理解其实现原理和优缺点，可以在适当的场景中充分利用其优势。

SparseArray 是一种优化的稀疏数组，适用于键为整数的场景。它的实现通过两个并行数组和二分搜索来提高查找和存储的效率，避免了使用HashMap可能带来的内存开销。

• 存储：使用两个并行数组分别存储键和值。
• 查找：通过二分搜索快速定位键的位置。
• 垃圾回收：延迟删除机制，通过标记删除和垃圾回收减少数组重新分配次数。
• 性能优化：通过ViewHolder模式和减少对象分配，SparseArray 在大量数据操作时性能表现良好。

欢迎点赞|关注|收藏|评论，您的肯定是我创作的动力