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

ops/2024/12/16 1:06:35/

文章目录

      • 一、`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__3">一、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 在大量数据操作时性能表现良好。
欢迎点赞|关注|收藏|评论，您的肯定是我创作的动力

在这里插入图片描述


http://www.ppmy.cn/ops/42446.html

相关文章

QT 圆盘百分比

QT 圆盘百分比

1. /* 设置抗锯齿 */painter.setRenderHints(QPainter::Antialiasing, true);/* 最外层的圆 */QRect drawRect event->rect();QRadialGradient gradient1(drawRect.center(), drawRect.width() / 2, drawRect.center()); gradient1.setColorAt(0, Qt::transparent); gradi…
阅读更多...
Python爬虫入门到进阶：解锁网络数据的钥匙

Python爬虫入门到进阶：解锁网络数据的钥匙

Python爬虫入门到进阶&#xff1a;解锁网络数据的钥匙 一、Python爬虫基础1.1 爬虫基本概念1.2 Python爬虫必备库1.3 第一个爬虫示例 二、实战爬虫实例2.1 爬取天气数据2.2 高级技巧&#xff1a;异步爬虫 三、反爬机制与应对策略3.1 常见反爬机制3.2 应对策略 四、性能优化与安…
阅读更多...
php基础笔记

php基础笔记

开端&#xff1a; PHP 脚本可以放在文本的任意位置 PHP 脚本以 开始&#xff0c;以 ?>** 结束&#xff1a; PHP 文件的默认文件扩展名是 ".php" 标签替换 <? echo 123;?> //short_open_tagson 默认开启 <?(表达式)?> 等价于 <?php echo …
阅读更多...
PS —— 制作证件照

PS —— 制作证件照

PS —— 制作证件照 裁剪工具魔棒工具油漆桶工具扩展画布 老是看编程&#xff0c;会有些疲劳&#xff0c;这个专栏我会放一些其他的知识&#xff0c;我们今天利用PS制作证件照&#xff08;注意&#xff0c;这里一些ps的基础操作我不会很展开的去讲&#xff09;&#xff1a; 裁…
阅读更多...
在 Keras 中使用 LSTM 层

在 Keras 中使用 LSTM 层

在 Keras 中使用 LSTM 层时&#xff0c;不需要在全连接层&#xff08;Dense 层&#xff09;前面添加展平层&#xff08;Flatten 层&#xff09;。这是因为 LSTM 层的输出已经是一个一维向量&#xff0c;可以直接作为 Dense 层的输入。下面详细解释这个问题。 ### LSTM 层的输出…
阅读更多...
如何秒杀Promise面试题

如何秒杀Promise面试题

如何秒杀Promise面试题 如果你在面试的时候技术面给你出了点关于Promise的面试题首先不要慌&#xff0c;先问候他爹妈一套问候语&#xff01; 然后切记不要(ps:这是病句别在意!&#x1f923;) 自己想 找他要纸和笔 首先关于promise的面试题无非就是 promise 的状态和宏队列、…
阅读更多...
摸鱼大数据——Hadoop基础理论知识之ZooKeeper1-3

摸鱼大数据——Hadoop基础理论知识之ZooKeeper1-3

1、ZK概述 ZooKeeper概念: Zookeeper是一个分布式协调服务的开源框架。本质上是一个分布式的小文件存储系统 ZooKeeper作用: 主要用来解决分布式集群中应用系统的一致性问题。HA搭建&#xff1b;管理去中心化的集群&#xff08;例如Kafka&#xff09; ZooKeeper结构: 采用树形…
阅读更多...
Web 安全基础：如何正确设置 HTTP 头信息

Web 安全基础：如何正确设置 HTTP 头信息

如何设置正确的网站安全头部 近年来&#xff0c;推出“安全评分卡”的公司如雨后春笋般涌现&#xff0c;这已开始成为企业销售过程中的一个考量因素。我从客户那里了解到&#xff0c;他们对于那些被评为低分的供应商持有顾虑&#xff0c;并且至少有一次是基于这种评分初步改变…
阅读更多...
最新文章

Copyright @ 2022~2023