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为止。
写操作是直接尾插入到链表中。

遍历时删除元素

1. 每当需要遍历的时候，记下这个Iterator
2. 删除元素时通知所有正在遍历的Iterator
3. Iterator收到通知后修正下一个元素
4. 记下的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 是非常出色的。

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