Android数据结构解析系列：
Android中的数据结构解析（一）ArrayList、LinkedList、Vector
Android中的数据结构解析（二）HashSet、LinkedHashSet、TreeSet
Android中的数据结构解析（三）HashMap、HashTable、TreeMap

HashMap是Java和Android开发中非常常用的数据结构，相信大多数人都对它非常熟悉。然而，作为一名Android开发，仅仅只知道使用HashMap是不够的。在很多情况下，HashMap对内存的消耗较大，从而影响移动设备的性能。因此，为了内存优化和性能提升，Android提供了用来替代HashMap的api：SparseArray和ArrayMap。

SparseArray

先来看一下SparseArray的介绍：

/** * SparseArrays map integers to Objects.  Unlike a normal array of Objects, * there can be gaps in the indices.  It is intended to be more memory efficient * than using a HashMap to map Integers to Objects, both because it avoids * auto-boxing keys and its data structure doesn't rely on an extra entry object * for each mapping. */

可以看到，SparseArray只能存储key为int类型的数据。所以，可以使用SparseArray来替代HashMap。它在性能上优于HashMap的原因有两点：

1.避免了int转为Integer时的自动装箱
在上一节中讲过，HashMap是通过key值的hashCode方法来确定元素存放的位置的。所以，当key值是基本类型int时，会自动装箱成Integer对象。装箱过程中会创建对象，这个动作是很消耗内存的。而SparseArray避免了装箱的这个动作，从而提升了性能。

2.避免了额外的Entry对象
HashMap的底层实现是数组+链表的数据结构。HashMap的每一条数据都会用一个Entry对象进行记录：

static class HashMapEntry implements Entry {    final K key;    V value;    final int hash;    HashMapEntry next;

除了key和value之外，还记录了hash值，和到下一个Entry对象的指针。而SparseArray只需要一个key数组和一个value数组存放数据（下面会讲到），不需要额外的Entry对象，从而节省了内存。

接下来看一下SparseArray的具体实现和常用方法：

构造方法：

    private int[] mKeys;    private Object[] mValues;    private int mSize;    ……    public SparseArray() {        this(10);    }    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;    }

key和value分别存放在mKeys和mValues这两个数组中。调用无参构造方法时，默认初始化数组的长度为10。

再来看一下SparseArray中增删改查方法的实现：

    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取反(~)就是应该插入的位置            i = ~i;            //如果插入的位置刚好是被删除过的元素，则直接将删除掉的value替换为要插入的value            if (i < mSize && mValues[i] == DELETED) {                mKeys[i] = key;                mValues[i] = value;                return;            }            //如果曾经删除过元素且没有进行过gc，进行一次gc操作            if (mGarbage && mSize >= mKeys.length) {                gc();                // gc后数组下标可能会改变 所以重新查找一遍                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);            }            //插入的操作            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);            mSize++;        }    }

SparseArray存储的元素都是按元素的key值从小到大排列好的。put方法的第一行，先调用了ContainerHelpers.binarySearch(mKeys, mSize, key)查找key是否存在。看一下这个方法的源码：

    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    }

就是一个简单的二分查找算法，如果找到key就返回key的位置，如果找不到就返回key应该插入位置的取反。二分查找是SparseArray的核心算法，可以快速查找到key的位置。

再回到put方法。在对key进行二分查找之后，如果key存在则直接替换掉相应的value，如果key不存在则在对应的位置插入key和value。

看到这里可能会有人迷糊了：中间那两个莫名其妙的if是干嘛的呢？好像删掉它们也不会有什么问题啊？这里就涉及到了SparseArray的一个巧妙的优化。我们知道，对数组进行插入和删除操作的代价是非常大的，例如在数组中间删除一个元素，那么这个元素后面的所有元素都要向前移动一个位置，如果删除操作多了，会极大的降低性能。

那么SparseArray的删除操作是怎么做的呢？来看一下delete方法：

    private static final Object DELETED = new Object();    ……    public void delete(int key) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            if (mValues[i] != DELETED) {                mValues[i] = DELETED;                mGarbage = true;            }        }    }

首先还是用二分查找找到要删除key在数组中的位置，查找到之后，并不立即删除这个元素，而是将相应的value标记为DELETED。这样如果之后有插入的key和这个删除掉的key相同时，直接替换掉value，这样就省去了一次删除和一次插入操作，提升了性能。在执行垃圾回收gc方法时，会一次性将所有标记为DELETED的元素全部删除，使原本要执行多次的删除操作减少到了一次：

    private void gc() {        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;    }

看到这里，你应该不会再对put里那两个奇怪的if感到困惑了。再看一下get方法：

    public E get(int key) {        return get(key, null);    }    @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使用了二分查找，并且每次插入/删除等操作时都需要查找一次，所以在数据量大的时候，虽然节省了内存，但效率肯定是不如HashMap的。这时候的性能提升就很不明显了。

所以，使用SparseArray替换HashMap适合于以下两个条件：
1.key为int类型。（long类型也可以，使用LongSparseArray）
2.数据量不大。（千级左右）

ArrayMap
相对于SparseArray，ArrayMap不限制key的类型，任何的HashMap都可以用ArrayMap替换。ArrayMap的内部存储方式依然是两个数组：

    int[] mHashes;    Object[] mArray;

不过不同的是，ArrayMap的key和value全部存储在mArray数组中。存储形式可以表示为：[key1, value1, key2, value2, key3, value3……]
那么mHashes数组中存储的自然就是每一个元素的hash值，查找元素时，先计算key转换过后的hash值，在mHashes数组中找到对应的hash值的位置，然后就可以在mArray数组中找到对应的key和value了。

ArrayMap在性能上优于HashMap的原因有两点：

1.和SparseArray一样，由于使用了两个数组存储数据，不再需要额外创建Entry对象，因此节省了内存空间。

2.扩容时，HashMap会重新new一个长度为2倍的容器返回。而ArrayMap则是调用System.arraycopy方法copy数据，减少了内存开销。

ArrayMap在mHashes数组中查找hash值时，同样用的是二分查找，所以在数据量较大时效率较低。因此ArrayMap一样适合于在数据量不大时使用。

总结
综上所述，在数据量在千级或千级以内时，使用SparseArray和ArrayMap可以减少内存的消耗，提升性能。其中，在key值为int或long型时，使用SparseArray（LongSparseArray）；key值为其他对象时，使用ArrayMap。

更多相关文章

  1. Android的五大布局
  2. 20172323 2017-2018-2《程序设计与数据结构》第十一周学习总结
  3. python+appium自动化测试-元素定位之android uiautomatorandroid
  4. Android(安卓)JetPack Compose 入门
  5. 添加xmlns:android="http://schemas.android.com/apk/res/androi
  6. Android(安卓)内容提供器---创建内容提供器（元素）
  7. Android(安卓)- 主要的UI元素
  8. 构建 Android(安卓)手机 RSS 阅读器
  9. 安卓新手之路——关于layout一些属性的整理

随机推荐

  1. android.net.LocalSocket
  2. android工具之TraceView学习笔记
  3. 【总结】Android消息机制
  4. [置顶] Android中的dispatchTouchEvent()
  5. android httpclient localhost Connectio
  6. Android之Room
  7. Android参数设置: Preference
  8. Android组件的设计
  9. Android中Adapter类详解
  10. android实现简单的画画板