在安卓项目中, 新建一个 HashMap 对象, 会有提示: 建议使用 SparseArray 会有更好的表现. 尤其是键为 Integer 类型的 maps, 更加高效. 尤其是 value 是原始数据类型时, 可以使用 SparseIntArray 等来避免装箱的操作. (其实还有其它优势)

为什么叫 SparseArray?

SparseArray 稀疏数组. 为什么叫稀疏?

先来看下 Javascript 中关于稀疏数组的定义:

稀疏数组就是包含从 0 开始的不连续索引的数组. 通常, 数组的 length 属性值代表数组中元素的个数. 如果数组是稀疏的, length 属性值大于元素的个数. 可以用 Array() 构造函数或简单地指定数组的索引值大于当前数组长度来创建稀疏数组.

可能有点懵, 我先说下我写完这篇笔记的理解. 在 SparseArray 数组中, 部分需要删除的元素, 不会被立即从数组中删除, 而是被标记为需要删除. 只有在需要的时候, 才一次性去删除和释放空间. 这时, 数组的 length 长度不能反映有效元素的个数, 因为被标记需要删除的元素也被计算进去了. SparseArray 中, 有一个单独的成员变量来计算实际有效元素的个数. 所以 SparseArray 数组就是一大串数组中有很多标记为可删除的元素, 所以是稀疏的, 零散的. 之后会详细记录对于删除标志位的学习.

类型

Android Studio 给出的提示 - value 是原始数据类型时, 可以避免装箱的操作. 那详细看一下 SparseArray 给出的类型:

SparseArray          <int, Object>
SparseBooleanArray   <int, boolean>
SparseIntArray       <int, int>
SparseLongArray      <int, long>
LongSparseArray      <long, Object>

会发现它和 HashMap 唯一不同的就是键值对的类型, HashMap的键值都为泛型, 但是 SparseArray 的键值只能为 int/long. 因为 long 的范围更大, 所以 LongSparseArray 储存的数据比 SparseArray 多.

int 的范围是 -2^31 到 2^31-1, 而 long 是 -2^63 到 2^63-1

使用方法

SparseArray<String> sparseArray= new SparseArray<>();
       
// 增加元素
sparseArray.append(0, "myValue"); // append 方式, 追加. 其实也包含了 put. 后面源码分析
sparseArray.put(1, "myValue"); // put 方式, 指定 key 更新
        
//删除元素, 二者等同
sparseArray.remove(1);
sparseArray.delete(1);

//修改元素, put/append 相同的 key 值即可
sparseArray.put(1,"newValue");
sparseArray.append(1,"newValue");

设计思想

成员变量

首先来 SparseArray 的源码, 其中定义了一些成员变量:

private static final Object DELETED = new Object();
private boolean mGarbage = false;

// 需要说明一下
// 这里的 mKeys 数组是按照 key 值递增存储的
private int[] mKeys;
private Object[] mValues;
private int mSize;

• DELETED - 标志字段, 用于判断是否删除.
• mGarbage - 标志字段, 用于确定当前是否需要垃圾回收.
• mKeys 数组 - 存储 key. int 类型.
• mValues 数组 - 存储值
• mSize 当前元素数量

append 方法

public void append(int key, E value) {
    
    // 当 mSize 不为 0 并且不大于 mKeys 数组中的最大值时
    // 因为 mKeys 是一个升序数组, 最大值即为 mKeys[mSize-1]
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
        // 执行 put 方法
        put(key, value);
        return;
    }
    
    // 不是 put 则证明需要新增
    
    // 当垃圾回收标志 mGarbage 为 true 并且当前元素已经占满整个数组
    if (mGarbage && mSize >= mKeys.length) {
        gc(); // 执行垃圾回收进行空间压缩
    }
        
    // 当 mSize 为 0, 或者 key 值大于当前 mKeys 数组最大值的时候
    // 在数组最后一个位置插入元素.
    mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
    mValues = GrowingArrayUtils.append(mValues, mSize, value);
    
    // 元素加一
    mSize++;
}

会发现处理以下两种情况:

1. 如果是更新对应 key 的值, append 方法调用 put 方法. 此时 key 值不等于 0 且小于等于最大值. 因为 key 值之前有提到是递增存储.
2. 如果是新增. 即 key 等于 0, 数组为空, 或者 key 大于当前最大值, 在最后插入.

put 方法

public void put(int key, E value) {

    // 二分查找
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
    // 查找到
    if (i >= 0) {
        mValues[i] = value; // 更新值
    } else { // 没有找到
        i = ~i; // 获得二分查找结束后, lo 的值
        
        // 元素要添加的位置正好被标记为 DELETED, 直接覆盖它的值即可.
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        
        // 垃圾回收, 但是空间压缩后，mValues 数组和 mKeys 数组元素有变化, 需要重新计算插入的位置
        if (mGarbage && mSize >= mKeys.length) {
           gc();

            // 重新二分查找插入的位置
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        
        // 在指定位置 i 处, 插入元素
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        
        // 元素加一
        mSize++;
    }
}

方法里的二分查找取反操作很奇怪, 我们先看下二分查找的代码:

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;  // 和普通二分查找不一样的地方. 返回了负的 lo.
}

正常没找到, 我们可能会返回 -1, 表示查找失败就够了. 那为什么返回一个 lo 的取反?

1. 首先需要和 -1, 一样的功能, 需要一个负数表示没有找到.
2. 这个 lo 值其实就是新元素的插入位置.

好了, 回到 put 方法, 在拿到待插入元素应该插入的位置之后, 它首先判断需要插入的位置对应 mValues 数组的值是不是 DELETED, 如果是的话，直接覆盖, 那为什么这样做?

先看下 delete 方法源码

public void delete(int key) {
    // 查找要删除的元素下标
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

SparseArray 也有 remove 方法, 它其实是直接调用 delete, 所以二者是一样的效果.

看到这个 delete 方法, 并没有直接去删除, 而是将 value 值设为 DELETED 标志位. 然后设置 mGarbage 为 true, 也就是垃圾回收标志位. 再来看下之前紧跟着的 gc() 方法:

private void gc() {
  
    int n = mSize; // 压缩前数组大小
    int o = 0;     // 压缩后数组大小, 初始为0
    int[] keys = mKeys; // 保存新的 key 值的数组
    Object[] values = mValues; // 保存新的 value 值的数组

    for (int i = 0; i < n; i++) { 
        Object val = values[i];
        
        // 如果没有 DELETED 标志位
        if (val != DELETED) {
            
            // i != o, 说明前面已经有元素被打上 DELETED 标签
            if (i != o) {
                // 将位置 i 的元素移动到 o 处. 其实 o 处就是之前 DELETED 标签的位置. 被覆盖
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null; // 释放空间
            }

            // 新数组元素加一
            o++;
        }
    }
    
    // 回收完毕, 还原标志位
    mGarbage = false;
    
    // 回收之后数组的大小
    mSize = o;
}

所以是通过 gc() 方法, 根据标志位用 DELETED 之后的元素覆盖该标志位的元素, 达到压缩和空间释放的目的.

为什么不直接删除

回头来看 put 方法:

// 添加元素时直接覆盖 DELETED 标志位的元素
if (i < mSize && mValues[i] == DELETED) {
    mKeys[i] = key;
    mValues[i] = value;
    return;
}

还记得这一段吗? 在添加元素的时候, 如果对应的元素正好被标记了 DELETE, 那么直接覆盖它即可! 这样做, 和每次都删除元素相比, 可以直接省去删除元素的操作, 大大提高了效率. 只有空间不足的时候, 才调用 gc() 方法一次性压缩空间, 效率进一步.

SparseArray 与 HashMap、ArrayMap 比较

SparseArray 的限制在于键必须是 int/long 类型, 值必须是Object类型. 这样可以避免key自动装箱产生过多的 Object. 但是这样的话, 如果 key 值相同, 那么数据就会被直接覆盖.

• SparseArray 不能保证保留插入顺序, 在迭代的时候应该注意. SparseArray 中没有 Iterator, 只实现了 Cloneable 接口, 没有继承 Collection、List 或者 Map 接口.

• 查找数据使用的是二分法, 明显比通过 hashcode 慢, 所以数据越大, 查找速度慢的劣势越明显.

优点:

• 避免了基本数据类型的装箱操作
• 不需要额外的结构体, 单个元素的存储成本更低
• 数据量小的情况下, 随机访问的效率更高

缺点：

• 插入操作需要复制数组, 增删效率降低
• 数据量巨大时, 复制数组成本巨大，gc() 成本也大, 查询效率也会明显下降

总结

1. 通过标志位, 延迟删除机制的机制大大提高效率. 也是稀疏数组的意义所在.
2. 键为 Integer 类型的 maps, 更加高效. 尤其是 value 是原始数据类型时, 可以使用 SparseIntArray 等来避免装箱.
3. 二分法相比于 hashmap, 在大体量数据时, 效率降低.