Java之LinkedHashMap实现原理

LinkedHashMap是有序hashmap,有序是指可以按元素插入顺序或元素最近访问顺序(LRU)排列；

LinkedHashMap = 散列表 + 循环双向链表；

一、LinkedHashMap的构造函数

transient LinkedEntry<K, V> header;
private final boolean accessOrder;

public LinkedHashMap() {
    init();
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, false);
}

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

@Override 
void init() {
     header = new LinkedEntry<K, V>();
}

static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
    LinkedEntry<K, V> nxt;
    LinkedEntry<K, V> prv;
    /** Create the header entry */
    LinkedEntry() {
        super(null, null, 0, null);
        nxt = prv = this;
    }
    /** Create a normal entry */
    LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
      super(key, value, hash, next);
      this.nxt = nxt;
      this.prv = prv;
    }
}

1. 在 LinkedHashMap 的构造方法中，实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组;
2. LinkedHashMap 重写了父类HashMap的init() 方法，进行链表头节点的初始化操作；LinkedEntry是继承的HashMap类中的内部类HashMapEntry；
3. 额外可以增加 accessOrder 这个参数，如果不设置，默认为 false，代表按照插入顺序进行迭代；当然可以显式设置为 true，代表以访问顺序进行迭代；

二、LinkedHashMap按照访问顺序进行迭代的实现；

public V get(Object key) {
    if (key == null) {
        HashMapEntry<K, V> e = entryForNullKey;
        if (e == null)
            return null;
        if (accessOrder)
            makeTail((LinkedEntry<K, V>) e);
        return e.value;
    }
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];e != null; e = e.next) {
      K eKey = e.key;
      if (eKey == key || (e.hash == hash && key.equals(eKey))) {
        if (accessOrder)
          makeTail((LinkedEntry<K, V>) e);
        return e.value;
      }
    }
    return null;
}

private void makeTail(LinkedEntry<K, V> e) {
    // Unlink e
    e.prv.nxt = e.nxt;
    e.nxt.prv = e.prv;
    // Relink e as tail
    LinkedEntry<K, V> header = this.header;
    LinkedEntry<K, V> oldTail = header.prv;
    e.nxt = header;
    e.prv = oldTail;
    oldTail.nxt = header.prv = e;
    modCount++;
}

从代码可以看到当accessOrder设置为true时，会将最新访问的元素添加到双向链表的尾部，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失；

三、LinkedHashMap的迭代

1. 用与迭代hashmap的一样的方式通过获取key迭代；
2. 用与迭代Linkedlist的一样的方式通过头指针来迭代；
3. 这么设计的目的是为了快速查询，并且又保证了一定的迭代顺序；但是由于它多维护了一个双向链表故而会比较占资源；

四、LinkedHashMap的Lru缓存实现

最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法removeEldestEntry（在每次添加数据的时候会有一个判断，可以自行去看源码），默认是返回false，即不删除数据，可以对LinkedHashMap进行一些简单的扩展；

1. 普通实现

//当map中的元素个数大于cacheSize时，删除最老的数据（链表头部的元素）；
final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
          return size() > cacheSize;
      }
};

2. 如LruCache一样的扩展实现

public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_CACHE_SIZE;
    public LRUCache2(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
}