SafeIterableMap：一个能在遍历中删除元素的数据结构
SafeIterableMap 是由Google工程师编写，应用在 Android Architecture Components 中的一个数据结构，可以在 LiveData 的Library里面找到对应的使用和源码。
SafeIterableMap 具有以下特性：
- 支持键值对存储，用链表实现，模拟成Map的接口
- 支持在遍历的过程中删除任意元素，不会触发ConcurrentModifiedException
- 非线程安全
其实这个数据结构的实际应用场景几乎是没有的，因为
Iterator.remove()方法基本可以满足我们在遍历中删除元素的需求。但是，SafeIterableMap里面有很多trick还是非常值得学习。
用链表来实现Map接口
protected Entry<K, V> get(K k) {
Entry<K, V> currentNode = mStart;
while (currentNode != null) {
if (currentNode.mKey.equals(k)) {
break;
}
currentNode = currentNode.mNext;
}
return currentNode;
}
protected Entry<K, V> put(@NonNull K key, @NonNull V v) {
Entry<K, V> newEntry = new Entry<>(key, v);
mSize++;
if (mEnd == null) {
mStart = newEntry;
mEnd = mStart;
return newEntry;
}
mEnd.mNext = newEntry;
newEntry.mPrevious = mEnd;
mEnd = newEntry;
return newEntry;
}
读操作是通过从头指针开始，一直往后找直到对应的key为止。
写操作是直接尾插入到链表中。
遍历时删除元素
- 每当需要遍历的时候，记下这个Iterator
- 删除元素时通知所有正在遍历的Iterator
- Iterator收到通知后修正下一个元素
- 记下的Iterator是弱引用，以防遍历结束后内存泄漏
看一下Iterator的相关实现：
private abstract static class ListIterator<K, V> implements Iterator<Map.Entry<K, V>>,SupportRemove<K, V> {
//...
@Override
public boolean hasNext() {
return mNext != null;
}
//每当删除元素时会调用这个方法，通知entry被删除了
@Override
public void supportRemove(@NonNull Entry<K, V> entry) {
if (mExpectedEnd == entry && entry == mNext) {
mNext = null;
mExpectedEnd = null;
}
if (mExpectedEnd == entry) {
mExpectedEnd = backward(mExpectedEnd);
}
//上面两个判断是当删除了最后一个元素时，要把尾指针修正到前一个位置
//当删除的是下一个元素时，要把mNext指针指到再下一个
if (mNext == entry) {
mNext = nextNode();
}
}
//...
}
通过在 supportRemove(Entry<K,V> removedEntry) 方法中修正尾指针和下一个元素的指针，就可以达到安全遍历的效果。那么，在 remove 方法是怎么通知各个Iterator呢：
private WeakHashMap<SupportRemove<K, V>, Boolean> mIterators = new WeakHashMap<>();
public Iterator<Map.Entry<K, V>> iterator() {
ListIterator<K, V> iterator = new AscendingIterator<>(mStart, mEnd);
mIterators.put(iterator, false);
return iterator;
}
public Iterator<Map.Entry<K, V>> descendingIterator() {
DescendingIterator<K, V> iterator = new DescendingIterator<>(mEnd, mStart);
mIterators.put(iterator, false);
return iterator;
}
public IteratorWithAdditions iteratorWithAdditions() {
IteratorWithAdditions iterator = new IteratorWithAdditions();
mIterators.put(iterator, false);
return iterator;
}
public V remove(@NonNull K key) {
//...
if (!mIterators.isEmpty()) {
for (SupportRemove<K, V> iter : mIterators.keySet()) {
iter.supportRemove(toRemove);
}
}
//...
}
在需要遍历Map的时候，获取的 Iterator 就会被放到一个 WeakHashMap 中，当Map需要 remove 元素的时候只要通知 WeakHashMap 中所有的迭代器即可。这里的trick是用了 WeakHashMap 而不是 List<WeakReference>，缺点是只用到key部分的内容，value部分的内存是放弃的，但更大的好处是不需要我们维护删除已经被GC的迭代器，WeakHashMap 可以帮助清理掉key已经被回收的entry。
SafeIterableMap 用在 LiveData 里面是非常恰到好处的。因为 LiveData 的订阅者数量通常不会很多，所以使用链表来存储会比 HashMap 节省很多内存空间。而且 SafeIterableMap 的插入操作是O(1)的,遍历操作与 HasMap 相似，所以速度上是毫不逊色的（还少了hash计算）。所以在这种元素不多，不需要 randomAccess 的场合中, SafeIterableMap 是非常出色的。
最适合的数据结构才是最好的。
