关于android:Android入门教程-Android-SparseArray-原理解析

39次阅读

共计 3631 个字符，预计需要花费 10 分钟才能阅读完成。

什么是 SparseArray？
它的外部实现采纳了什么数据结构？
SparseArray 相比于 HashMap 的优劣势是什么？

什么是 SparseArray？

SparseArray 存储的是键值对，以 int 作为 key，Object 作为 value。Sparse 有稠密、短少的意思。SparseArray 利用场景是绝对稀少的数据，个别是几百以内。

SparseArray 采纳的数据结构？

SparseArray 并不像 HashMap 采纳一维数组 + 单链表和二叉树构造，而是采纳两个一维数组，一个是存储 key(int 类型), 一个是存 value object。

    private int[] mKeys; // 存储 key
    private Object[] mValues; // 存储 value 对象
    private int mSize; // 记录存储键值对的数量

mKeys 和 mValues 读写时采纳的下标是一一对应的。

SparseArray 默认容量多大？

SparseArray 在默认构造函数中指定其默认容量大小。默认为 10

初始化后 mSize = 0，实例化 mKeys 和 mValues。

SparseArray get 办法的流程剖析

输出一个 int 型的 key，通过二分法查找匹配的下标。若没找到对应的下标，则返回 null 或用户指定的默认对象。

key 是递增寄存的。二分法查找下标时，可能会返回一个负值，此时示意在 mKeys 中没找到对应的键。

    public E get(int key) {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) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key); // 二分法查找下标

        if (i < 0 || mValues[i] == DELETED) { 
        // 找到的下标为负或以后地位元素以被删除，表明没找到
            return valueIfKeyNotFound;
        } else {return (E) mValues[i]; // 找到指定元素
        }
    }

SparseArray put 办法的流程剖析

public void put(int key, E value) {
       // 二分法找到 key 的下标
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            // 代表以后曾经存在 key 及其对应的值，间接替换 value
            mValues[i] = value;
        } else {
            // 示意以后并不存在 key，则应增加新的键值对
            // i 取反，失去要增加的数组地位下标。二叉查找返回的是 key 的“该当”寄存的地位下标。i = ~i;

            if (i < mSize && mValues[i] == DELETED) {
                // 原来地位上的元素曾经被删掉了，间接赋值替换
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                // 容量有余，进行回收操作
                gc();
                // 从新查找指标下标
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 指标下标为 i，将 key 增加进 mKeys 数组中
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            // 指标下标为 i，将 value 插入 mValues 数组中
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            // 已存储的数据个数加 1
            mSize++;
        }
}

// GrowingArrayUtils.java
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
        assert currentSize <= array.length;

        if (currentSize + 1 <= array.length) {
            // 以后数组容量短缺，index 开始的元素后移 1 位
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        // 容量有余，先扩容生成新的数组 newArray
        @SuppressWarnings("unchecked")
        T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
                growSize(currentSize));
        // 将原来数组 index 之前的局部复制到新数组对象中
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element; // 插入元素
        // 将原数组 index+ 1 之后的元素拷贝到新数组中
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

// 扩容计算规定，以后容量小于等于 4 则返回 8；否则返回 2 倍的容量
// 扩容后最小容量是 8
public static int growSize(int currentSize) {return currentSize <= 4 ? 8 : currentSize * 2;}

key 下标的二叉查找办法剖析

二叉查找办法 ContainerHelpers.binarySearch(int[] array, int size, int value)

    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
    }

如果没有找到输出 value 对应的下标，则会返回一个按位取反后的值（个别是个负值）。

例如输出 array 是 [1,2,4,5]，size 是 4，value 是 3；那么会失去 2 的取反值。而 2 就是 value 的指标地位下标。

SparseArray 最大容量？每次扩容多少？

SparseArray 并不像 HashMap 一样定义有最大容量是多少，最大能够达到 Integer.MAX_VALUE，可能会报 oom。每次扩容时如果以后容量小于 5 则扩容是 8，否则扩容为原容量的 2 倍。

public static int growSize(int currentSize) {return currentSize <= 4 ? 8 : currentSize * 2;}

SparseArray 与 HashMap 的比拟，利用场景是？

SparseArray 采纳的不是哈希算法，HashMap 采纳的是哈希算法。
SparseArray 采纳的是两个一维数组别离用于存储键和值，HashMap 采纳的是一维数组 + 单向链表或二叉树。
SparseArray key 只能是 int 类型，而 HashMap 的 key 是 Object。
SparseArray key 是有序存储（升序），而 HashMap 不是。
SparseArray 默认容量是 10，而 HashMap 默认容量是 16。
SparseArray 默认每次扩容是 2 倍于原来的容量，而 HashMap 默认每次扩容时是原容量 *0.75 倍
SparseArray value 的存储被不像 HashMap 一样须要额定的须要一个实体类（Node）进行包装
SparseArray 查找元素总体而言比 HashMap 要逊色，因为 SparseArray 查找是须要通过二分法的过程，而 HashMap 不存在抵触的状况其技术处的 hash 对应的下标间接就能够取到值。

针对下面与 HashMap 的比拟，采纳 SparseArray 还是 HashMap，倡议依据如下需要选取：