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