Android特有的数据结构分析

android为了减少内存的使用和装箱拆箱损耗的性能，提供一些特有的数据接口，在 android.util包下面，都是使用数据进行保存，适当的使用这些对象可以优化我们的应用

ArrayMap
ArraySet
SparseArray
SparseIntArray
SparseBooleanArray
SparseLongArray

ArrayMap可代替Map

//保存hashint[] mHashes;//保存key和valueObject[] mArray;

 public V put(K key, V value) {        final int hash;        int index;        //先计算index取反的值        if (key == null) {            hash = 0;            index = indexOfNull();        } else {            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();            index = indexOf(key, hash);        }        if (index >= 0) {            index = (index<<1) + 1;            final V old = (V)mArray[index];            mArray[index] = value;            return old;        }        index = ~index;        if (mSize >= mHashes.length) {            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);            final int[] ohashes = mHashes;            final Object[] oarray = mArray;            allocArrays(n);            if (mHashes.length > 0) {                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);                System.arraycopy(oarray, 0, mArray, 0, oarray.length);            }            freeArrays(ohashes, oarray, mSize);        }        //扩展数组        if (index < mSize) {            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)                    + " to " + (index+1));            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);        }        mHashes[index] = hash;        //key value连续保存        mArray[index<<1] = key;        mArray[(index<<1)+1] = value;        mSize++;        return null;    }

ArraySet
跟ArrayMap数据结构一样，只保存value，value唯一

int[] mHashes;    Object[] mArray;

 public boolean add(E value) {        final int hash;        int index;        if (value == null) {            hash = 0;            index = indexOfNull();        } else {            hash = mIdentityHashCode ? System.identityHashCode(value) : value.hashCode();            index = indexOf(value, hash);        }        if (index >= 0) {            return false;        }        index = ~index;        if (mSize >= mHashes.length) {            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);            if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n);            final int[] ohashes = mHashes;            final Object[] oarray = mArray;            allocArrays(n);            if (mHashes.length > 0) {                if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0");                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);                System.arraycopy(oarray, 0, mArray, 0, oarray.length);            }            freeArrays(ohashes, oarray, mSize);        }        if (index < mSize) {            if (DEBUG) Log.d(TAG, "add: move " + index + "-" + (mSize-index)                    + " to " + (index+1));            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);            System.arraycopy(mArray, index, mArray, index + 1, mSize - index);        }        mHashes[index] = hash;        mArray[index] = value;        mSize++;        return true;    }

SparseIntArray
key-value映射类型，使用基础类型int，原来替换Map<>Map

private int[] mKeys;private int[] mValues;

    public void put(int key, int value) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            mValues[i] = value;        } else {            i = ~i;            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);            mSize++;        }    }    //GrowingArrayUtils.java     public static  T[] insert(T[] array, int currentSize, int index, T element) {        assert currentSize <= array.length;        //数组长度足够，插入数据        if (currentSize + 1 <= array.length) {            System.arraycopy(array, index, array, index + 1, currentSize - index);            array[index] = element;            return array;        }        //数字长度不足，一般扩展2倍空间        @SuppressWarnings("unchecked")        T[] newArray = ArrayUtils.newUnpaddedArray((Class)array.getClass().getComponentType(),                growSize(currentSize));        //复制index前面部分数据        System.arraycopy(array, 0, newArray, 0, index);        newArray[index] = element;         //复制index后面部分数据        System.arraycopy(array, index, newArray, index + 1, array.length - index);        return newArray;    }        public static int growSize(int currentSize) {        return currentSize <= 4 ? 8 : currentSize * 2;    }

SparseLongArray 可代替Map

private int[] mKeys;private long[] mValues;

SparseBooleanArray 可代替Map

 private int[] mKeys;private boolean[] mValues;

SparseArray Map

private int[] mKeys;    private Object[] mValues;

更多相关文章

随机推荐