Android 性能为王时代SparseArray和HashMap一争高下,它与HashMap类
Android 性能为王时代SparseArray和HashMap一争高下,它与HashMap类
文章目录
- 一、`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<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 优点
4.2 缺点
五、使用场景
5.1 适用场景
5.2 不适用场景
六、实际使用示例
下面是一个实际应用场景中的示例,用于存储和查找用户会话数据:
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
在大量数据操作时性能表现良好。
欢迎点赞|关注|收藏|评论,您的肯定是我创作的动力 |
用户评论