Android 性能为王期间SparseArray和HashMap一争高下

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

1. 类定义和构造函数

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

1. public class SparseArray<E> implements Cloneable {
2.     private static final Object DELETED = new Object();
3.     private boolean mGarbage = false;
4.     private int[] mKeys;
5.     private Object[] mValues;
6.     private int mSize;
8.     public SparseArray() {
9.         this(10);  // 默认初始容量为10
10.     }
12.     public SparseArray(int initialCapacity) {
13.         if (initialCapacity == 0) {
14.             mKeys = EmptyArray.INT;
15.             mValues = EmptyArray.OBJECT;
16.         } else {
17.             mKeys = new int[initialCapacity];
18.             mValues = new Object[initialCapacity];
19.         }
20.         mSize = 0;
21.     }
22. }

复制代码

2. 基本方法

2.1 put(int key, E value)

将键值对插入 SparseArray 中。

1. public void put(int key, E value) {
2.     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
4.     if (i >= 0) {
5.         mValues[i] = value;
6.     } else {
7.         i = ~i;
9.         if (i < mSize && mValues[i] == DELETED) {
10.             mKeys[i] = key;
11.             mValues[i] = value;
12.             return;
13.         }
15.         if (mGarbage && mSize >= mKeys.length) {
16.             gc();
18.             i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
19.         }
21.         mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
22.         mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
23.         mSize++;
24.     }
25. }

复制代码

2.2 get(int key)

通过键获取值，如果不存在则返回默认值 null。

1. public E get(int key) {
2.     return get(key, null);
3. }
5. public E get(int key, E valueIfKeyNotFound) {
6.     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
8.     if (i < 0 || mValues[i] == DELETED) {
9.         return valueIfKeyNotFound;
10.     } else {
11.         return (E) mValues[i];
12.     }
13. }

复制代码

2.3 delete(int key)

删除键值对。

1. public void delete(int key) {
2.     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
4.     if (i >= 0) {
5.         if (mValues[i] != DELETED) {
6.             mValues[i] = DELETED;
7.             mGarbage = true;
8.         }
9.     }
10. }

复制代码

2.4 removeAt(int index)

删除指定索引处的键值对。

1. public void removeAt(int index) {
2.     if (mValues[index] != DELETED) {
3.         mValues[index] = DELETED;
4.         mGarbage = true;
5.     }
6. }

复制代码

2.5 gc()

垃圾回收，清理被标记删除的元素。

1. private void gc() {
2.     int n = mSize;
3.     int o = 0;
4.     int[] keys = mKeys;
5.     Object[] values = mValues;
7.     for (int i = 0; i < n; i++) {
8.         Object val = values[i];
10.         if (val != DELETED) {
11.             if (i != o) {
12.                 keys[o] = keys[i];
13.                 values[o] = val;
14.                 values[i] = null;
15.             }
17.             o++;
18.         }
19.     }
21.     mGarbage = false;
22.     mSize = o;
23. }

复制代码

2.6 size()

返回键值对的数目。

1. public int size() {
2.     if (mGarbage) {
3.         gc();
4.     }
5.     return mSize;
6. }

复制代码

2.7 keyAt(int index) 和 valueAt(int index)

通过索引获取键或值。

1. public int keyAt(int index) {
2.     if (mGarbage) {
3.         gc();
4.     }
5.     return mKeys[index];
6. }
8. public E valueAt(int index) {
9.     if (mGarbage) {
10.         gc();
11.     }
12.     return (E) mValues[index];
13. }

复制代码

3. 辅助方法

3.1 binarySearch()

二分搜索，用于在有序数组中查找元素。

1. public static int binarySearch(int[] array, int size, int value) {
2.     int lo = 0;
3.     int hi = size - 1;
5.     while (lo <= hi) {
6.         final int mid = (lo + hi) >>> 1;
7.         final int midVal = array[mid];
9.         if (midVal < value) {
10.             lo = mid + 1;
11.         } else if (midVal > value) {
12.             hi = mid - 1;
13.         } else {
14.             return mid; // value found
15.         }
16.     }
17.     return ~lo;  // value not present
18. }

复制代码

二、使用示例

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

1. SparseArray<String> sparseArray = new SparseArray<>();
2. sparseArray.put(1, "One");
3. sparseArray.put(2, "Two");
4. sparseArray.put(3, "Three");
6. // 获取值
7. String value = sparseArray.get(2); // "Two"
9. // 删除值
10. sparseArray.delete(3);
12. // 获取键和值
13. for (int i = 0; i < sparseArray.size(); i++) {
14.     int key = sparseArray.keyAt(i);
15.     String val = sparseArray.valueAt(i);
16.     Log.d("SparseArray", "Key: " + key + ", Value: " + val);
17. }

复制代码

通过这种方式，我们可以高效地管理键为整数的键值对，特殊适用于性能敏感的应用场景。
继续深入分析SparseArray的实现细节，并探讨其优缺点和使用场景。
三、详细实现分析

3.1 ContainerHelpers 类

ContainerHelpers 提供了 SparseArray 使用的二分搜索功能。

1. public class ContainerHelpers {
2.     public static int binarySearch(int[] array, int size, int value) {
3.         int lo = 0;
4.         int hi = size - 1;
6.         while (lo <= hi) {
7.             final int mid = (lo + hi) >>> 1;
8.             final int midVal = array[mid];
10.             if (midVal < value) {
11.                 lo = mid + 1;
12.             } else if (midVal > value) {
13.                 hi = mid - 1;
14.             } else {
15.                 return mid; // value found
16.             }
17.         }
18.         return ~lo;  // value not present
19.     }
20. }

复制代码

该方法通过二分查找在一个有序整数数组中定位特定值的位置。如果找到匹配值，则返回其索引；否则返回插入点的反码（即 ~lo）。
3.2 GrowingArrayUtils 类

GrowingArrayUtils 用于在数组中插入元素并自动扩展数组容量。

1. public class GrowingArrayUtils {
2.     public static int[] insert(int[] array, int currentSize, int index, int element) {
3.         if (currentSize + 1 > array.length) {
4.             int[] newArray = new int[growSize(currentSize)];
5.             System.arraycopy(array, 0, newArray, 0, index);
6.             newArray[index] = element;
7.             System.arraycopy(array, index, newArray, index + 1, currentSize - index);
8.             return newArray;
9.         } else {
10.             System.arraycopy(array, index, array, index + 1, currentSize - index);
11.             array[index] = element;
12.             return array;
13.         }
14.     }
16.     public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
17.         if (currentSize + 1 > array.length) {
18.             @SuppressWarnings("unchecked")
19.             T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), growSize(currentSize));
20.             System.arraycopy(array, 0, newArray, 0, index);
21.             newArray[index] = element;
22.             System.arraycopy(array, index, newArray, index + 1, currentSize - index);
23.             return newArray;
24.         } else {
25.             System.arraycopy(array, index, array, index + 1, currentSize - index);
26.             array[index] = element;
27.             return array;
28.         }
29.     }
31.     private static int growSize(int currentSize) {
32.         return currentSize <= 4 ? 8 : currentSize * 2;
33.     }
34. }

复制代码

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

4.1 优点

• 内存效率高：SparseArray 使用并行数组，避免了 HashMap 中对象封装导致的内存开销，特殊适合键是整数的环境。
  
• 高效查找：通过二分查找在键数组中定位元素，查找时间复杂度为 O(log N)。
  
• 自动扩展：GrowingArrayUtils 确保数组在需要时自动扩展，镌汰手动管理数组大小的贫苦。
  
• 避免自动装箱：与 HashMap<Integer, Object> 差别，SparseArray 直接使用 int 类型键，避免了自动装箱的开销。
  

4.2 缺点

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

五、使用场景

5.1 适用场景

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

5.2 不适用场景

• 频仍插入删除：如果应用需要频仍插入和删除操纵，SparseArray 的性能大概不如 HashMap。
  
• 非整数键：如果键不是整数，SparseArray 无法使用。
  

六、实际使用示例

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

1. public class SessionManager {
2.     private SparseArray<Session> sessionSparseArray;
4.     public SessionManager() {
5.         sessionSparseArray = new SparseArray<>();
6.     }
8.     public void addSession(int sessionId, Session session) {
9.         sessionSparseArray.put(sessionId, session);
10.     }
12.     public Session getSession(int sessionId) {
13.         return sessionSparseArray.get(sessionId);
14.     }
16.     public void removeSession(int sessionId) {
17.         sessionSparseArray.delete(sessionId);
18.     }
20.     public int getSessionCount() {
21.         return sessionSparseArray.size();
22.     }
24.     // 清理被标记删除的会话
25.     public void cleanUpSessions() {
26.         for (int i = 0; i < sessionSparseArray.size(); i++) {
27.             int key = sessionSparseArray.keyAt(i);
28.             Session session = sessionSparseArray.get(key);
29.             if (session.isExpired()) {
30.                 sessionSparseArray.removeAt(i);
31.             }
32.         }
33.     }
34. }
36. class Session {
37.     private long creationTime;
38.     private long expiryTime;
40.     public Session(long creationTime, long expiryTime) {
41.         this.creationTime = creationTime;
42.         this.expiryTime = expiryTime;
43.     }
45.     public boolean isExpired() {
46.         return System.currentTimeMillis() > expiryTime;
47.     }
48. }

复制代码

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

SparseArray 是 Android 提供的一个高效数据结构，用于整数键值对的存储和查找。它通过优化内存使用和查找性能，特殊适合在性能敏感和内存有限的应用中使用。通过理解实在现原理和优缺点，可以在恰当的场景中充分使用其上风。
SparseArray 是一种优化的稀疏数组，适用于键为整数的场景。它的实现通过两个并行数组和二分搜索来进步查找和存储的效率，避免了使用HashMap大概带来的内存开销。

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

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。