LinkedHashMap源码

​ LinkedHashMap是一个有序的map集合,他的特点就是在map的基础上增加了顺序从而让无序的map成为一个有序的集合,同时LinkedHashMap底层的实现也非常有意思。

一、继承树与构造方法

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

​ LinkedHashMap继承了HashMap,也就是说很多的Map接口LinkedHashMap自己并没有实现而是使用的HashMap的实现,当然他自己也重写了很多的方法。

// 默认的构造方法   
public LinkedHashMap() {
   
   
        super();
        accessOrder = false;
}

​ 从构造方法中可以看出LinkedHashMap使用super方法调用HashMap进行的初始化操作。

accessOrder:是否能改变顺序,如果设置位true,那么在修改数据和获取数据以后他会进入到链表的尾部一般该值我们都是使用默认的,大家也不要轻易的修改它

二、put方法添加数据

// 直接调用HashMap的put方法添加数据    
public V put(K key, V value) {
   
   
    return putVal(hash(key), key, value, false, true);
}

​ 从方法的调用来看LinkedHashMap和HashMap使用的是同一个方法那么LinkedHashMap是如何来维护插入的顺序的呢？

​ 主要是LinkedHashMap重写了HashMap中的newNode方法,在方法中除了创建一个Node节点以为还使用双链表的方式来维护插入的顺序。

    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); //向双链表中插入一个Entry节点对象
        return p;
    }

    //维护LinkedHashMap顺序的双链表
    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;
        }
    }

三、iterator迭代的时候如何保证顺序

// 迭代的代码
Iterator iterator = linkedHashMap.keySet().iterator();
while(iterator.hasNext()){
   
   
    Object next = iterator.next();
}
// 当调用next方法的时候会进入到LinkedHashMap重写的nextNode方法
final LinkedHashMap.Entry<K,V> nextNode() {
   
   
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    // 此处就是链表的遍历,从而保证了获取的顺序
    current = e;
    next = e.after;
    return e;
}

​ 从上面的代码我们可以看到他的key的迭代的时候并没有调用HashMap提供的那个方法进行迭代而是自己重写了nextNode方法,然后再nextNode方法中变量LinkedHashMap所维护的那个双链表,而该链表正好维护了插入的顺序,所以取出来的时候自己也是有序的。

四、fail fast机制

​ fail fast机制其实在很多的集合中都有这个机制,主要的表现就是如果我们在迭代的过程中删除了元素那么系统就会抛出ConcurrentModificationException的异常。

​ fail fast机制是如何实现这个概念的呢？

​ 一个线程要迭代一个集合的时候会首先获取他的modCount，并且再迭代的时候会一直不停的判断该值是否背修改了如果被修改了则会抛出并发修改异常。

final LinkedHashMap.Entry<K,V> nextNode() {
   
   
    LinkedHashMap.Entry<K,V> e = next;
    // 每次迭代都会检测modCount 是否背修改如果被修改则抛出并发修改异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;
    return e;
}

五、LinkedHashSet/TreeSet/HashSet底层实现

1. HashSet底层使用的是HashMap来实现的,只是只用到了他的key，value统一使用的是一个Object类型的对象,且HashMap是无序的所以HashSet也是无序的
2. TreeSet 底层使用的是TreeMap的key,同时可以传递一个Comparator接口进行排序
3. LinkedHashSet 底层使用的是LinkedHashMap所以该set是有序的且顺序是通过一个双向链表来实现的