SparseArrays源码分析

    在android开发中，如果要使用到以Integer为key的map的时候，要优先使用SparseArrays。API文档上指明使用SparseArrays可以更高效的使用内存。通过阅读源码，可以看出在SparseArrays的实现中，避免了自动装箱机制，以及舍弃了entry来保存key和value的匹配，而是分别使用了两个数组来保存key和value。但是有利就有弊，这种实现方式就不得不放弃HashMap在查找上面的效率。因为SparseArrays是通过二份查找来实现搜索的，自然比不上HashMap的查找速率。

    另外，由于key和value都是通过数组来保存的，就带来了另外一个问题。这就是数组在增加和删除的时候是比较低效的，原因大家应该都清楚。所以SparseArrays为了避免这个问题，使用了一种在我看来比较巧妙的机制。实现方法是，在删除的时候，并不是立即执行数组的删除操作，而只是把要删的key对于的value置为DELETED，声明语句为private static final Object DELETED = new Object()。同时该类有一个全局变量boolean mGarbage = false;当执行delete操作或者remove操作时，该变量会置为true。当执行查询或者增加等操作的时候，才会根据mGarbage的值来执行真正的删除操作。这样就避免了频繁的对数组进行删除操作，极大了提高了效率。

     最后需要说明的是，SparseArrays会在数组装满的情况下自动扩充容量，避免了对内存的使用浪费。如下面代码所示：

if (pos >= mKeys.length) {
            int n = ArrayUtils.idealIntArraySize(pos + 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;
        }