关于an-d-ro-id:这一次彻底搞懂SparseArray实现原理

最近在整顿 SparseArray 这一知识点的时候，发现网上大多数 SparseArray 原理剖析的文章都存在很多问题（能够说很多作者并没有读懂 SparseArray 的源码），也正因而，才有了这篇文章。咱们晓得，SparseArray 与 ArrayMap 是 Android 中高效存储 K - V 的数据结构，也是是 Android 面试中的常客，弄懂它们的实现原理是很有必要的，本篇文章就以 SparseArray 的源码为例进行深入分析。

SparseArray 能够翻译为 稠密数组，从字面上能够了解为涣散不间断的数组。尽管叫做 Array，但它却是存储 K - V 的一种数据结构。其中 Key 只能是 int 类型，而 Value 是 Object 类型。咱们来看下它的类构造：

public class SparseArray<E> implements Cloneable {
    // 用来标记此处的值已被删除
    private static final Object DELETED = new Object();
    // 用来标记是否有元素被移除
    private boolean mGarbage = false;
    // 用来存储 key 的汇合
    private int[] mKeys;
    // 用来存储 value 的汇合
    private Object[] mValues;
    // 存入的元素个数
    private int mSize;
    
    // 默认初始容量为 10
    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 仅仅实现了 Cloneable 接口并没有实现 Map 接口，并且 SparseArray 外部保护了一个 int 数组和一个 Object 数组。在无参构造方法中调用了有参结构，并将其初始容量设置为了 10。

是不是感觉很奇怪？作为一个容器类，不先讲 put 办法怎么先将 remove 呢？这是因为 remove 办法的一些操作会影响到 put 的操作。只有先理解了 remove 能力更容易了解 put 办法。咱们来看 remove 的代码：


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

能够看到 remove 办法间接调用了 delete 办法。而在 delete 办法中会先通过二分查找（二分查找代码后边剖析）找到 key 所在的地位，而后将这一地位的 value 值置为 DELETE，留神，这里还将 mGarbage 设置为了 true 来标记汇合中存在删除元素的状况。设想一下，在删除多个元素后这个汇合中是不是就可能会呈现不间断的状况？大略这也是 SparseArray 名字的由来吧。

作为一个存储 K - V 类型的数据结构，put 办法是 key 和 value 的入口。也是 SparseArray 中最重要的一个办法。先来看下 put 办法的代码：

// SparseArray
public void put(int key, E value) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) { // 意味着之前 mKeys 中曾经有对应的 key 存在了, 第 i 个地位对应的就是 key。mValues[i] = value; // 间接更新 value
    } else { // 返回正数阐明未在 mKeys 中查找到 key
      
        // 取反失去待插入 key 的地位
        i = ~i;
      
    // 如果插入地位小于 size, 并且这个地位的 value 刚好是被删除掉的，那么间接将 key 和 value 别离插入 mKeys 和 mValues 的第 i 个地位
        if (i < mSize && mValues[i] == DELETED) {mKeys[i] = key;
            mValues[i] = value;
            return;
        }
    // mGarbage 为 true 阐明有元素被移除了，此时 mKeys 曾经满了，然而 mKeys 外部有被标记为 DELETE 的元素
        if (mGarbage && mSize >= mKeys.length) {
            // 调用 gc 办法挪动 mKeys 和 mValues 中的元素，这个办法能够后边剖析
            gc();
                    
            // 因为 gc 办法挪动了数组，因而插入地位可能有变动，所以须要从新计算插入地位
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        } 
    // GrowingArrayUtils 的 insert 办法将会将插入地位之后的所有数据向后挪动一位，而后将 key 和 value 别离插入到 mKeys 和 mValue 对应的第 i 个地位，如果数组空间有余还会开启扩容，后边剖析这个 insert 办法
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

尽管这个办法只有寥寥数行，然而想要齐全了解却并非易事，即便写了很具体的正文也不容易读懂。咱们无妨来详细分析一下。第一行代码通过二分查找失去了一个 index。看下二分查找的代码：

// ContainerHelpers
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 就是这个元素的最佳存储地位。上述代码中将 lo 取反作为了返回值。因为 lo 肯定是大于等于 0 的数，因而取反后的返回值必然小于等于 0. 明确了这一点，再来看 put 办法中的这个 if…else 是不是很容易了解了？

// SparseArray
public void put(int key, E value) {if (i >= 0) {mValues[i] = value; // 间接更新 value
    } else { 
        i = ~i;
        // ... 省略其它代码
    }
}

如果 i >=0, 意味着以后的这个 key 曾经存在于 mKeys 中了，那么此时 put 只须要将最新的 value 更新到 mValues 中即可。而如果 i <= 0 就意味着 mKeys 中之前没有对应的 key。因而就须要将 key 和 value 别离插入到 mKeys 和 mValues 中。而插入的最佳地位就是对 i 取反。

失去插入地位之后，如果这个地位是被标记为删除的元素，那么久能够间接将其笼罩掉了，因而有以下代码：

public void put(int key, E value) {
    // ...
    if (i >= 0) {// ...} else {    
        // 如果 i 对应的地位是被删除掉的，能够间接将其笼罩
        if (i < mSize && mValues[i] == DELETED) {mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        // ...
    }
    
}

如果上边条件不满足，那么持续往下看：

public void put(int key, E value) {
    // ...
    if (i >= 0) {// ...} else {    
    // mGarbage 为 true 阐明有元素被移除了，此时 mKeys 曾经满了，然而 mKeys 外部有被标记为 DELETE 的元素
        if (mGarbage && mSize >= mKeys.length) {
            // 调用 gc 办法挪动 mKeys 和 mValues 中的元素，这个办法能够后边剖析
            gc();
                    
            // 因为 gc 办法挪动了数组，因而插入地位可能有变动，所以须要从新计算插入地位
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        } 
        // ...
    }
    
}

上边咱们曾经晓得，在 remove 元素的时候 mGarbage 会被置为 true，这段代码意味着有被移除的元素，被移除的地位并不是要插入的地位，并且如果 mKeys 曾经满了，那么就调用 gc 办法来挪动元素填充被移除的地位。因为 mKeys 中元素地位产生了变动，因而 key 插入的地位也可能扭转，因而须要再次调用二分法来查找 key 的插入地位。

以上代码最终会确定 key 被插入的地位，接下来调用 GrowingArrayUtils 的 insert 办法来进行 key 的插入操作：

// SparseArray
public void put(int key, E value) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {// ...} else { 
         // ...

    // GrowingArrayUtils 的 insert 办法将会将插入地位之后的所有数据向后挪动一位，而后将 key 和 value 别离插入到 mKeys 和 mValue 对应的第 i 个地位，如果数组空间有余还会开启扩容，后边剖析这个 insert 办法
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

GrowingArrayUtils 的 insert 办法代码如下：

// GrowingArrayUtils
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    // 如果插入后数组 size 小于数组长度，能进行插入操作
    if (currentSize + 1 <= array.length) {
        // 将 index 之后的所有元素向后挪动一位
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        // 将 key 插入到 index 的地位
        array[index] = element;
        return array;
    }

    // 来到这里阐明数组已满，需须要进行扩容操作。newArray 即为扩容后的数组
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

// 返回扩容后的 size
public static int growSize(int currentSize) {return currentSize <= 4 ? 8 : currentSize * 2;}

insert 办法的代码比拟容易了解，如果数组容量足够，那么就将 index 之后的元素向后挪动一位，而后将 key 插入 index 的地位。如果数组容量有余，那么则须要进行扩容，而后再进行插入操作。

这个办法其实很容易了解，咱们晓得 Java 虚拟机在内存不足时会进行 GC 操作，标记革除法在回收垃圾对象后为了防止内存碎片化，会将存活的对象向内存的一端挪动。而 SparseArray 中的这个 gc 办法其实就是借鉴了垃圾收集整理碎片空间的思维。

对于 mGarbage 这个参数上边曾经有提到过了，这个变量会在删除元素的时候被置为 true。如下：

// SparseArray 中所有移除元素的办法中都将 mGarbage 置为 true

public E removeReturnOld(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {if (mValues[i] != DELETED) {final E old = (E) mValues[i];
            mValues[i] = DELETED;
            mGarbage = true;
            return old;
        }
    }
    return null;
}

public void delete(int key) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

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

public void removeAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {throw new ArrayIndexOutOfBoundsException(index);
    }
    if (mValues[index] != DELETED) {mValues[index] = DELETED;
        mGarbage = true;
    }
}

而 SparseArray 中所有插入和查找元素的办法中都会判断如果 mGarbage 为 true，并且 mSize >= mKeys.length 时调用 gc, 以 append 办法为例，代码如下：

public void append(int key, E value) {if (mGarbage && mSize >= mKeys.length) {gc();
    }
  
   // ... 省略无关代码
}

源码中调用 gc 办法的中央多达 8 处，都是与增加和查找元素相干的办法。例如 put()、keyAt()、setValueAt()等办法中。gc 的实现其实比较简单，就是将删除地位后的所有数据向前挪动一下，代码如下：

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

这个办法就比较简单了，因为 put 的时候是维持了一个有序数组，因而通过二分查找能够间接确定 key 在数组中的地位。

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 是一个应用起来很简略的数据结构，然而它的原理了解起来仿佛却没那么容易。这也是网上大部分文章对应 SparseArray 的解析都是含糊不清的起因。置信通过本篇文章的学习肯定对 SparseArray 的实现有了新的意识！

Android 根底系列教程：

Android 根底课程 U - 小结_哔哩哔哩_bilibili

Android 根底课程 UI- 布局_哔哩哔哩_bilibili

Android 根底课程 UI- 控件_哔哩哔哩_bilibili

Android 根底课程 UI- 动画_哔哩哔哩_bilibili

Android 根底课程 -activity 的应用_哔哩哔哩_bilibili

Android 根底课程 -Fragment 应用办法_哔哩哔哩_bilibili

Android 根底课程 - 热修复 / 热更新技术原理_哔哩哔哩_bilibili

本文转自 https://juejin.cn/post/6972985532397649933，如有侵权，请分割删除。

关于an-d-ro-id:这一次彻底搞懂SparseArray实现原理

一、SparseArray 的类构造

二、SparseArray 的 remove()办法

三、SparseArray 的 put()办法

四、SparseArray 的 gc()办法

五、SparseArray 的 get()办法

六、总结

相干教程

Just My Socks（注册教程内含优惠码）

关于an-d-ro-id:这一次彻底搞懂SparseArray实现原理

一、SparseArray 的类构造

二、SparseArray 的 remove()办法

三、SparseArray 的 put()办法

四、SparseArray 的 gc()办法

五、SparseArray 的 get()办法

六、总结

相干教程

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）