Android - SparseArray

SparseArray

SparseArray :
1.是一个稀疏数组,最大限度的利用空间,内部是两个数组对数据Key 和 Value进行保存
2.数组数据是有序排列
3.根据二分法对Key进行查找
SparseArray 和 ArrayMap 的区别

• ArrayMap : 存储的Key是Key的HashCode()值,Key可以使任意类型
• SparseArray : 存储的Key是一个Int类型的数据,key只能是int类型

SparseArray源码 - 重要字段

//一个value被删除时会被赋值成DELETED
private static final Object DELETED = new Object();
//是否需要gc(),这个gc()不是系统gc(),是内部自定义gc()方法
private boolean mGarbage = false;
//存储Key 的数组
private int[] mKeys;
//存储Value的数组
private Object[] mValues;
//实际的数据存储长度
private int mSize;

SparseArray源码 - 结构图

1679248-bbc4898bd546681f.png

SparseArray源码 - 构造方法

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源码 - put

  public void put(int key, E value) {
    //通过二分法查找Key在数组中的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //i>=0 : 表示已经存在这个Key,直接赋值Value
    if (i >= 0) {
      mValues[i] = value;
    } else {
      //否则取反,例子:i = -11 , ~i = 10
      i = ~i;
      //如果i < 实际数据的长度 && Value[]数组上对应的值已经标记为Delete
      //对Key[]直接赋值,对Value[]直接赋值,return
      if (i < mSize && mValues[i] == DELETED) {
        mKeys[i] = key;
        mValues[i] = value;
        return;
      }
      //需要垃圾回收 && 实际数据长度 >= Key[]数组的长度
      if (mGarbage && mSize >= mKeys.length) {
        //把标记成Delete的数据开始回收
        gc();
        //重新查找Key在Key[]的位置
        i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
      }
      //数据插入到数组中,GrowingArrayUtils实际就是StringBuffer
      mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
      mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
      mSize++;
    }
  }
流程 :
  1.通过二分法查找Key[]数组中的index,index>0表示Key存在
  2.存在 : 直接找到Value[index] 修改
  3.判断index是否小于size,并且Value的值是否已经标记Delete
  4.是 : 直接根据index赋值Key[]和Value[]的值
  5.是否需要垃圾回收,删除已经标记Delete的数据,根据二分法重新获取index
  6.通过StringBuffer对数据进行insert()

SparseArray源码 - get

  public E get(int key) {
    return get(key, null);
  }
  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];
      }
  }
流程 :
  1.通过二分法查找mKeys[]数组,找到Key 的index
  2.index < 0 || mValues[index] == Delete ,表示值已经被删除,返回null
  3.返回对应的value

SparseArray源码 - remove,delete

  public void remove(int key) {
    delete(key);
  }
  public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
      if (i >= 0) {
        if (mValues[i] != DELETED) {
          mValues[i] = DELETED;
          mGarbage = true;
        }
    }
  }
流程 :
  1.通过二分查找mKeys[]中Key对应的index
  2.index > 0 : 数据存在,把mValues[index] = Delete(不会直接删除), mGarbage = true

SparseArray源码 - gc

  private static void gc() {
    Object DELETED = new Object();
    int n = 10;
    int o = 0;
    int[] keys = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Object[] values = new Object[]{DELETED, DELETED, "30", 
                                  "40", "50", DELETED, "70", "80", "90", "100"};
    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;
          System.out.println("Keys = "+Arrays.toString(keys));
          System.out.println("Values = "+Arrays.toString(values));
        }
        o++;
      }
    }
    System.out.println("Keys = "+Arrays.toString(keys));
    System.out.println("Values = "+Arrays.toString(values));
  }
源码修改了部分,直接打印出结果,方便参考
结果:
Keys     =  [3, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Values   =  [30, Object@7f31245a, null, 40, 50, @7f31245a, 70, 80, 90, 100]
Keys     =  [3, 4, 3, 4, 5, 6, 7, 8, 9, 10]
Values   =  [30, 40, null, null, 50, Object@7f31245a, 70, 80, 90, 100]
Keys     =  [3, 4, 5, 4, 5, 6, 7, 8, 9, 10]
Values   =  [30, 40, 50, null, null, Object@7f31245a, 70, 80, 90, 100]
Keys     =  [3, 4, 5, 7, 5, 6, 7, 8, 9, 10]
Values   =  [30, 40, 50, 70, null, Object@7f31245a, null, 80, 90, 100]
Keys     =  [3, 4, 5, 7, 8, 6, 7, 8, 9, 10]
Values   =  [30, 40, 50, 70, 80, Object@7f31245a, null, null, 90, 100]
Keys     =  [3, 4, 5, 7, 8, 9, 7, 8, 9, 10]
Values   =  [30, 40, 50, 70, 80, 90, null, null, null, 100]
Keys     =  [3, 4, 5, 7, 8, 9, 10, 8, 9, 10]
Values   =  [30, 40, 50, 70, 80, 90, 100, null, null, null]
Keys     =  [3, 4, 5, 7, 8, 9, 10, 8, 9, 10]
Values   =  [30, 40, 50, 70, 80, 90, 100, null, null, null]