一、全文概括
1、SparseArray数据结构
2、数据插入以及取出过程
3、常见问题
二、SparseArray数据结构
1、由两个数组组成，一个用于存储key,一个用于存储value。存储key的数组为int型，存储value的数组为对象类型
2、key在数组中的index就是value在相应数组中的index
三、数据的插入以及取出过程
1、数据的插入文字描述
1.1、根据利用二分查找是否有对应的key值，若有返回大于0的index,替换value数组中相应index的值
1.2、没有找到则返回小于0的index.将index取反变为正数，查看value数组对应index的状态是否为删除状态。若为删除状态。则把key存在key数组index位上，把value存在value数组index位上。
1.3、如果不为删除状态，则判断是否需要回收(remove和delete方法都是改变相应位置的状态)；如果需要进行回收，然后重新计算index;
1.4、插入数据，先判断需不需扩容，如果不需要则将key数组和value数组index及之后的数据往后移一位，将index对应的key和value插入
1.5、如果需要扩容（小于等于4，则返回8， 否则返回当前size的两倍）然后把index之前的数据考入，把index对应的key和value插入，把index后面的数据拷入
2、数据插入流程图
sparseArray插入过程.png
3.获取数据过程
利用二分查找找到key相应的index 然后获取value值
四、常见问题
1、有一堆数从中选两个数相加等于10；
常规的解决方法：暴力解决需要两个for循环
把数存入SparseArray
网友评论