SafeIterableMap：一个能在遍历中删除元素的数据结构

SafeIterableMap 是由Google工程师编写，应用在 Android Architecture Components 中的一个数据结构，可以在 LiveData 的Library里面找到对应的使用和源码。

SafeIterableMap 具有以下特性：

• 支持键值对存储，用链表实现，模拟成Map的接口

• 支持在遍历的过程中删除任意元素，不会触发ConcurrentModifiedException

• 非线程安全

其实这个数据结构的实际应用场景几乎是没有的，因为 Iterator.remove() 方法基本可以满足我们在遍历中删除元素的需求。但是，SafeIterableMap 里面有很多trick还是非常值得学习。

用链表来实现Map接口

1. protected Entry<K, V> get(K k) {

2.    Entry<K, V> currentNode = mStart;

3.    while (currentNode != null) {

4.        if (currentNode.mKey.equals(k)) {

5.            break;

6.        }

7.        currentNode = currentNode.mNext;

8.    }

9.    return currentNode;

10. }

12. protected Entry<K, V> put(@NonNull K key, @NonNull V v) {

13.    Entry<K, V> newEntry = new Entry<>(key, v);

14.    mSize++;

15.    if (mEnd == null) {

16.        mStart = newEntry;

17.        mEnd = mStart;

18.        return newEntry;

19.    }

21.    mEnd.mNext = newEntry;

22.    newEntry.mPrevious = mEnd;

23.    mEnd = newEntry;

24.    return newEntry;

25. }

读操作是通过从头指针开始，一直往后找直到对应的key为止。 写操作是直接尾插入到链表中。

遍历时删除元素

1. 每当需要遍历的时候，记下这个Iterator

2. 删除元素时通知所有正在遍历的Iterator

3. Iterator收到通知后修正下一个元素

4. 记下的Iterator是弱引用，以防遍历结束后内存泄漏

看一下Iterator的相关实现：

1. private abstract static class ListIterator<K, V> implements Iterator<Map.Entry<K, V>>,SupportRemove<K, V> {

3.    //...

5.    @Override

6.    public boolean hasNext() {

7.        return mNext != null;

8.    }

10.    //每当删除元素时会调用这个方法，通知entry被删除了

11.    @Override

12.    public void supportRemove(@NonNull Entry<K, V> entry) {

13.        if (mExpectedEnd == entry && entry == mNext) {

14.            mNext = null;

15.            mExpectedEnd = null;

16.        }

18.        if (mExpectedEnd == entry) {

19.            mExpectedEnd = backward(mExpectedEnd);

20.        }

21.        //上面两个判断是当删除了最后一个元素时，要把尾指针修正到前一个位置

23.        //当删除的是下一个元素时，要把mNext指针指到再下一个

24.        if (mNext == entry) {

25.            mNext = nextNode();

26.        }

27.    }

29.    //...

30. }

通过在 supportRemove(Entry<K,V> removedEntry) 方法中修正尾指针和下一个元素的指针，就可以达到安全遍历的效果。那么，在 remove 方法是怎么通知各个Iterator呢：

1. private WeakHashMap<SupportRemove<K, V>, Boolean> mIterators = new WeakHashMap<>();

3. public Iterator<Map.Entry<K, V>> iterator() {

4.    ListIterator<K, V> iterator = new AscendingIterator<>(mStart, mEnd);

5.    mIterators.put(iterator, false);

6.    return iterator;

7. }

9. public Iterator<Map.Entry<K, V>> descendingIterator() {

10.    DescendingIterator<K, V> iterator = new DescendingIterator<>(mEnd, mStart);

11.    mIterators.put(iterator, false);

12.    return iterator;

13. }

15. public IteratorWithAdditions iteratorWithAdditions() {

16.    IteratorWithAdditions iterator = new IteratorWithAdditions();

17.    mIterators.put(iterator, false);

18.    return iterator;

19. }

21. public V remove(@NonNull K key) {

22.    //...

24.    if (!mIterators.isEmpty()) {

25.        for (SupportRemove<K, V> iter : mIterators.keySet()) {

26.            iter.supportRemove(toRemove);

27.        }

28.    }

30.    //...

31. }

在需要遍历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 是非常出色的。

最适合的数据结构才是最好的。