Android中你还在用HashMap<Integer,Object>吗？

发表于   |   分类于   |     |   阅读次数

Android中你还在使用HashMap<Integer,Object>吗？

众所周知，当我们要维护一个整型到对象的映射关系的时候，想定义一个Map<int,Object>会报错，我们必须使用Map<Integer,Object>。

明明只需要使用一个整型数据，却要使用一个类。这并不是杀鸡用牛刀，而是一种浪费。

是不是很押韵。

SparseArray的简介

SparseArray，是android.util包下的一个类，介绍是这样的：

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.

意思就是(翻译的不好，勿喷)：

SparseArrays是一个整型到对象的映射，它不像一个正常的对象数组，在索引处可以是空的。他是为了比HashMap提供更高的内存性能而设计的。原因有两点：

  1. 它避免了对key自动装箱操作；
  2. 每个映射关系也不是依赖额外的对象。

思考：

  1. 它要如何使用？使用起来和HashMap有什么区别？
  2. 它是如何提高内存性能的？有没有负作用？

SparseArray的使用

基本的使用方法，以及与Map的使用区别：一起来看代码：

1
2
3
4
5
6
7
8
9
10
11
12
//定义
SparseArray<Object> sparseArray = new SparseArray<>() ;
Map<Integer,Object> map = new HashMap<>() ;
//添加数据
sparseArray.put(1,new Object());
map.put(1,new Object()) ;
//取数据
Object o1 = sparseArray.get(1) ;
Object o2 = map.get(1) ;
//删除数据
sparseArray.remove(1);
Object o3 = map.remove(1);

在基本的使用过程中，SparseArray与Map的使用方法基本上一模一样。细微区别就是SparseArray的remove没有返回值。不过这无伤大雅。你可以完全把它按照Map的使用方法使用。

SparseArray如何提高内存性能的

从SparseArray的源码分析：

成员变量

意思看名字都知道了。

1
2
3
private int[] mKeys;
private Object[] mValues;
private int mSize;

它的key值使用的是int的数组，并不是Integer。那么这就避免了自动装箱操作。它的Key和Value分别是存储在两个数组中。这就没有使用额外的对象来维护key和value之间的映射关系。因此它的内存使用效率非常高。

自动装箱，举个栗子便于理解：Integer integer = 1 ;

主要方法

既然没有使用额外的对象来维护映射关系，那我们看看它是如何工作的：

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
        }
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

put的过程：

  1. 使用二分查找算法查找key在数组中的位置。如果有返回对应位置，如果没有返回第一个比它大的值的位置的取反值。
  2. i>=0 即是已经包含了该值。这个时候直接赋值
  3. 如果没有包含该值，中间两个判断先忽略，看完remove再来看，分别在两个数组中插入值。

分析一下这个过程：

使用二分查找的时间复杂度是O(logn)，而插入操作中涉及到了对象的移动。而在HashMap中由key得到对应的位置是计算出来了，是O(1)，而且没有插入操作没有对象的移动。该过程是用时间换空间。

get

get方法最终调用的下面这个方法：其中valueIfKeyNotFound为null

1
2
3
4
5
6
7
8
9
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];
    }
}

这个就很简单了，二分查找对应位置，如果有返回，如果没有，就返回null；查找时间复杂度O(logn)，HashMap中计算是O(1)；

remove

remove方法最终调用的是delete方法：

1
2
3
4
5
6
7
8
9
10
public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

这个方法中使用的是二分查找，然后把值标记为DELETED，然后把mGarbage改为true；

通过使用DELETED标记删除的数据，减少了数据移动造成的不必要的浪费。mGarbage其实在put方法中就有，说忽略了。现在回头看其中两个判断：

1
2
3
4
5
6
7
8
9
10
11
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);
}

第一个if是，如果要插入的位置是DELETED，那么就直接替换。

第二个if是，如果有垃圾，又并且空间不够了，就执行垃圾回收操作并重新计算位置。

gc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}

这里可以看出，垃圾回收是遍历和移动数据。
一个垃圾回收是O(n)的时间复杂度。

扩展容量

这个时候应该想到，如果它的空间不够了怎么办？这个时候就要扩展容量了。

这个工作主要是在插入的时候做的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }
    //下面的是容量不够的情况
    @SuppressWarnings("unchecked")
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize)); 
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

容量扩展的算法是growSize控制的，源码附上，这个不解释了：

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

总结

  1. SparseArray是为了替换Map而设计的。当你要使用Map时可以考虑使用SparseArray。
  2. SparseArray的基本使用方法与Map一样，方法名也一样。只是remove没有返回值。
  3. SparseArray消耗内存比HashMap少，但是速度稍慢。使用的时候做好权衡。时间复杂度大概O(logn)和O(1)的差别。

希望对你有帮助。看源码烦了，最后给大家一个福利：