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

YvesCheung / 文 发表于2018-03-18 23:48 次阅读 源码,livedata,safeiterablemap

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 是非常出色的。

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

收藏 赞 (0) 踩 (0)