读LinkedHashMap源码_JAVA_编程开发_程序员俱乐部

class="java" name="code">
//LinkedHashMap继承了HashMap,他和HashMap相比维持了一个插入时候的顺序。LinkedHashMap和HashMap之间也是一种模板设计模式的体现
//先看构造函数
public LinkedHashMap() {
        super();
	//排序规则false按照插入顺序读出,true最近最少使用可用于做LRU(Least Recently Used)缓存
        accessOrder = false;
    }

public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

 public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

//覆盖HashMap中的init钩子方法。
 void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

//在新增的时候会调用父类的方法
public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        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;
		//这句代码是关键,这也是个钩子方法.执行LinkedHashMap里面的recordAccess方法。
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
	//这句又被覆盖了
        addEntry(hash, key, value, i);
        return null;
    }

  void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
	    //如果是LRU模式
            if (lm.accessOrder) {
                lm.modCount++;
		//删除了自己
                remove();
		//在把自己重新加入队列中,这样headed.after永远都是在队列中最不常用的。
                addBefore(lm.header);
            }
        }

private void remove() {
            before.after = after;
            after.before = before;
        }


//调用remove()的时候会调用这个方法
void recordRemoval(HashMap<K,V> m) {
            remove();
        }

void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
	//如果需要删除存活时间最长的元素
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

//也是覆盖了父类的方法
void createEntry(int hash, K key, V value, int bucketIndex) {
      1  HashMap.Entry<K,V> old = table[bucketIndex];
      2  Entry<K,V> e = new Entry<>(hash, key, value, old);
      3  table[bucketIndex] = e;
         1,2,3的步骤和HashMap的操作一直
	 
        e.addBefore(header);
        size++;
    }

//这个覆盖了父类在扩容时候的元素迁移
void transfer(HashMap.Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
	//从header双向列表开始迁移比原来的transfer直接从entry[]上更加快,效率更高
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            if (rehash)
                e.hash = (e.key == null) ? 0 : hash(e.key);
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }
//构建了一个双向链表将元素插到了head的前面,head.before的后面,也就是按顺序插入
 private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }


//获取元素
public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

//回到初始状态
 public void clear() {
        super.clear();
        header.before = header.after = header;
    }
 
 //重新覆盖了containsValue方法直接从header开始遍历效率更高
 public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator

        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

//在调用map.entry遍历的时候覆盖了newEntryIterator方法。
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return 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;
        }
       //从head开始挨个遍历这样也就保证了FIFO顺序
        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;
        }
    }



/**
总结：LinkedHashMap继承了HashMap.内部维护了一个双向链表来保证可以按照顺序取出或者按照最少被使用来取出元素。
他的遍历方法直接从内部的双向链表遍历,这样效率更高。
这个类也是模板设计模式的最佳体现。几个钩子方法的使用很精妙。
*/