性能优化: HashMap SparseArray ArrayMap

2023-12-23 04:38

本文主要是介绍性能优化: HashMap SparseArray ArrayMap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考:

HashMap & SparseArray & ArrayMap 简单说明

安卓性能优化—使用ArrayMap与SparseArray

简介:

ArrayMap与SparseArray都要比传统的HashMap 更有效率;但是当数据量达到千级以上的时候,ArrayMap与SparseArray都要比传统的HashMap 效率更低50%;

ArrayMap和SparseArray一样,也会对key使用二分法进行从小到大排序,区别是ArrayMap的key是hash值,

SparseArray应用场景:

public class SparseArray<E> implements Cloneable {private int[] mKeys;					//key为intprivate Object[] mValues;		//value为泛型private int mSize;//............
}

虽说SparseArray性能比較好,可是由于其加入、查找、删除数据都须要先进行一次【二分查找】。

所以在数据量大的情况下性能并不明显,将减少至少50%。

满足下面两个条件我们能够使用SparseArray取代HashMap:

数据量不大,最好在千级以内

key必须为int类型,这中情况下的HashMap能够用SparseArray取代:

HashMap<Integer, Object> map = new HashMap<>();
//用SparseArray取代:
SparseArray<Object> array = new SparseArray<>();

SparseArray有两个优点:

1.避免了自动装箱(auto-boxing),

2.数据结构不会依赖于外部对象映射。

我们知道HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置,存放的都是数组元素的引用,通过每个对象的hash值来映射对象。而SparseArray则是用数组数据结构来保存映射,然后通过折半查找来找到对象。但其实一般来说,SparseArray执行效率比HashMap要慢一点,因为查找需要折半查找,而添加删除则需要在数组中执行,而HashMap都是通过外部映射。但相对来说影响不大,最主要是SparseArray不需要开辟内存空间来额外存储外部映射,从而节省内存。

HashMap

使用有限一维拉链数组存储结构,鉴于所用Entry结构{key, value, nextExtry},Key的hash值用于取余获得所属的数组行下标,通过链表方式顺序存放所有余数相同的各个Entry。该数组的每个存储单元被称为“桶”。

取值时依据hash定位到行,再遍历链表定位key对应的Entry对象,并通过此方式解决哈希冲突问题。

当 Entry总数据量 > 数组Length(桶容量) * 0.75默认加载因子时,数组将扩容至原数组2倍,并重新计算排布旧数据,重建数据结构,此步骤非常消耗性能,最佳方式是初始化HashMap为接近目标容量的2次幂大小,减少扩容次数。

桶容量设置得太高会导致内存浪费,而当数据量达到千万级别时容易产生大量冲突,导致冲突链表过长,影响性能。

SparseArray稀疏数组

Android框架内的优化型存储结构类,在key为整型数值类型时可考虑替代HashMap提供更有效的空间利用率。

内部通过两个平行数组方式分别(同步)存储key与value,key限定为int或long类型,节省内存,避免装箱拆箱。

采用二分法进行插入和查找,存储按大小排序,大数据集下数据插入速度慢,但查找性能高,在千级数据量内可取代HashMap。

SparseArray 的 key为int
LongSparseArray 的 key为long

 public class LongSparseArray<E> implements Cloneable { private long[] mKeys;					//key为longprivate Object[] mValues;			//value为泛型private int mSize;//............
}

ArrayMap

Android框架内的优化型存储结构类。

类似于SparseArray使用两个平行数组分别(同步)存储key与value,模拟Map使用方式,Key类型不限,同样采用二分法进行插入、查找。

LongSparseArray 和SparseArray的二分查找工具类:

class ContainerHelpers {// This is Arrays.binarySearch(), but doesn't do any argument validation.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}static int binarySearch(long[] array, int size, long value) {int lo = 0;int hi = size - 1;while (lo <= hi) {final int mid = (lo + hi) >>> 1;final long 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}
}

这篇关于性能优化: HashMap SparseArray ArrayMap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/526736

相关文章

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标(连接、查询、资源、复制),支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

Linux进程CPU绑定优化与实践过程

《Linux进程CPU绑定优化与实践过程》Linux支持进程绑定至特定CPU核心,通过sched_setaffinity系统调用和taskset工具实现,优化缓存效率与上下文切换,提升多核计算性能,适... 目录1. 多核处理器及并行计算概念1.1 多核处理器架构概述1.2 并行计算的含义及重要性1.3 并

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Linux系统性能检测命令详解

《Linux系统性能检测命令详解》本文介绍了Linux系统常用的监控命令(如top、vmstat、iostat、htop等)及其参数功能,涵盖进程状态、内存使用、磁盘I/O、系统负载等多维度资源监控,... 目录toppsuptimevmstatIOStatiotopslabtophtopdstatnmon

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

JVisualVM之Java性能监控与调优利器详解

《JVisualVM之Java性能监控与调优利器详解》本文将详细介绍JVisualVM的使用方法,并结合实际案例展示如何利用它进行性能调优,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录1. JVisualVM简介2. JVisualVM的安装与启动2.1 启动JVisualVM2

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据