HaspMap，SparseArray，ArrayMap的分析

HashMap的原理

HashMap作为各种语言的核心数据结构之一，应用非常广泛，其实现如下：
链接：https://www.cnblogs.com/chengxiao/p/6059914.html

1024555-20161113235348670-746615111.png

HashMap的缺点：

• HashMap频繁扩容效率低；
• HashMap非线程安全；
• 高度依赖hash算法，可能导致链表过长( jdk1.8后使用红黑树替代了链表)，或则频繁扩容(扩容依赖碰撞)；
• HashMap内存占用过大；

so，HashMap虽然性能卓越，但是有很多缺点，是不是我们在一些场景下(数据量较少，例如 < 1000)情况下，可以用其他数据结构来替代？

SparseArray
SparseArray(稀疏数组).他是Android内部特有的api,标准的jdk是没有这个类的.在Android内部用来替代HashMap<Integer,E>这种形式,使用SparseArray更加节省内存空间的使用,SparseArray也是以key和value对数据进行保存的.使用的时候只需要指定value的类型即可.并且key不需要封装成对象类型.
根据亲测,SparseArray存储数据占用的内存空间确实比HashMap要小一些.一会放出测试的数据在进行分析。我们首先看一下二者的结构特性.

• SparseArray 结构图
  默认容器大小10
  1541755523(1).png
• HashMap 结构图
  详见：HashMap介绍
• Sparse在内存中维护两个数组，一个Key(int)，一个数组Value；
  在插入时,首先通过二分法查找位置，如果找到且当前位置为DELETED状态时，直接替换，其他情况分段copy(根据当前Size决定是否扩容)，因此SparseArray的效率是不如HashMap的

    /**
     * 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) {
        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);
            }

            if (mSize >= mKeys.length) {
                int n = ArrayUtils.idealIntArraySize(mSize + 1);

                int[] nkeys = new int[n];
                Object[] nvalues = new Object[n];

                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

                mKeys = nkeys;
                mValues = nvalues;
            }

            if (mSize - i != 0) {
                // Log.e("SparseArray", "move " + (mSize - i));
                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
            }

            mKeys[i] = key;
            mValues[i] = value;
            mSize++;
        }
    }

delete操作

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

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

SparseArray内部维护了一套整理机制，在特殊情况下会触发（获取Size时，插入时等）

    /**
     * Returns the number of key-value mappings that this SparseArray
     * currently stores.
     */
    public int size() {
        if (mGarbage) {
            gc();
        }

        return mSize;
    }

    /**
     * Given an index in the range <code>0...size()-1</code>, returns
     * the key from the <code>index</code>th key-value mapping that this
     * SparseArray stores.
     *
     * <p>The keys corresponding to indices in ascending order are guaranteed to
     * be in ascending order, e.g., <code>keyAt(0)</code> will return the
     * smallest key and <code>keyAt(size()-1)</code> will return the largest
     * key.</p>
     */
    public int keyAt(int index) {
        if (mGarbage) {
            gc();
        }

        return mKeys[index];
    }

SparseArray的gc并不是垃圾回收机制(java GC)，Sparse的gc完成的工作是内存整理，对于标记为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) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;

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

扩容算法：

    public static int idealByteArraySize(int need) {
        for (int i = 4; i < 32; i++)
            if (need <= (1 << i) - 12)
                return (1 << i) - 12;

        return need;
    }

• 总结
  HaspMap速度更优，但是在内存占用比较大，默认16，扩充系数0.75，每次扩充2倍。在移动端，数据量比较少的情况下(1000以下)，HaspMap的优势不太明显，但是内存占用比较大。因此Android针对于移动端采用了SparseArray(key必须是Int)和ArrayMap等轻量级的数据结构。