转载

Java填坑系列之SparseArray

前言

今天我们来了解一下与HashMap类似的数据结构SparseArray，并分析下它的源码实现。在分析源码的过程中，我们带着以下几个问题来看。

SparseArray底层数据结构是什么？
SparseArray如何通过key获得对应数组下标
SparseArray的扩容机制是什么？
SparseArray与HashMap有什么区别？

核心字段

private static final Object DELETED = new Object();
  private boolean mGarbage = false;
  private int[] mKeys;
  private Object[] mValues;
  private int mSize;
复制代码

首先我们先来了解一下SparseArray类中声明的变量都是做什么的，如下

DELETED 表示删除状态(后面详细说明)
mGarbage 表示是否GC
mKeys 表示Key数组，SparseArray中专门存取Key的数组
mValues 表示Values数组，SparseArray中专门存取Value的数组
mSize 表示数组实际存储的元素大小

小结

通过了解以上几个变量，我们可以大概知道SparseArray底层是通过两个数组来实现的，一个int数组来存取Key，一个Object数组来存取Value。

构造方法

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;
    }
复制代码

可以看出SparseArray默认容量为10，然后我们来看一下put()方法。

put()

public void put(int key, E value) {
  	//通过key获取对应的数组位置
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //若i>=0，说明key存在，直接赋值
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //此时i<0，然后对i取反
            i = ~i;
	    //如果i<mSize并且i对应的Value已经是标记位删除状态，那么就复用这个位置
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //如果需要GC并且mSize大于等于mKeys数组的长度，那么进行GC，并且重新查找i
            if (mGarbage && mSize >= mKeys.length) {
                gc();
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //最后分别插入key和value，并且判断是否需要扩容
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }
复制代码

通过分析put()方法源码，我们可以知道SparseArray添加元素可以分为以下几步。

获取key对应的数组位置i
判断i是否大于0
- 如果i>0,说明key存在，直接赋值
- 如果i<0，说明key不存在
  - 如果i<mSize并且i对应的Value已经是标记位删除状态，那么就复用这个位置
  - 如果需要GC并且mSize大于等于mKeys数组的长度，那么进行GC，并且重新查找i
  - 最后分别插入key和value，并且判断是否需要扩容

查找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;  
            }
        }
        return ~lo;  
    }
复制代码

可以看出通过二分查找的方式来获得key在数组中对应的下标，最后如果没找到，会对lo取反并返回。

GC相关方法

private void gc() { 
   	//表示实际大小
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        //遍历所有元素，如果某个元素标记为DELETED，那么就删除
        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++;
            }
        }
        //设为false，表示不需要GC
        mGarbage = false;
        mSize = o;
    }
复制代码

扩容机制

在插入key和value时调用了GrowingArrayUtils的insert()方法，然后我们来看一下SparseArray里如何进行扩容的，源码如下。

public static int[] insert(int[] array, int currentSize, int index, int element) {
        assert currentSize <= array.length;
        //不需要扩容
        if (currentSize + 1 <= array.length) {
            //从index以后的元素向后移一位
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            //在index对应的位置赋值
            array[index] = element;
            return array;
        }
	//需要扩容，创建一个新数组
        int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
        //将array数组中从0到index之间的元素(不包括index对应的元素)复制到新数组中
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        //再将index之后的元素复制到新数组中
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }
    
  public static int growSize(int currentSize) {
  		//如果currentSize小于等于4，就为8，否则乘以2
        return currentSize <= 4 ? 8 : currentSize * 2;
    }
复制代码

通过分析以上方法的源码，我们知道了SparseArray的扩容机制，主要步骤如下。

创建一个新数组，数组容量根据currentSize来判断
将旧数组中，index之前的数组元素复制到新数组中
对新数组中的index对应的元素进行赋值
将旧数组中，index之后的数组元素复制到新数组中

删除操作

我们再来看一下SparseArray的删除方法，通过查看源码可以发现有多个删除方法，我们一个个的来看一下。

remove(int key)

public void remove(int key) {
        delete(key);
    }
public void delete(int key) {
	//通过key获得对应的数组下标i
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
        //如果mValues[i]没有被标记为DELETED，那么就进行标记，并设置mGarbage为true，表示需要GC
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
复制代码

可以看出该方法是通过key来进行删除，主要分为以下几步。

获得key对应的数组下标
如果i>=0，判断mValues[i]是否被标记为DELETED
- 如果没有被标记为DELETED，那么就进行标记，并设置mGarbage为true，表示需要GC

removeAt(int index)

public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }
复制代码

通过index找到对应的位置进行删除操作。

查找

get(int key)

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通过key来查找对应的元素，主要有以下几步。