LinkedHashMap 保持有序迭代原理

之前一直有这个疑问,今天有时间就把源码看了看终于知道了原理。分享给大家也做笔记自己可以随后查看�?br style="box-sizing: inherit; -webkit-tap-highlight-color: transparent;">

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

  */
    private static class Entry<K,Vextends 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找到下一个迭代对象�?/p>

private transient Entry<K,V> header;

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

private abstract class LinkedHashIterator<Timplements 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�?/p>

然后每次迭代就通过after知道了下一个值,也就保持了有序�?/p>

相关文章
相关标签/搜索