您好、欢迎来到现金彩票网!
当前位置:在线斗牛棋牌游戏 > 稀疏数据 >

SparseArray 稀疏数组解析

发布时间:2019-05-31 16:02 来源:未知 编辑:admin

  安卓提供了一个名为SparseArray的数据结构,用来替代小型的以int为key的HashMap,SparseArray牺牲了一些运行性能,用以换取内存节省。本文将针对SparseArray源码进行相关剖析。

  SparseArray的底层实现为数组,在SparseArray中定义了下面两个数据结构,分别用来记录Key和Value,可以发现由于这个数据结构要求键必须是int,因此稀疏数组内部实现没有使用包装类,从而避免了拆装箱的成本。

  SparseArray的查询操作是最基础的操作,代码如下所示。从代码中可以看出,SparseArray的内部数组大小远小于Integer范围,因此采用了二分查找的映射方式。

  如果二分查找结果0,或者目标点被标记为DELETED,则代表KEY无效。

  SparseArray的具体映射方式如下所示,可以发现数组索引是连续的,但是KEY不是连续的,如果要查询5,通过二分查找算法,算出下标为1,因此直接访问下标为1的Value即可。

  增加操作第一步是通过二分查找找出元素应该存放的位置,如果当前KEY已存在,则直接覆盖,因此修改操作的时间复杂度是O(log(n))。

  如果当前KEY不存在,则证明要新插入一个KEY。插入新的KEY分为以下四种情况:

  如果KEY对应的位置已经被某个元素占据,需要移动这个元素以后的所有元素,把位置空出来,然后放置KEY。

  如果KEY对应的位置已经被某个元素占据,并且此时没办法向后移动元素,因为所有的位置都已经被占据,则需要执行GC操作,GC操作删除一些被DELETE标记的元素,从而使得整个数组尾部有空闲位置,可以向后移动元素。(对应第二个if)

  如果KEY对应的位置已经被某个元素占据,并且通过GC操作依然没办法向后移动元素。此时代表数组容量确实不足,需要数组扩容。ert函数当插入的下标大于数组长度时会自动扩容。

  对于上述四种情况,除了第一种情况的时间复杂度为O(1)之外,其他的时间复杂度为O(n)。

  SparseArray采用了标记删除算法,通过GC操作进行真正回收,从而可以减少数组移动次数。由于是标记删除,因此删除操作的时间复杂度为O(1)。

  GC操作算法中维护了一个整数o,代表剩余的元素数量,对于未标记为DELETE的元素,将下标o对应位置的Key和Object进行赋值,然后o++即可。

  通过上述分析,可以发现SparseArray是一个适用于Key为Int,且数据量较小情况下,为了优化内存占用,从而替代HashMap的工具。

  根据官方文档的描述,在数据量较大的情况下,SparseArray比HashMap性能要差,在数百条数据的情况下,两个数据结构的差异并不是很明显,性能差异小于50%。

  SparseArray通过数组实现,避免了K,V结构体,从而减少了内存占用。另一方面,避免装箱和拆箱操作对于内存和速度都有轻微的优化效果。标记删除使得数据结构的删除复杂度为O(1)。

  但是,由于底层基于数组拷贝实现插入操作,因此对于数据量较大的情况,SparseArray性能较差。另外,对于高并发情况,SparseArray不是线程安全的,需要特别注意。返回搜狐,查看更多

http://svabelgium.com/xishushuju/62.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有