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. }

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

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

  13.    mSize++;

  14.    if (mEnd == null) {

  15.        mStart = newEntry;

  16.        mEnd = mStart;

  17.        return newEntry;

  18.    }

  19.    mEnd.mNext = newEntry;

  20.    newEntry.mPrevious = mEnd;

  21.    mEnd = newEntry;

  22.    return newEntry;

  23. }

读操作是通过从头指针开始,一直往后找直到对应的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> {

  2.    //...

  3.    @Override

  4.    public boolean hasNext() {

  5.        return mNext != null;

  6.    }

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

  8.    @Override

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

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

  11.            mNext = null;

  12.            mExpectedEnd = null;

  13.        }

  14.        if (mExpectedEnd == entry) {

  15.            mExpectedEnd = backward(mExpectedEnd);

  16.        }

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

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

  19.        if (mNext == entry) {

  20.            mNext = nextNode();

  21.        }

  22.    }

  23.    //...

  24. }

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

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

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

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

  4.    mIterators.put(iterator, false);

  5.    return iterator;

  6. }

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

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

  9.    mIterators.put(iterator, false);

  10.    return iterator;

  11. }

  12. public IteratorWithAdditions iteratorWithAdditions() {

  13.    IteratorWithAdditions iterator = new IteratorWithAdditions();

  14.    mIterators.put(iterator, false);

  15.    return iterator;

  16. }

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

  18.    //...

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

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

  21.            iter.supportRemove(toRemove);

  22.        }

  23.    }

  24.    //...

  25. }

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

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

640?wx_fmt=jpeg

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/safeiterablemap:一个能在遍历中删除元素的数据结构-2/

此条目发表在Android分类目录。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。