SafeIterableMap is a data structure written by Google engineers and applied in Android Architecture Components. You can find the corresponding use and source code in LiveData Library.

SafeIterableMap has the following features:

  • Support key-value storage, with linked list implementation, simulated into Map interface
  • Support in the process of traversing the delete any element, not trigger ConcurrentModifiedException
  • Non-thread-safe

There are almost no practical scenarios for this data structure, because iterator.remove () is basically enough to remove elements in a loop. However, there are many tricks in SafeIterableMap that are worth learning.

Use linked lists to implement the Map interface

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;
}
Copy the code

Read operations start with a ab initio pointer and work backwards until the corresponding key is found. Write operations are directly tail-inserted into the list.

Delete elements iteratively

  1. Write down the Iterator whenever it needs to be iterated over
  2. Notify all iterators iterating when an element is deleted
  3. Iterator is notified to correct the next element
  4. The written Iterator is a weak reference in case of a memory leak at the end of the iteration

Take a look at the related implementation of Iterator:

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

    / /...
    
    @Override
    public boolean hasNext(a) {
        returnmNext ! =null;
    }

    // This method is called whenever an element is deleted, notifying entry that it has been deleted
    @Override
    public void supportRemove(@NonNull Entry<K, V> entry) {
        if (mExpectedEnd == entry && entry == mNext) {
            mNext = null;
            mExpectedEnd = null;
        }

        if (mExpectedEnd == entry) {
            mExpectedEnd = backward(mExpectedEnd);
        }
        // When the last element is removed, the tail pointer is corrected to the previous position

        // When deleting the next element, move the mNext pointer to the next element
        if(mNext == entry) { mNext = nextNode(); }}/ /...
}
Copy the code

Safe traversal is achieved by correcting the last pointer and the pointer to the next element in the supportRemove(Entry

removedEntry) method. How does the remove method notify each Iterator:
,v>

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(a) {
    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); }}/ /...
}
Copy the code

When a Map needs to be traversed, the obtained Iterator is put into a WeakHashMap, and when the Map needs to remove elements, all iterators in the WeakHashMap are notified. The trick here is to use WeakHashMap instead of List

, the disadvantage is that only the content of key part is used, the memory of value part is abandoned, but the greater advantage is that we do not need to maintain and delete the iterator that has been GC. WeakHashMap can help clean up entries whose key has been reclaimed.

SafeIterableMap is perfectly appropriate for LiveData. Because LiveData usually does not have a large number of subscribers, using linked lists for storage saves a lot of memory space compared to HashMap. And SafeIterableMap has O(1) inserts and traversals similar to HasMap, so it’s no less fast (minus the hash). So SafeIterableMap is great in situations where there are few elements and randomAccess is not needed.

The most suitable data structure is the best.