LinkedHashMap介绍和源码分析

LinkedHashMap的介绍

1、LinkedHashMap的简介

HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。此外，LinkedHashMap可以很好的支持LRU算法，LruCache框架底层就是使用LikedHashMap实现的

2、LinkedHashMap的构造函数

//构造一个带指定初始容量和默认加载因子 (0.75) 的空 LinkedHashMap
public LinkedHashMap(int initialCapacity)   
//默认构造函数
public LinkedHashMap()   
//构造一个映射关系与指定 Map 相同的新 LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m)  
//造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap
public LinkedHashMap(int initialCapacity, float loadFactor) 

LinkedHashMap的数据结构

LinkedHashMap重要字段说明

head：双向链表头部
tail：双向列表尾部
accessOrder：true访问顺序排序 false 插入顺序排序
LinkedHashMap.Entry：继承HashMap.Entry在上面添加了前节点和后节点
其他重要字段跟HashMap一样

LinkedHashMap的重要方法和源码解析

//添加数据方法 添加数据数据方法跟前篇的HashMap相同 只是在每次结束后调用了处理LinkedHashMap的链表方法
//添加数据时 数据表中已存在当前数据  如果accessOrder为true 按访问顺序排序并且表尾不是这个相同的数据
void afterNodeAccess(Node<K,V> e) { // 移动已经存在的node到表尾 
        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;
        }
    }

//超过链表的最大返回 删除最老的元素  removeEldestEntry：1.8中默认返回false 一直不会执行
void afterNodeInsertion(boolean evict) { 
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

//重新了HashMap的newNode方法 每次创建新对象时 都会处理双向链表
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;
    }

//把新添加的元素追加到双向链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {  
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

//跟HashMap的get一样 只是如果是访问排序的话 会把访问的数据添加到表尾
public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

//删除数据 跟HashMap一样 只是删除过后 会调用链表的删除服务
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;
    }

LinkedHashMap的遍历方式跟HashMap一样，只是重写相关方法，调用的是其中双向链表 保证数据的有序性。