内存优化之Android 容器类总结

目的

节省内存

源码

frameworks/base/core/java/android/util 
SpareArray 
SparseIntArray 
SparseLongArray 
SparseSetArray 
SparseBooleanArray 
ArraySet 
ArrayMap

代码介绍

SparseArray<E> implements Cloneable

SparseIntArray implements Cloneable

SparseLongArray implements Cloneable

SparseBooleanArray implements Cloneable

SparseSetArray<T>//此类为隐藏的类，没有公开

ArraySet<E> implements Collection<E>, Set<E>

ArrayMap<K, V> implements Map<K, V>

详细分析
参考:Android Q源码
一、ArrayMap
ArrayMap优化了HashMap存储Object --> Object的键值存储;
重点介绍：
1.put方法

public V put(K key, V value) {
    ········
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;
}

index使用key的hashcode值作为条件，生成一个mHashes列表
key和value都保存在一个数组中，数据对象为Object，此时，mArray的大小为mHashes*2
通过index找key和value

2.remove方法
将移除的数值至为null

public V remove(Object key) {
    final int index = indexOfKey(key);
    if (index >= 0) {
        return removeAt(index);
    }

    return null;
}

public V removeAt(int index) {
    if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
        // The array might be slightly bigger than mSize, in which case, indexing won't fail.
        // Check if exception should be thrown outside of the critical path.
        throw new ArrayIndexOutOfBoundsException(index);
    }

    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        // Now empty.
        ········
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        freeArrays(ohashes, oarray, osize);
        nsize = 0;
    } else {
        nsize = osize - 1;
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {

            ········

            if (index > 0) {
                if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize
                        + " to " + index);
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
        } else {
            ······
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }
    mSize = nsize;
    return (V)old;
}
注：
ArraySet:思路跟ArrayMap的做法一致

二、SparseArray
SparseArray优化了int --> Object的键值存储;
重点介绍
1.put方法

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分搜索

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;//这个有什么用？

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

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

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

两个数组，一个是mKeys,一个是mValues
通过key，使用二分搜索找到index赋值mKeys、mValues

2.remove方法
通过对mValues赋值一个DELETED对象

public void remove(int key) {
    delete(key);
}

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

注：
1）SparseIntArray优化了int --> int的键值存储;
2）SparseBooleanArray优化了 int --> boolean的键值存储;
3）SparseLongArray优化了 int --> long的键值存储。


特别注意：这里涉及二分法的搜索
android.util.ContainerHelper
    ContainerHelper.binarySearch

参考学习
https://www.jianshu.com/p/fdbc9d05981e
https://blog.csdn.net/qq_41345773/article/details/92066554