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;
mValues = new Object;
}
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 = value;
} else {
i = ~i;
if (i < mSize && mValues == DELETED) {
mKeys = key;
mValues = 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 == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues;
}
}
2.3 delete(int key)
删除键值对。
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues != DELETED) {
mValues = DELETED;
mGarbage = true;
}
}
}
2.4 removeAt(int index)
删除指定索引处的键值对。
public void removeAt(int index) {
if (mValues != DELETED) {
mValues = 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;
if (val != DELETED) {
if (i != o) {
keys = keys;
values = val;
values = 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;
}
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues;
}
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;
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;
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;
System.arraycopy(array, 0, newArray, 0, index);
newArray = element;
System.arraycopy(array, index, newArray, index + 1, currentSize - index);
return newArray;
} else {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array = 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 = element;
System.arraycopy(array, index, newArray, index + 1, currentSize - index);
return newArray;
} else {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array = element;
return array;
}
}
private static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
}
该类提供了向数组中插入元素的方法，如果数组已满，则会扩展数组容量。growSize 方法根据当前大小决定扩展大小。
四、优缺点
4.1 优点
[*]内存效率高：SparseArray 使用并行数组，避免了 HashMap 中对象封装导致的内存开销，特殊适合键是整数的环境。
[*]高效查找：通过二分查找在键数组中定位元素，查找时间复杂度为 O(log N)。
[*]自动扩展：GrowingArrayUtils 确保数组在需要时自动扩展，镌汰手动管理数组大小的贫苦。
[*]避免自动装箱：与 HashMap<Integer, Object> 差别，SparseArray 直接使用 int 类型键，避免了自动装箱的开销。
4.2 缺点
[*]不适合频仍删除操纵：删除操纵只是将值标记为 “已删除”，需要额外的垃圾回收步骤，这大概影响性能。
[*]键必须是整数：只能用于整数键的环境，不敷通用。
[*]固定容量扩展：数组扩展是按固定策略进行的（当前大小的倍数扩展），在某些极端环境下大概导致不必要的内存浪费。
五、使用场景
5.1 适用场景
[*]大量键值对：适用于需要存储大量键值对且键为整数的场景，如缓存、映射关系等。
[*]高性能要求：适合内存敏感的应用，如低端装备上的应用、实时应用等。
[*]稀疏数据集：特殊适用于键值对稀疏分布的场景。
5.2 不适用场景
[*]频仍插入删除：如果应用需要频仍插入和删除操纵，SparseArray 的性能大概不如 HashMap。
[*]非整数键：如果键不是整数，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 在大量数据操纵时性能表现良好。
欢迎点赞|关注|收藏|品评，您的肯定是我创作的动力 https://img-blog.csdnimg.cn/direct/831c93e23df14cb7a64408f00820dc3e.png#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]