Android入门教程-Android-SparseArray-原理解析

• 什么是 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中没找到对应的键。

<code class="java">    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 办法的流程剖析

<code class="java">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)

<code class="java">    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倍。

<code class="java">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，倡议依据如下需要选取：

• 如果对内存要求比拟高，而对查问效率没什么大的要求，能够是应用SparseArray
• 数量在百级别的 SparseArray 比 HashMap 有更好的劣势
• 要求 key 是 int 类型的，因为 HashMap 会对 int 自定装箱变成 Integer 类型
• 要求 key 是有序的且是升序

【Android 零根底入门教程视频参考】

喜欢 (0)赏

[搞代码]

分享 (0)