android进阶篇06、SparseArray和ArrayMap源码解析-一一网

SparseArray和ArrayMap都是HashMap的替代品，主要目的就是为了节省内存，因为在手机上内存是比较宝贵的；虽然在效率上有一点牺牲，但是如果存储的元素个数在1000这个量级之内的，其实效率和HashMap并没有什么差别；

一、SparseArray

1、成员变量和构造方法

我们首先看一下几个比较重要的成员变量和构造方法

成员变量

注释1处的DELETED在删除元素时用于标记，后面介绍remove方法时会看到；

注释2处的mGarbage也是删除元素时用于标记，在remove方法中也会看到；

注释3处的mKeys数组用于存放键值对的key，类型为int；

注释4处的mValues数组用于存放键值对的value，类型为Object；

注释5处的mSize表示存放的键值对的个数；

//1
private static final Object DELETED = new Object();
//2
private boolean mGarbage = false;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int)
//3
private int[] mKeys;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E)
//4
private Object[] mValues;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
//5
private int mSize;
复制代码

构造方法

两个构造方法如下所示，默认无参构造方法的容量为10；我们也可以通过传入int值初始化容量值；

/**
 * Creates a new SparseArray containing no mappings.
 */
public 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;
}
复制代码

下面我们接着看几个比较重要的方法；

2、put方法

put方法如下所示，从方法参数也可以看出key只能为int；

注释1处的binarySearch方法也就是二分查找，在下面单独介绍；

注释2处分支表示存在key对应的键值对，此时直接将mValues数组更新即可；

注释3处这个i=~i注意一下，待会分析完二分查找就会明白什么意思；

注释4处表示此key对应的索引i处的value已经被删除，并且索引i小于mSize，此时直接将mKeys和mValues数组中索引i对应的值更新即可；

注释5分支表示将标记为DELETED的键值对清除，并重新通过二分查找计算一下索引值，因为清除完元素索引可能发生变化；

注释6处的insert方法会通过数组拷贝的方式重新创建，我们下边单独介绍；

/**
 * 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) {
    //1
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //2
        mValues[i] = value;
    } else {
        //3
        i = ~i;

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

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

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        
        //6
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}
复制代码

先介绍一下上边注释1处的二分查找方法

这个方法没有什么特别需要解释的地方，就是传统的二分查找的实现，不过有一点需要注意一下，在数组中没有找到key时并不是返回null或者-1；注释1处表示没有找到key时返回~lo，也就是key在数组中的左边界的索引值的取反；这样也就解释了上边注释3处i=~i为什么那么做了；

// This is Arrays.binarySearch(), but doesn't do any argument validation.
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
        }
    }
    //1
    return ~lo;  // value not present
}
复制代码

再看一下insert方法，注释1、2、3多处调用了arrayCopy方法，也就是数组拷贝，这也是使用数组存储元素绕不开的操作；

/**
 * Inserts an element into the array at the specified index, growing the array if there is no
 * more room.
 *
 * @param array The array to which to append the element. Must NOT be null.
 * @param currentSize The number of elements in the array. Must be less than or equal to
 *                    array.length.
 * @param element The element to insert.
 * @return the array to which the element was appended. This may be different than the given
 *         array.
 */
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;

    if (currentSize + 1 <= array.length) {
        //1
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }

    @SuppressWarnings("unchecked")
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize));
    //2
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    //3
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}
复制代码

我们总结一下put方法，存放元素时，key是存放在int型数组mKeys中，并且在此数组中是有序排列的，这样我们就可以通过二分查找直接求得对应的索引值，然后再通过此索引值更新mKeys和mValues两个数组；

3、get方法

看完put方法，我们接着看一下get方法，理解了put方法，get方法就更容易理解了，get方法如下所示；

注释1处表示get方法有调用了两个参数的get方法，第二个参数表示如果没有找到对应的value值，就使用第2个参数的值；

注释2处使用二分查找法通过key找到索引i；

注释3处分支i小于0表示没有找到对应的索引，mValues[i]==DELETED表示此索引处的键值对已经被删除；

注释4处表示已经找到，则直接返回即可；

/**
 * Gets the Object mapped from the specified key, or <code>null</code>
 * if no such mapping has been made.
 */
public E get(int key) {
    //1
    return get(key, null);
}

/**
 * Gets the Object mapped from the specified key, or the specified Object
 * if no such mapping has been made.
 */
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    //2
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        //3
        return valueIfKeyNotFound;
    } else {
        //4
        return (E) mValues[i];
    }
}
复制代码

4、remove方法

增删改查就还差删除方法了，我们接着介绍一下remove方法

注释1处又调用了delete方法，因此两个方法作用是相同的；我们接着看一下delete方法；

注释2处也是先使用二分查找将key转变为索引i；

注释3处的分支i大于等于0表示存在此key对应的键值对；

注释4处mValues[i] = DELETED,mGarbage = true，这两个操作执行了删除的过程，可见删除其实并不是真正的删除，而是进行了DELETED标记；

/**
 * Alias for {@link #delete(int)}.
 */
public void remove(int key) {
    //1
    delete(key);
}

/**
 * Removes the mapping from the specified key, if there was any.
 */
public void delete(int key) {
    //2
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //3
        if (mValues[i] != DELETED) {
            //4
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
复制代码

5、gc方法

主要的知识点介绍完了，我们发现SparseArray就是借鉴了HashMap的思想，借助二分查找提高效率；其中最重要的就是减少了内存，在put方法中我们发现，只有当数组大小不够时才进行扩容，并且在扩容之前还执行gc方法保证不会有空间浪费；我们不妨看一下gc如何操作的，gc方法如下所示；

注释1处表示遍历mValues数组中的每个元素，如果没有被标记为DELETED才进行保存，这样就会将列表中被标记为DELETED的元素清除；从而减少了内存；

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

    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) {
            //1
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }
    //2
    mGarbage = false;
    mSize = o;

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

二、ArrayMap

ArrayMap的思想跟SparseArray差不多，其存在的目的主要是为了解决SparseArray中key只能为int的局限性，在ArrayMap中key和value均为泛型，我们直接分析一下三个主要的方法即可；在分析方法之前先介绍一下几个主要的成员属性；

1、成员属性

注释1处的mHashes数组用于存放key对应的hash值，因为此时的key不跟SparseArray一样只能是int了，所以我们如果还想用数组保存，就需要使用key对应的hash值放在数组中；

注释2处的mArray数组用于保存key和value键值对，你现在可能有点疑惑，一个数组怎么保存key和value两个值，我们在put方法中会进行介绍；

注释3处的mSize表示存储的键值对个数；

@UnsupportedAppUsage(maxTargetSdk = 28) // Hashes are an implementation detail. Use public key/value API.
//1
int[] mHashes;
@UnsupportedAppUsage(maxTargetSdk = 28) // Storage is an implementation detail. Use public key/value API.
//2
Object[] mArray;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
//3
int mSize;
复制代码

2、put方法

put方法有点长，我们只看几个关键的点；

注释1处用于求得key对应的hash值；

注释2处通过indexOf方法将hash值变为索引index，我们在下面单独介绍此方法；

注释3处的分支表示已经存在此key对应的键值对，只需要将新value值覆盖掉oldValue即可，并将oldValue返回；

下面很长的这一部分主要就是进行了扩容缩容等操作，我们不详细介绍了；

我们接着看注释4处，我们前面已经讲过mHashes数组用于保存key对应的hash值，mArray用于保存键值对；从这里就可以看出是如何保存的，index就是前面求得的索引值，key对应的hash值好说，直接mHashes[index]=hash即可；但是在保存键值对时进行了将index左移一位和左移一位然后加1的操作，这样索引0在mArray数组中就对应索引0和1，索引1就对应2和3，索引2就对应4和5，索引3就对应6和7……是不是很巧妙

/**
 * Add a new value to the array map.
 * @param key The key under which to store the value.  If
 * this key already exists in the array, its value will be replaced.
 * @param value The value to store for the given key.
 * @return Returns the old value that was stored for the given key, or null if there
 * was no such key.
 */
@Override
public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        //1
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        //2
        index = indexOf(key, hash);
    }
    if (index >= 0) {
        //3
        index = (index<<1) + 1;
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    index = ~index;
    if (osize >= mHashes.length) {
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= 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 (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }

        if (mHashes.length > 0) {
            if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }

        freeArrays(ohashes, oarray, osize);
    }

    if (index < osize) {
        if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
                + " to " + (index+1));
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }
    //4
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;
}
复制代码

我们接着看一下上面注释2处的indexOf方法，这个方法也挺长的，但关键部分只有1个地方，就是注释1处，看这个方法名我们就知道又是二分查找；

@UnsupportedAppUsage(maxTargetSdk = 28) // Hashes are an implementation detail. Use indexOfKey(Object).
int indexOf(Object key, int hash) {
    final int N = mSize;

    // Important fast case: if nothing is in here, nothing to look for.
    if (N == 0) {
        return ~0;
    }
    
    //1
    int index = binarySearchHashes(mHashes, N, hash);

    // If the hash code wasn't found, then we have no entry for this key.
    if (index < 0) {
        return index;
    }

    // If the key at the returned index matches, that's what we want.
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // Search for a matching key after the index.
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }

    // Key not found -- return negative value indicating where a
    // new entry for this key should go.  We use the end of the
    // hash chain to reduce the number of array entries that will
    // need to be copied when inserting.
    return ~end;
}
复制代码

我们接着看一下binarySearchHashes方法，注释1处又调用了ContainerHelpers的binarySearch方法，这个方法我们在SparseArray中已经介绍了，就是二分查找；

private static int binarySearchHashes(int[] hashes, int N, int hash) {
    try {
        //1
        return ContainerHelpers.binarySearch(hashes, N, hash);
    } catch (ArrayIndexOutOfBoundsException e) {
        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            throw new ConcurrentModificationException();
        } else {
            throw e; // the cache is poisoned at this point, there's not much we can do
        }
    }
}
复制代码

3、get方法

讲完了put方法，我们看一下get方法；

注释1处又调用了indexOfKey方法；我们接着看一下indexOfKey方法；

注释2处又调用了indexOf方法，这个方法我们在put方法中已经介绍了；

注释3处通过获得的index索引去mArray数组中查找value值，通过将index左移1位然后加1，这跟put方法就对应上了；

/**
 * Retrieve a value from the array.
 * @param key The key of the value to retrieve.
 * @return Returns the value associated with the given key,
 * or null if there is no such key.
 */
@Override
public V get(Object key) {
    //1
    final int index = indexOfKey(key);
    //3
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

/**
 * Returns the index of a key in the set.
 *
 * @param key The key to search for.
 * @return Returns the index of the key if it exists, else a negative integer.
 */
public int indexOfKey(Object key) {
    //2
    return key == null ? indexOfNull()
            : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
复制代码

4、remove方法

最后看一下remove方法；

注释1处通过indexOfKey方法求索引index，这个方法我们在get方法中已经介绍了；

注释2处通过索引调用removeAt方法执行删除操作；

/**
 * Remove an existing key from the array map.
 * @param key The key of the mapping to remove.
 * @return Returns the value that was stored under the key, or null if there
 * was no such key.
 */
@Override
public V remove(Object key) {
    //1
    final int index = indexOfKey(key);
    if (index >= 0) {
        //2
        return removeAt(index);
    }

    return null;
}
复制代码

我们接着看一下removeAt方法，这个方法也很长，我们只看一下主要操作；

注释1处通过索引从mArray数组中求得待删除的value值；

注释2处直接将mArray数组中key和value置为null；

注释3处返回oldValue；

/**
 * Remove the key/value mapping at the given index.
 *
 * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for
 * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an
 * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting
 * {@link android.os.Build.VERSION_CODES#Q} and later.</p>
 *
 * @param index The desired index, must be between 0 and {@link #size()}-1.
 * @return Returns the value that was stored at this index.
 */
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);
    }
    //1
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        // Now empty.
        if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        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) {
            // Shrunk enough to reduce size of arrays.  We don't allow it to
            // shrink smaller than (BASE_SIZE*2) to avoid flapping between
            // that and BASE_SIZE.
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);

            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }

            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 {
            if (index < nsize) {
                if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize
                        + " to " + index);
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
            //2
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }
    mSize = nsize;
    //3
    return (V)old;
}

复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

Android