怡康医药网站建设方案,优化方案历史,安徽安庆网站建设公司,北京网站设计十年乐云seo1、SparseArray是android sdk 提供集合类#xff0c;主要用来替换key 为int类型#xff0c;value为Object类型的Hashmap
2、SparseArray和HashMap相比优缺点#xff1a; 优点#xff1a; 1、SparseArray存在一个int[]keys, 因此避免自动装箱 2、SparseArray扩容时只需要数…1、SparseArray是android sdk 提供集合类主要用来替换key 为int类型value为Object类型的Hashmap
2、SparseArray和HashMap相比优缺点 优点 1、SparseArray存在一个int[]keys, 因此避免自动装箱 2、SparseArray扩容时只需要数组拷贝工作system.arraycopy), 不需要重建哈希表rehash十分消耗性能 缺点: 3、SparseArray以时间换空间由于使用二分查找时间比hashmap要慢。mkeys数组的元素总是连续的即使中间会存在DELETED元素但是这些DELETED元素在后续的gc()方法中被清除掉不像hashmap数组的元素由于内在的hash冲突无法彻底解决而导致数组空间利用很浪费。 4、不适合大容量的数据存储。存储大量数据时他的性能很差千条数据以内可以使用SparseArray 5、按照key进行自然排序 二、全局变量 //用于标记当前是否有待垃圾回收GC的元素 private boolean mGarbage false
key 数组和value数组的默认打下是10 //设置数组的默认初始容量为10public SparseArray() {this(10);}/*** Creates a new SparseArray containing no mappings that will not* require any additional memory allocation to store the specified* number of mappings. If you supply an initial capacity of 0, the* sparse array will be initialized with a light-weight representation* not requiring any additional array allocations.*/public SparseArray(int initialCapacity) {if (initialCapacity 0) {mKeys EmptyArray.INT;mValues EmptyArray.OBJECT;} else {mValues ArrayUtils.newUnpaddedObjectArray(initialCapacity);mKeys new int[mValues.length];}mSize 0;}添加元素、 主要看put(int key,E value)方法当中用到了ContainerHelpers类提供binarySearch,用于查找目标key在mKeys中的当前索引或者目标索引 binarySearch方法的返回值分为两种情况 1.如果mKeys中存在对应的key,则直接返回对应的索引值 2.如果mKeys中不存在对应的key
2.1 假设mKeys中存在值比key大且大小与key最接近的值的索引为parseIndex则此方法的返回值为~parsentIndex
2.2 如果mKeys中不存在比key还要大的值的话则返回值~mKeys.length通过这种方式来存放数据可以使得mKeys的内部值一直是按照递增的方式来排序的。
//将索引 index 处的元素赋值为 value//SparseArray 的元素值都是存到 mValues 中的因此如果知道目标位置index则可以直接向数组 mValues 赋值public void setValueAt(int index, E value) {//如果需要则先进行垃圾回收if (mGarbage) {gc();}mValues[index] value;}/*** Adds a mapping from the specified key to the specified value,* replacing the previous mapping from the specified key if there* was one.*/public void put(int key, E value) {//用二分查找法查找指定 key 在 mKeys 中的索引值int i ContainerHelpers.binarySearch(mKeys, mSize, key);//找得到则直接赋值if (i 0) {mValues[i] value;} else {//binarySearch 方法的返回值分为两种情况//1、如果存在对应的 key则直接返回对应的索引值//2、如果不存在对应的 key// 2.1、假设 mKeys 中存在值比 key 大且大小与 key 最接近的值的索引为 presentIndex则此方法的返回值为 ~presentIndex// 2.2、如果 mKeys 中不存在比 key 还要大的值的话则返回值为 ~mKeys.length//可以看到即使在 mKeys 中不存在目标 key但其返回值也指向了应该让 key 存入的位置//通过将计算出的索引值进行 ~ 运算则返回值一定是 0 或者负数从而与“找得到目标key的情况返回值大于0”的情况区分开//且通过这种方式来存放数据可以使得 mKeys 的内部值一直是按照值递增的方式来排序的i ~i;//如果目标位置还未赋值则直接存入数据即可对应的情况是 2.1if (i mSize mValues[i] DELETED) {mKeys[i] key;mValues[i] value;return;}//以下操作对应两种情况//1、对应 2.1 的一种特殊情况即目标位置已用于存放其他值了// 此时就需要将从索引 i 开始的所有数据向后移动一位并将 key 存到 mKeys[i]//2、对应的情况是 2.2if (mGarbage mSize mKeys.length) {gc();//GC 后再次进行查找因为值可能已经发生变化了i ~ContainerHelpers.binarySearch(mKeys, mSize, key);}//通过复制或者扩容数组将数据存放到数组中mKeys GrowingArrayUtils.insert(mKeys, mSize, i, key);mValues GrowingArrayUtils.insert(mValues, mSize, i, value);mSize;}}//和 put 方法类似//但在存入数据前先对数据大小进行了判断有利于减少对 mKeys 进行二分查找的次数//所以在“存入的 key 比现有的 mKeys 值都大”的情况下会比 put 方法性能高public void append(int key, E value) {if (mSize ! 0 key mKeys[mSize - 1]) {put(key, value);return;}if (mGarbage mSize mKeys.length) {gc();}mKeys GrowingArrayUtils.append(mKeys, mSize, key);mValues GrowingArrayUtils.append(mValues, mSize, value);mSize;}上文说布尔变量mGarbage用于标记当前是否有待垃圾回收(GC)的元素当该值为true时即意味着当前状态需要垃圾回收回收操作不是立马进行的而是在后续操作中完成。
以下几个方法在移除元素时只是切断mValues中的引用而mKeys没进行回收这个操作gc()进行处理。 //如果存在 key 对应的元素值则将其移除public void delete(int key) {//用二分查找法查找指定 key 在 mKeys 中的索引值int i ContainerHelpers.binarySearch(mKeys, mSize, key);if (i 0) {if (mValues[i] ! DELETED) {mValues[i] DELETED;//标记当前需要进行垃圾回收mGarbage true;}}}public void remove(int key) {delete(key);}//和 delete 方法基本相同差别在于会返回 key 对应的元素值public E removeReturnOld(int key) {int i ContainerHelpers.binarySearch(mKeys, mSize, key);if (i 0) {if (mValues[i] ! DELETED) {final E old (E) mValues[i];mValues[i] DELETED;mGarbage true;return old;}}return null;}//删除指定索引对应的元素值public void removeAt(int index) {if (mValues[index] ! DELETED) {mValues[index] DELETED;//标记当前需要进行垃圾回收mGarbage true;}}//删除从起始索引值 index 开始之后的 size 个元素值public void removeAtRange(int index, int size) {//避免发生数组越界的情况final int end Math.min(mSize, index size);for (int i index; i end; i) {removeAt(i);}}//移除所有元素值public void clear() {int n mSize;Object[] values mValues;for (int i 0; i n; i) {values[i] null;}mSize 0;mGarbage false;}垃圾回收、 因为SparseArray中可能会出现只移除value和value两者之一的情况导致数组存在无效引用因此gc()方法就用于移除无效引用并将有效的元素值位置合在一起
//垃圾回收//因为 SparseArray 中可能出现只移除 value 和 value 两者之一的情况//所以此方法就用于移除无用的引用private void gc() {int n mSize;//o 值用于表示 GC 后的元素个数int o 0;int[] keys mKeys;Object[] values mValues;for (int i 0; i n; i) {Object val values[i];//元素值非默认值 DELETED 说明该位置可能需要移动数据if (val ! DELETED) {//以下代码片段用于将索引 i 处的值赋值到索引 o 处//所以如果 i o 则不需要执行代码了if (i ! o) {keys[o] keys[i];values[o] val;values[i] null;}o;}}mGarbage false;mSize o;}
