android删除数组对象,Android数据结构（⼀）：SparArray ⼀、简介
SparArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both becau it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.
SparArray 与普通的数组不⼀样，它允许元素之间可以空缺(普通数组的元素必需是连续的)，所以 SparArray 类似于 Map。但是它的内存使⽤率⽐ HashMap 更⾼效：
SparArray不⽤⾃动装箱，HashMap需要⾃动装箱(例如：int 类型要变成 Integer 类型才能做为 Key )；
SparArray不需要依赖额外的数据结构(HashMap将元素封装成 Map.Entry)；
Note that this container keeps its mappings in an array data structure, using a binary arch to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary arch and adds and removes require inrting and deleting entries in the array. For containers holding up to hundreds of items, he performance difference is not significant, less than 50%.
SparArray通过『⼆分法』来查找 key，当 SparArray 数据太⼤时(元素太多了)，它的执⾏效率还不如 HashMap，因为它通过『⼆分法』来添加或删除元素时，存在数组元素的重新移动(只有在空间不⾜时才会这样，下段话会解释)。
To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-ud for the same key, or compacted later in a single garbage collection step of all removed entries. This garbage collection will need to be performed at any time the array needs to be grown or the the map size or entry values are retrieved.
SparArray为提⾼性能在删除数据时进⾏了优化，不会⽴即压缩数组⽽是为需要删除的条⽬打上标记，在往后需要数组扩容或者数据检索时进⾏数据清除和数组压缩，这样可以减少数组操作的频率，同时可以复⽤key值。
⼆、源码分析
2.1、成员变量
pantypublic class SparArray implements Cloneable {
/
/ 删除元素时，⽤ DELETED 来代替要删除的元素(标记 key 对应的元素已删除)2012高考优秀作文
private static final Object DELETED = new Object();
private boolean mGarbage = fal;
private int[] mKeys; // 存储 key 的数组
private Object[] mValues; // 存储 对象 的数组
private int mSize; // 当前已存在元素的个数
}
2.2、⼆分查找
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation.
// 从这⾥可以看出来(如果元素存在)：
/
/ 1. 第1个元素⼀定是在 array 的 mid 位置
// 2. 第2个元素⼀定是在 array 的 上/下半区的 mid 位置
// 3. 依此类推，元素的分布是每个给定 array & 指定 size 的 mid 位置
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;
} el if (midVal > value) {
hi = mid - 1;
} el {
return mid; // value found
}
}
return ~lo; // value not prent
}
}
⼤家注意，没有找到时，是对 lo 的取反。
⼀般情况，如果没有找到，我们都会返回 -1，表⽰没有找到，⽽这⾥的取反(正数取反就是负数)，同样表⽰没有找到，但是，如果我们再取反(反反得正)，就可以在该位置添加元素，是不是很巧妙？
2.3、添加对象(put)
/**
发挥英文
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
// ⼆分查找，找到 i 为正数，未找到 i 为取反后的负数
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
给某人打电话的英文if (i >= 0) {
// 找到，即相同的key，那么值就覆盖gold finger
mValues[i] = value;
} el {
// 反反得正
i = ~i;
// 如果 i 在数组长度范围内，且该处的值被标记为 DELETED(已删除)，则直接覆盖if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
求同存异英文
return;
}
// 数组空间不够，且存在有被标记 DELETED 的元素，则压缩空间
if (mGarbage && mSize >= mKeys.length) {
// 该⽅法就是真正的移除 DELETED 的元素，并移动元素
gc();
// gc 后需要重新计算新的位置(因为元素移动)
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
cruicontrol// 如果上⾯没有做 gc 操作，则表⽰空间真的全满了，需要动态增加数组⼤⼩
// 这⾥就涉及到数组的整体拷背了
mKeys = GrowingArrayUtils.inrt(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.inrt(mValues, mSize, i, value);
mSize++;
}
inconvenient}
2.4、gc
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) {
// 前⾯有元素被删除，因此 i 肯定不等于 o
if (i != o) {
家长会班主任发言稿keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = fal;
mSize = o;
}
2.5、GrowingArrayUtils.inrt
public static T[] inrt(T[] array, int currentSize, int index, T element) {
asrt currentSize <= array.length;
//⼩于数组长度，直接移动数组内数据即可
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
//⼤于现有数组长度，需要新建数组，将原数组数据拷贝⾄新数组
T[] newArray = (T[]) Class().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;
}
三、总结
study的过去式和过去分词SparArray对⽐HashMap：
优势：
避免了基本数据类型的装箱操作
不需要额外的结构体，单个元素的存储成本更低
数据量⼩的情况下，随机访问的效率更⾼
延迟删除
⼆分查找返回值的特殊处理
劣势：
插⼊和删除操作需要操作数组，效率较低数据量巨⼤时，复制数组成本巨⼤
数据量巨⼤时，⼆分查找效率也会明显下降
