LinkedHashMap源码分析

LinkedHashMap在java1.6和1.7中的源码几乎一样，就不一一比较了，这里就以1.7为例。其次LinkedHashMap是HashMap的子类，所有很多方法就直接采用HashMap中的实现，所以在研究LinkedHashMap之前首先需要搞明白HashMap的实现。

1 LinkedHashMap简介

LinkedHashMap是HashMap的子类，众所周知LinkedHashMap在咋们印象中是顺序存放的，其实数据的保存还是跟HashMap的数据保存一模一样的，只不过LinkedHashMap在类中自己维护了一个指针，这个指针的实现就跟java1.6中LinkedList一样，维护了的是一个保存数据的头指针。同样这个链表是一个双向链表。

1 2	// LinkedHashMap 的数据头指针 private transient Entry<K,V> header;

同时还有一个属性 accessOrder，默认是false，可以通过构造方法指定

1 2	// 这个属性如果为true，那么就会按照最近最少访问进行排序 private final boolean accessOrder;

换句话说就是，如果 accessOrder为true的时候，当你访问了一个元素，那么这个元素就会排在链表的最后，以此类推。。最少访问的就在最前面，那么这个属性就是按照这种规则进行排序的。。后面会对此属性进行源码分析。

2 初始化

2.1 构造函数

构造函数都是采用了super来引用了HashMap中的构造方法，所以没什么难度。唯一不同就是对 accessOrder进行了赋值，这个属性构造方法默认全部是false，除非通过构造函数自己指定。

1	LinkedHashMap<String, String> linkedMap = new LinkedHashMap<String, String>(16, .75f, true);

2.2 init()方法

不知道大家在研究HashMap的时候，在HashMap的构造函数中有一个 init() 方法，这个方法在HashMap是空函数，但是在LinkedHashMap却得到了实现，所以在调用构造函数的同时也会调用这个init()方法。

// 初始化头指针
void init() {
      header = new Entry<>(-1, null, null, null);
      header.before = header.after = header;
}

3 操作元素

3.1 添加元素

LinkedHashMap在添加元素的时候内部会调用addEntry()方法，同样LinkedHashMap不仅仅要HashMap中的数据，同时还要维护自己的双向链表。

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);
        }
}
// 这个方法在父类中的 addEntry() 方法中调用了
void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        // 维护自己的双向链表，将创建的数据插在头指针的前面，即整个链表的最后
        e.addBefore(header);
        size++;
}

代码中很明确，在维护HashMap的数据同时也对LinkedHashMap中的双向链表数据进行了维护。
这里还有一个方法 removeEldestEntry()，这个方法的参数是header后面的数据，即当前最旧的数据。

1
2
3

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
      return false;
}

这个方法在LinkedHashMap中使用返回false，那这个protected方法有什么意义呢？这里就有一个就有一个设计思想，比如当你设计的LinkedHashMap中最大只能存在100个元素，那么这个方法就起作用了。

private static final int MAX_ENTRIES = 100;
// 覆盖这个方法, 当超过100个元素返回true, 然后代码中删除最旧的元素
protected boolean removeEldestEntry(Map.Entry eldest) {
     return size() > MAX_ENTRIES;
}

3.2 获取元素

获取元素比较简单，但是LinkedHashMap做了自己的实现。

public V get(Object key) {
     // 通过父类中的方法获取值
     Entry<K,V> e = (Entry<K,V>)getEntry(key);
     if (e == null)
         return null;
     // 这个方法 accessOrder 属性就起作用了 
     e.recordAccess(this);
     return e.value;
}

recordAccess的方法实现是，如果 accessOrder 属性为true，那么就将当前访问过的元素删除并插入到双向链表的最后。

void recordAccess(HashMap<K,V> m) {
     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
     // 如果为 true 执行
     if (lm.accessOrder) {
         lm.modCount++;
         remove();
         addBefore(lm.header);
     }
}

3.3 迭代元素

LinkedHashMap之所以迭代出来的元素是有序的，是因为keySet()方法和entrySet()方法都做了自己的实现，虽然所有的内部类都和HashMap中一样，只不过获取的数据方式变了，LinkedHashMap是从自己的双向链表中获取的。。。具体就不再表述了，看下源码其实很简单。

4 其他方法

4.1 containsValue(Object value)

1	public boolean containsValue(Object value) {}

这个方法还是考虑的很周到的，覆盖了父类中的方法，不再和HashMap中一样从Hash表中去循环迭代元素，而是从自己的双向链表中去迭代。这个就提高了访问的效率。

4.2 clear()方法

不说了，太简单。

public void clear() {
     super.clear();
     header.before = header.after = header;
}

5 总结

总体来说LinkedHashMap继承了HashMap，之所以有序是因为自己内部维护了一个双向链表，其他也没有就和HashMap基本类似。
同样和HashMap一样的是，当学完LinkedHashMap之后，LinkedHashSet基本就没必要看了，实现大部分代码都是采用了LinkedHashMap中的实现。
LinkedHashSet同样也继承自HashSet，HashSet在构造方法的参数中有一个 dummy 布尔参数，如果传入该值，那么HashSet就构造一个LinkedHashMap的实例，否则还是用HashSet自己默认的HashMap的实例。其他属于LinkedHashSet自己的代码基本没有。。。

1
2
3

public LinkedHashSet() {
    super(16, .75f, true);
}

// 从LinkedHashSet中的super调用的, 传入了dummy
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

// 如果不传dummy，就是HashSet自己的实现
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}