LinkedHashMap

今天有个需求，要求把某个公司和这个公司的有序产品放到map中存储，同时放入这个map中的公司时有顺序要求的——什么顺序放进去，什么顺序拿出来！
用普通的HashMap解决这个需求就不合适了。jdk提供的集合框架中的LinkedHashMap比较适合这个需求。那么他又是怎么实现这个功能的呢？一起来看看源码吧。

• LinkedHashMap的接口定义如下：

 

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

这里可以看出，LinkedHashMap就是HashMap的一个子类。

• Entry的关键区别：

•  
  • HashMap的Entry定义片段：

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        final int hash;
        Entry<K,V> next;

•  
  • LinkedHashMap的Entry定义片段：

    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // 可以看到在HashMap.Entry基础上，增加了下面两个属性！
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

• 再来看看HashMap的put方法

    public V put(K key, V value) {
        //从这里可以看出，HashMap是允许以null为key的存储的！
	if (key == null)
	    return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //LinkedHashMap override了下面这个方法！
        addEntry(hash, key, value, i);
        return null;
    }

 

• 那么put时，两个方法最大的区别就是上面的这个addEntry方法了，分别看一下：

    //HashMap中的方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        //这里可以看出，如果hash不均匀的话，会造成table中的某些entry元素比较庞大（因为里面会嵌套N层的子entry）
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

    //LinkedHashMap中的方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);
        
        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        //这里LinkedHashMap本身的removeEldestEntry方法是直接返回false的，但他的N个子类可能会采用不用的淘汰老元素的策略。
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold) 
                resize(2 * table.length);
        }
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        //注意：这里将新创建的元素插入到连表里header的前面（也就是Map的put方法中将entry加入双向链表的地方）
        e.addBefore(header);
        size++;
    } 

• 剩下就是看LinkedHashMap是如何实现这个按插入的顺序展示entrySet中的元素了：

//HashMap中的EntryIterator中的nextEntry方法
        Entry<K,V> nextEntry() { 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null) 
                throw new NoSuchElementException();
                
            Entry<K,V> n = e.next;
            Entry[] t = table;
            int i = index;
            while (n == null && i > 0)
                n = t[--i];
            index = i;
            next = n;
            return current = e;
        }

//LinkedHashMap重新定义了自己的内部类EntryIterator（当然其实HashMap中的EntryIterator也是private的），这里关键的不同就在这个nextEntry方法了
	Entry<K,V> nextEntry() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            //关键在这里，会将nextEntry指向当前元素的下一个元素！
            nextEntry = e.after;
            return e;
	}

 好了，关键原理找到了，其实其中还有很多细节，不过对理解原理不重要，可以暂时忽略！