Java容器解析系列(16) android内存优化之SparseArray

HashMap的缺点:

自动装箱导致的性能损失;
使用拉链法来解决hash冲突,如果hash冲突较多,需要遍历链表,导致性能下降,在Java 8 中,如果链表长度>8,会使用红黑树来代替链表;
由于loadFactor的存在,导致(1 - loadFactor) * capacity 的空间会浪费,capacity越大,浪费空间更多;
扩容时需要重新计算hash,浪费性能;
每一个value都由一个Node保存,Node除了保存本身的数据外,还需要其他冗余数据,如hash值,下一个节点的指针等;

SparseArray的特点:

key只能为int类型,避免了自动装箱;
使用二分法查找key,在查询指定key时需要进行二分查找,查询的时间复杂度为O(logN),添加删除亦如是;所以不适合大量数据,在数据量为1000以下(up to hundreds of items)时,其与HashMap之间的性能差别(difference)低于50%;
没有冗余数据;
为了提升性能,在删除数据时,并不马上调整压缩数组(压缩数组需要移动数组的元素),而是将被删除位置的value标记为DELETED,之后该位置可能被重用,在一次压缩中,清除掉所有的DELETED;
可以通过keyAt(int)和valueAt(int)来遍历SparseArray中的key和value;
扩容时只是复制数组值,不需要进行hash计算;

总体来看,相对于HashMap,SparseArray是以时间换空间;

数据结构:

SparseArray使用两个数组来分别存储key和value:

private int[] mKeys;// 存储key值的数组

private Object[] mValues;// 存储value值的数组  mKeys[i]---mValues[i]为一个键值对

private int mSize;// 存储键值对个数,确切地说,是当前存储的key值个数,key-value键值对均存储在数组中下标为 [0,mSize-1]之间的位置

private static final Object DELETED = new Object();// DELETED标记

private boolean mGarbage = false;// 用于判断是否需要进行压缩

构造方法:

public SparseArray() {

   this(10);// 默认初始容量:10

}

public SparseArray(int initialCapacity) {

   if (initialCapacity == 0) {

      mKeys = EmptyArray.INT;

      mValues = EmptyArray.OBJECT;

   } else {

      mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);

      mKeys = new int[mValues.length];// key value数组大小一致

   }

   mSize = 0;

}

添加key-value:

public void put(int key, E value) {

   int i = ContainerHelpers.binarySearch(mKeys, mSize, key);// 通过二分法查找key在mKeys中的索引

   if (i >= 0) {

      mValues[i] = value;// 覆盖已有值

   } else {

     // 如果没有找到，那么i值为 ~(0) 或 ~(mSize - 1),这里再取反,值就成了 0 或  (mSize - 1),参考源码 ContainerHelpers.binarySearch(mKeys, mSize, key)

      i = ~i;

      if (i < mSize && mValues[i] == DELETED) {// 刚好是一个被删除的值直接替换

         mKeys[i] = key;

         mValues[i] = value;

         return;

      }

      // 需要通过gc(),腾出新的空间

      if (mGarbage && mSize >= mKeys.length) {

         gc();

         // gc() 后索引变了,需要重新找个位置,重新二分查找,确定key/value在数组中的索引

         i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);

      }

      mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);// 插入新key

      mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);// 插入新值

      mSize++;

   }

}

上述部分引用方法如下:

// # ContainerHelpers.binarySearch(int[], int, int)

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.gc()

// 对 mKeys 和 mValues 进行重新排列,将mValues中标记为DELETED的值清除掉

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;// 更新mSize

}

// # GrowingArrayUtils.insert(int[], int, int, int);

public static int growSize(int currentSize) {

    return currentSize <= 4 ? 8 : currentSize * 2;// 扩容为之前的两倍

}

public static int[] insert(int[] array, int currentSize, int index, int element) {

    // 不需要扩容

    if (currentSize + 1 <= array.length) {

        // 将之后的所有元素向后移一位 这里的时间复杂度为O(N)

        System.arraycopy(array, index, array, index + 1, currentSize - index);

        array[index] = element;// 插入元素到指定位置

        return array;

    }

    // 扩容

    int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));

    System.arraycopy(array, 0, newArray, 0, index);

    newArray[index] = element;// 插入元素到指定位置

    System.arraycopy(array, index, newArray, index + 1, array.length - index);

    return newArray;

}

查询:

public E get(int key) {

   return get(key, null);

}

// 获得指定key的值，如果没有，返回 valueIfKeyNotFound

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];

   }

}

删除:

public void remove(int key) {

   delete(key);

}

public void delete(int key) {

   int i = ContainerHelpers.binarySearch(mKeys, mSize, key);// 二分法找到位置

   if (i >= 0) {

      // 将值修改为 DELETED

      if (mValues[i] != DELETED) {

         mValues[i] = DELETED;

         mGarbage = true;// 需要垃圾回收,必要时检查该变量,并对 mKeys 和 mValues 进行重新排序

      }

   }

   // 这里并没有将 mSize - 1,因为如果将 mSize - 1，需要重新对 mKeys 和 mValues 进行重新移动

}

综上,SparseArray的时间复杂度:

增:O(N);因为需要移动数组元素;
查:O(logN).使用二分法查找;
删:O(logN);查找到要删除的key之后,将其value标记为DELETED;
改:O(logN);同删除,只是将value改为新值而已;

如果key为long类型的话,可以使用LongParseArray,其实现与ParseArray相同,只是mKeys为long[]

如果key为int类型:

value为int类型,可以使用SparseIntArray
value为long类型,可以使用SparseLongArray
value为boolean类型,可以使用SparseBooleanArray

跟多关于Android的SparseArray相关,参考视频:

SparseArray Family Ties

巴特西

Java容器解析系列(16) android内存优化之SparseArray

最新文章

热门文章