容器类源码解析系列(四)—SparseArray分析

引言

容器类源码解析系列已经更新到了第四篇,前三篇已经分别对ArrayList、LinkedList、HashMap进行源码分析。

  1. 容器类源码解析系列(一)—— ArrayList 源码分析(最新版)

  2. 容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

  3. 容器类源码解析系列(三)—— HashMap 源码分析(最新版)

SparseArray 是用来存储Key-Value这种映射关系的容器,它要求Key的类型必须是int型

要点

  • Key的类型必须是int型;

  • SparseArray底层通过双数组的结构实现数据存储,一个数组用来存储key值,一个数组用来存储value;

SparseArray

  • 相较于HashMap,在存储key(int型)-value数据时,SparseArray会更省内存,但是在数据量大的情况下,查找效率没有HashMap好。

  • Sparse可以存储NULL值,没有fail-fast机制;

关于fail-fast机制,容器类源码解析系列(一)—— ArrayList 源码分析(最新版) 这篇文章有详细介绍。

构造方法

在看构造方法之前先看一下几个重要成员变量。

1
2
3
4
5
6
  private static final Object DELETED = new Object();
  private boolean mGarbage = false;
  
  private int[] mKeys;
  private Object[] mValues;
  private int mSize;

mKeys和mValues是我上面提到的那两个数组,分别用来存储key和value的。mSize表示容器中key-value键值对的数量。 DELETED是什么呢?还有mGarbage? 上面的要点中,我们提到,SparseArray在存储数据时比HashMap更省内存,但是效率没有HashMap高,SparseArray使用了二分查找,这个我们在后面的源码分析中能够看到。 所以SparseArray想了一个方法来提高效率,就用到了DELETED和mGarbage这两个变量。这个方法是,在删除数据时,没有立马把数据置空回收,重组数组结构,而是先把要删除的value先置为DELETED状态,在后面合适的时机,mGarbage会被置为true,然后调用gc方法,统一清除DELETED状态的数据,重新调整容器结构。而在这个过程中,如果有新添加的数据,是可以复用DELETED状态对应的index的,这样DELETED数据又会变成正常数据,不会被回收了。 这样就避免了频繁的回收调整次数。

 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
	/**
     * Creates a new SparseArray containing no mappings.
     */
    public SparseArray() {
        this(10);
    }

    /**
     * Creates a new SparseArray containing no mappings that will not
     * require any additional memory allocation to store the specified
     * number of mappings.  If you supply an initial capacity of 0, the
     * sparse array will be initialized with a light-weight representation
     * not requiring any additional array allocations.
     */
    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;
    }
	

构造方法很简单,就两个构造方法,默认的不传capacity参数的情况下创建的数组长度是10。

常规操作

添加数据

 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
27
28
29
30
31
32
/**
     * 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) {
      	//通过二分查找来找到mKeys数组中对应key的index索引。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) { //如果找到了,表示之前存过这个key,则覆盖旧的value。
            mValues[i] = value;
        } else {
            i = ~i;//取反,把负数变成正数。(注释一)

            if (i < mSize && mValues[i] == DELETED) {//如果这个key对应的value之前被删除了,但是还没有被执行gc操作,目前还是DELETED状态,那么就复用此index。(注释二)
                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);//插入新key,如果需要扩容,就像ArrayList那样,通过copy操作来完成。
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);//插入新value
            mSize++;//表示新添加了一对key-value键值对。
        }
    }

上面在查找key对应的索引时,使用了二分查找二分搜索算法 。我们看下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
    }

~ 操作是什么意思呢?表示按位取反。

假设lo值为3;int是四个字节,其二进制表示为:00000000 00000000 00000000 00000011,那么~3 就等于:

11111111 11111111 11111111 11111100 等于-4。

所以注释一处的操作就好理解了。注释二 的行为表现就是我们上面说到的DELETED状态的妙用,用来提高效率的。

set 操作

1
2
3
4
5
6
7
public void setValueAt(int index, E value) {
        if (mGarbage) {
            gc();
        }

        mValues[index] = value;
    }

这里要注意index的范围要在0~size()-1之间。

删除操作

 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;
            }
        }
    }

可以看到,它在执行删除操作时并没有立马把对应的value置为null。而是先设置为DELETED状态,然后后面找到合适时机一致回收,这个期间该key是可以被复用的,如果被复用那么DELETED状态可以重新变成NORMAL状态。我们同时也注意到mGarbage这个标志位在此刻被置为了true。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
     * Removes the mapping at the specified index.
     *
     * <p>For indices outside of the range <code>0...size()-1</code>,
     * the behavior is undefined.</p>
     * 主要index的范围问题
     */
    public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

get操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
		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];
        }
    }

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
27
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);
    }

在调用gc操作后,会对那些个DELETED状态的value统一置为null ,方便回收。同时会对index进行一次重新排序。

我们看看有哪些操作可能会触发SparseArray的gc方法 注意哦,我这篇文章里说的gc操作,指的都是SparseArray内部的gc方法。

put(int key, E value) size() keyAt(int index)
valueAt(int index) setValueAt(int index, E value) indexOfKey(int key)
indexOfValue(E value) indexOfValueByValue(E value) append(int key, E value)

总结

android开发用如果存储key-value下的key是int型的话,建议使用SparseArray容器来操作,可以减少内存消耗。



扫码加入我的个人微信公众号:Android开发圈 ,一起学习Android知识!!

在这里插入图片描述