思考LinkedHashMap

学习有序HashMap实现原理

挖掘背后实现，加深对java集合框架理解

demo书写

这时候打印的就是put时候的顺序，但是换成HashMap就是乱序的

LinkedHashMap<String,String> map=new LinkedHashMap();
        map.put("a","1");
        map.put("b","2");
        map.put("c","3");
        Iterator<Map.Entry<String,String>> iterator=map.entrySet().iterator();
        while(iterator.hasNext()){
            Log.d("TEST",iterator.next().getKey());
        }

分析put操作

发现LinkedHashMap本身没有写put逻辑，也就是直接用父类方法，HashMap的put方法。是不是很疑惑？
后来找了发现是因为

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

原来真正的原理是在这里，所以分析一下数据结构

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

这里和HashMap的结构几乎一样，但是多了2个指向前后的指针。
在插入节点的时候，根据linkNodeLast的方法分析，会将插入的节点成员变量before
赋值为当前last也就是tail，指向尾节点。也就是说每一次put的时候，把put对象的before设置成当前尾节点。把当前尾节点after设置成put对象。以后一个个加进来，顺序也就找到了。
感觉这里用到比较多的是链表，看这个源码最好对链表比较好的掌握，后面也分析比较方便一点

再看遍历逻辑：
迭代器学习
由于每一个Map都会用Set<Node>存储节点数据结构，所以我们这里找一下linkedHashMap内部节点数据结构是什么

 final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }

所以如果想看迭代怎么依次找出顺序的节点就应该找 LinkedEntryIterator

 final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

final LinkedHashMapEntry<K,V> nextNode() {
            LinkedHashMapEntry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }

哈哈哈，这里看出来就是一个个找到 LinkedHashMapEntry.after
所以迭代器就是迭代LinkedHashMapEntry成员变量after，至于after是什么时候赋值的。也就是put的时候。原来有序map是这么实现的啊，是不是很简单。