(Note) Android-SparseArray

2018-11-07 本文已影响1人 CokeNello

Thanks

EmptyArray.java

ArrayUtils.java

面试必备：SparseArray源码解析

SparseArray.java

GrowingArrayUtils.java

Android学习笔记之性能优化SparseArray

类简介

源码的类简介：

/**
 * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
 * there can be gaps in the indices.  It is intended to be more memory efficient
 * than using a HashMap to map Integers to Objects, both because it avoids
 * auto-boxing keys and its data structure doesn't rely on an extra entry object
 * for each mapping.
 *
 * <p>Note that this container keeps its mappings in an array data structure,
 * using a binary search to find keys.  The implementation is not intended to be appropriate for
 * data structures
 * that may contain large numbers of items.  It is generally slower than a traditional
 * HashMap, since lookups require a binary search and adds and removes require inserting
 * and deleting entries in the array.  For containers holding up to hundreds of items,
 * the performance difference is not significant, less than 50%.</p>
 *
 * <p>To help with performance, the container includes an optimization when removing
 * keys: instead of compacting its array immediately, it leaves the removed entry marked
 * as deleted.  The entry can then be re-used for the same key, or compacted later in
 * a single garbage collection step of all removed entries.  This garbage collection will
 * need to be performed at any time the array needs to be grown or the the map size or
 * entry values are retrieved.</p>
 *
 * <p>It is possible to iterate over the items in this container using
 * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
 * <code>keyAt(int)</code> with ascending values of the index will return the
 * keys in ascending order, or the values corresponding to the keys in ascending
 * order in the case of <code>valueAt(int)</code>.</p>
 */

由注释可以得到一些特性：

SparseArray是int映射到object的数据结构，它不像一般的对象数组，它的索引中可能存在着间隙。
它使用的是int作为key而不是integer，避免了auto-boxing带来的性能消耗，性能较好
注意的是，其通过数组的数据结构去存储keys，在增删查改的时候，基于Binary search去查找对应的key，即二分查找，时间复杂度为O(log2N)，其相对来说比HashMap，时间复杂度O(1)，要慢，对于数据量多的场景下，性能下降更加明显
因为用的是Binary Search，所以其key是有序的
为了提升性能，在删除的时候，并不会立即压缩数组，回收空间，而是先标记此元素已经被删除，再到合适的时机再执行GC方法把空间回收。如果在被GC之前，有别的元素命中了此被标记为删除的元素，就可以直接使用这个空间而不需要再次开辟空间。

变量

//删除时，对应的值赋值为`delete`，在gc的时候再对空间进行回收
private static final Object DELETED = new Object();
//是否需要gc
private boolean mGarbage = false;
//存储keys值数组
private int[] mKeys;
//存储values的数组
private Object[] mValues;
//大小
private int mSize;

构造函数

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

最主要的是上面这个，传入大小，如果大小为0，则赋值一个：EmptyArray.INT 和 EmptyArray.OBJECT，这两个又是啥呢？我们看一下这个类：

public final class EmptyArray {
    private EmptyArray() {}
    public static final boolean[] BOOLEAN = new boolean[0];
    public static final byte[] BYTE = new byte[0];
    public static final char[] CHAR = new char[0];
    public static final double[] DOUBLE = new double[0];
    public static final int[] INT = new int[0];
    public static final Class<?>[] CLASS = new Class[0];
    public static final Object[] OBJECT = new Object[0];
    public static final String[] STRING = new String[0];
    public static final Throwable[] THROWABLE = new Throwable[0];
    public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0];
}

嗯，其实就是一个空的数组。接着，不为空的话，就初始化对应的大小的数组。
其，默认的构造函数如下，默认是初始化10的容量：

public SparseArray() {
    this(10);
}

查

public E get(int key) {
    return get(key, null);
}

@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //如果index是小于零，说明是没找到，或者其对应的value被标记了`DELETED`，即value被删除而还没被gc.
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

查找的核心是，Binary Search，我们看看里面的方法：

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) {
            //value要找的数大于中间值，说明需要找的肯定不在低区，查找范围折半
            lo = mid + 1;
        } else if (midVal > value) {
            //value要找的数小于于中间值，说明需要找的肯定不在高区，查找范围折半
            hi = mid - 1;
        } else {
            //找到
            return mid;  // value found
        }
    }
    //在最后，lo>hi，则说明了没有找到这个元素，此时的lo下标必定是大于等于0的。
    //而，找到的时候，lo也是大于等于0，所以最后做了一个取反的操作，即是如果小于零说明没有找到。
    return ~lo;  // value not present
}

一个非递归的二分查找，因为在没有找到的时候，lo的值可能大于等于0的，所以最后做了一个取反的操作，即是如果小于零说明没有找到。

删除

删除对于key的数据，先查找，若找到则把对应的值置为DELETED，把mGarbage = true

public void delete(int key) {
    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);
}

public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}

删除对应key，并返回删除的Value，有点像栈的pop，此方法标记为@hide

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

删除从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 put(int key, E value) {
    //先二分查找是否已经存在
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //大于零说明已经存在相应的KEY，则更新VALUE
    if (i >= 0) {
        mValues[i] = value;
    }
    //小于0说明没有找到
    else {
        //取反，KEY本来应该在i位置的
        i = ~i;
        //如果对应的位置合法并且标记`DELETED`，则重新复用
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //如果被标记需要gc，先GC，再二分查找一次
        if (mGarbage && mSize >= mKeys.length) {
            gc();
            //再二分查找一次，因为GC后下标可能会改变
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //到这里，已经GC，已经压缩过数组，则不存在被标记`DELETED`的情况，则需数组扩容后再插入：
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

这里，GrowingArrayUtils.insert来对数组进行扩充：

public static int[] insert(int[] array, int currentSize, int index, int element) {
        //断言：当前集合长度 小于等于 array数组长度
        assert currentSize <= array.length;
        //不需要扩容
        if (currentSize + 1 <= array.length) {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
        //需要扩容：扩容大小由方法growSize确定
        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;
}

growSize(currentSize)：根据现在的size 返回合适的扩容后的容量

public static int growSize(int currentSize) {
        //如果当前size 小于等于4，则返回8， 否则返回当前size的两倍
        return currentSize <= 4 ? 8 : currentSize * 2;
}

GC

GC并不是我们说的JVM的GC，而是SparseArray一个方法

private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        //遍历原来的数组，把标记了`DELETED`
        //的位置清理，i来遍历原数组，
        //o则是标记当前的非`DELETED`的位置
        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;

        // Log.e("SparseArray", "gc end with " + mSize);
    }

Clone方法

SparseArray只实现了接口：Cloneable

public SparseArray<E> clone() {
    SparseArray<E> clone = null;
    try {
        clone = (SparseArray<E>) super.clone();
        clone.mKeys = mKeys.clone();
        clone.mValues = mValues.clone();
    } catch (CloneNotSupportedException cnse) {
        /* ignore */
    }
    return clone;
}

这是一个深复制的一个clone实现。

总结

SparseArray，时间换空间

保存的数据量无论是大还是小，Map所占用的内存始终是大于SparseArray的。有数据显示：数据量100000条时SparseArray要比HashMap要节约27%的内存.

Android里面还有其他的类似的：SparseBooleanArray，SparseIntArray，SparseLongArray，整体逻辑和设计都差不多
SparseArray 的查找性能要比 HashMap 要慢

(Note) Android-SparseArray

Thanks

类简介

变量

构造函数

查

删除

增，改

GC

Clone方法

总结

猜你喜欢

热点阅读