[数据结构与算法]JDK源码==》LinkedHashMap类学习

1、LinkedHashMap的主要成员变量及构造

public class LinkedHashMap<K,V>
        extends HashMap<K,V>
        implements Map<K,V> {
        
        // 双向链表的头部
        transient LinkedHashMap.Entry<K,V> head;
        // 双向链表的尾部
        transient LinkedHashMap.Entry<K,V> tail;
        // 此链接哈希映射的迭代排序方法:true用于访问顺序，false用于插入顺序
        final boolean accessOrder;
        
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
    	}
    	
    	public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
    	}
    	
    	public LinkedHashMap() {
            super();
            accessOrder = false;
    	}
    	
    	public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
    	}
        
        public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
    	}
    	...........................

}

2、get通过键名查找定的数据

	// 使用了HashMap中的内部类
	static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
		...................
    }
	public V get(Object key) {
        Node<K,V> e;
        // 使用了HashMap中的getNode方法查询对应的节点
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

3、put、replace、remove，由于该类没有重写对应的put、replace、remove方法，所以引用父类HashMap的方法，但是对应的功能方法里面执行的方法却有重写

	void reinitialize() {
        super.reinitialize();
        head = tail = null;
    }

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

    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        LinkedHashMap.Entry<K,V> t =
            new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

4、containsValue查询是否存在对应的Value值

	public boolean containsValue(Object value) {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }

5、clear清空

	public void clear() {
        super.clear();
        head = tail = null;
    }

6、LinkedHashMap与HashMap的关联

在HashMap类中可以看到有三个方法如下，没有实现方法体，但是在LinkedHashMap类中这三个方法有方法体，有对应的实现，该注释说明了允许LinkedHashMap的后期回调

在LinkedHashMap中这三个方法对应的重写方法

	void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }