Android源码——SparseArray源码解析

SparseArray是什么？

SparseArray为int映射Object的稀疏矩阵，索引之间可以存在间隙，效率比HashMap高

继承结构

public class SparseArray implements Cloneable {

}

域

被删除时占坑、是否回收、键、值、实际大小

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

方法

构造函数

public SparseArray() {
    this(10);
}
	
public SparseArray(int initialCapacity) {
    initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
    mKeys = new int[initialCapacity];
    mValues = new Object[initialCapacity];
    mSize = 0;
}

二分查找

• key和中间值比较，大于找左边，小于找右边
• 如果key在最右边（high一直未改变），则取反返回
• 如果找到（high=low），则返回索引
• 如果未找到，则对high取反返回

private static int binarySearch(int[] a, int start, int len, int key) {
    int high = start + len, low = start - 1, guess;
    while (high - low > 1) {
        guess = (high + low) / 2;
        if (a[guess] < key)
            low = guess;
        else
            high = guess;
    }
    if (high == start + len)
        return ~(start + len);
    else if (a[high] == key)
        return high;
    else
        return ~high;
}

这里未找到不返回-1，而是对下一个存放位置进行取反，取反后值小于0

put和set方法

• 通过二分查找获取索引，i >= 0说明存在则替换
• 若旧元素已被删除（DELETED），则替换
• 若新增，但超过最大容量可回收，则gc并寻找插入位置
• 若新增，但超过最大容量不可回收，则扩容
• 若新增，且新增元素不是最后一位，则 i 后面的key和value往后移
• 新数据插入，size++

public void put(int key, E value) {
    int i = binarySearch(mKeys, 0, 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();
            i = ~binarySearch(mKeys, 0, mSize, key);
        }
        if (mSize >= mKeys.length) {
            int n = ArrayUtils.idealIntArraySize(mSize + 1);
            int[] nkeys = new int[n];
            Object[] nvalues = new Object[n];
            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
            mKeys = nkeys;
            mValues = nvalues;
        }
        if (mSize - i != 0) {
            System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
            System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
        }
        mKeys[i] = key;
        mValues[i] = value;
        mSize++;
    }
}

设置对应index的value，若有删除则需先gc

public void setValueAt(int index, E value) {
    if (mGarbage) {
        gc();
    }
    mValues[index] = value;
}

append方法

追加到末尾，当key大于所有已存在key的情况，省去二分查找

• 若传入的key小于最大的key，则调用put
• 若超过最大容量但可回收，则gc
• 若超过最大容量不可回收，则扩容
• 插入到末尾或扩容后的位置

public void append(int key, E value) {
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
        put(key, value);
        return;
    }
    if (mGarbage && mSize >= mKeys.length) {
        gc();
    }
    int pos = mSize;
    if (pos >= mKeys.length) {
        int n = ArrayUtils.idealIntArraySize(pos + 1);
        int[] nkeys = new int[n];
        Object[] nvalues = new Object[n];
        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
        mKeys = nkeys;
        mValues = nvalues;
    }
    mKeys[pos] = key;
    mValues[pos] = value;
    mSize = pos + 1;
}

get方法

通过二分查找获取索引，未找到返回null或默认值

public E get(int key) {
    return get(key, null);
}

public E get(int key, E valueIfKeyNotFound) {
    int i = binarySearch(mKeys, 0, mSize, key);
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

返回key或value，若有删除则需先gc

public int keyAt(int index) {
    if (mGarbage) {
        gc();
    }
    return mKeys[index];
}


public E valueAt(int index) {
    if (mGarbage) {
        gc();
    }
    return (E) mValues[index];
}

remove方法

通过二分查找获取索引，若存在则置为DELETED，mGarbage置为true，这里只删除value，不缩减size，删除key将在gc或put中覆盖

public void delete(int key) {
    int i = binarySearch(mKeys, 0, mSize, key);
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

public void remove(int key) {
    delete(key);
}

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

clear方法

置空value，为什么要新建一个Object[]，而不是直接使用mValues？

public void clear() {
    int n = mSize;
    Object[] values = mValues;
    for (int i = 0; i < n; i++) {
        values[i] = null;
    }
    mSize = 0;
    mGarbage = false;
}

gc方法

• 若不存在DELETED，则 i 和 o 始终相等
• 若存在DELETED，则 i 比 o 多1，o即是DELETED所在索引
• 下一次遍历时，覆盖o所在位置的key和value
• 遍历完后mGarbage置false，最终大小为o

private void gc() {
    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;
}

size方法

先gc回收，再返回实际大小

public int size() {
    if (mGarbage) {
        gc();
    }
    return mSize;
}

index方法

若存在返回index，否则返回一个负数

public int indexOfKey(int key) {
    if (mGarbage) {
        gc();
    }
    return binarySearch(mKeys, 0, mSize, key);
}

线性查找，value不唯一，只能找到第一个对应的value，未找到返回-1

public int indexOfValue(E value) {
    if (mGarbage) {
        gc();
    }
    for (int i = 0; i < mSize; i++)
        if (mValues[i] == value)
            return i;
    return -1;
}

clone方法

调用Object和数组的clone进行深拷贝

public SparseArray clone() {
    SparseArray clone = null;
    try {
        clone = (SparseArray) super.clone();
        clone.mKeys = mKeys.clone();
        clone.mValues = mValues.clone();
    } catch (CloneNotSupportedException cnse) {
        /* ignore */
    }
    return clone;
}