LinkedHashMap 保持有序迭代原理

原创
2015/11/09 16:33
阅读数 1.4K

之前一直有这个疑问,今天有时间就把源码看了看终于知道了原理。分享给大家也做笔记自己可以随后查看。

linkedHashMap entry 继承了hashMap.Entry 然后定义了一个before与after用来存储当前key的上一个值引用和下一个值的引用。然后再addBefore的时候,把上一个值设置成当前对象引用。因为现在还不知道下一个是什么,所以默认也是当前对象引用。

  */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }


        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

然后linkedHashMap 定义了一个header变量用来存储第一个值的引用地址,这样迭代的时候就先迭代header,然后根据header 的next找到下一个迭代对象。

private transient Entry<K,V> header;

然后通过LinkedHashMapIterator的nextEntry方法就能看出nextEntry = e.after。 也就是说nextEntry是上一个值的下一个值。上一个值是当前对象,下一个值也就等于下一个对象,所以这就是它保持有序的原理。

private abstract class LinkedHashIterator<T> implements Iterator<T> {
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }


简单来说,就是第一个赋值是给header,第二次赋值是给header.after。

然后每次迭代就通过after知道了下一个值,也就保持了有序。

展开阅读全文
打赏
1
3 收藏
分享
加载中
更多评论
打赏
0 评论
3 收藏
1
分享
返回顶部
顶部