LinkedHashMap、WeakHashMap和ConcurrentHashMap

1 LinkedHashMap

1.1 存储结构

1. 继承自 HashMap，因此具有和 HashMap 一样的快速查找特性；

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

2. 内部维护了一个双向链表，用来维护插入顺序或者 LRU 顺序；

/*** The head (eldest) of the doubly linked list.*/
transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/
transient LinkedHashMap.Entry<K,V> tail;

3. accessOrder 决定了顺序，默认为 false，此时维护的是插入顺序;

final boolean accessOrder;

4. LinkedHashMap 最重要的是以下用于维护顺序的函数，它们会在 put、get 等方法中调用;

void afterNodeAccess(Node<K,V> p) {
     }
void afterNodeInsertion(boolean evict) {
     }

1.2 afterNodeAccess()

如果 accessOrder 为 true，即指定为 LRU 顺序，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。

void afterNodeAccess(Node<K,V> e) {
     // move node to lastLinkedHashMap.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;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {
    p.before = last;last.after = p;}tail = p;++modCount;}
}

1.3 afterNodeInsertion()

1. 在 put 等操作之后执行，当 removeEldestEntry() 方法返回 true 时会移除最晚的节点，也就是链表首部节点first;
2. evict 只有在构建 Map 的时候才为 false，在这里为 true;

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

3. removeEldestEntry() 默认为 false，如果需要让它为 true，需要继承 LinkedHashMap 并且覆盖这个方法的实现，这在实现 LRU 的缓存中特别有用，通过移除最近最久未使用的节点，从而保证缓存空间足够，并且缓存的数据都是热点数据;

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

1.4 LRU 缓存

以下是使用 LinkedHashMap 实现的一个 LRU 缓存：

• 设定最大缓存空间 MAX_ENTRIES 为 3；
• 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
• 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除;

public class LRUCache<K,V> extends LinkedHashMap<K,V>{
    private static final int MAX_ENTRIES = 3;LRUCache(){
    super(MAX_ENTRIES,0.75f,true);}/*** removeEldestEntry() 默认为 false，* 如果需要让它为 true，需要继承 LinkedHashMap 并且覆盖这个方法的实现，* 这在实现 LRU 的缓存中特别有用，通过移除最近最久未使用的节点，* 从而保证缓存空间足够，并且缓存的数据都是热点数据。*/@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;}public static void main(String[] args) {
    LRUCache<Integer,String> cache=new LRUCache<>();cache.put(1, "a");cache.put(2, "b");cache.put(3, "c");cache.get(1); //LRU 键值1被访问过了，则最近最久未访问的就是2cache.put(4, "d");System.out.println(cache.keySet());}
}

[3, 1, 4]

2 WeakHashMap

2.1 存储结构

1. WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference关联的对象在下一次垃圾回收时会被回收；
2. WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收；

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

2.2 ConcurrentCache

• Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能;

• ConcurrentCache 采取的是分代缓存：

  1. 经常使用的对象放入 eden 中，eden 使用 ConcurrentHashMap 实现，不用担心会被回收；
  2. 不常用的对象放入 longterm，longterm 使用 WeakHashMap 实现，这些老对象会被垃圾收集器回收;
  3. 当调用 get() 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收;
  4. 当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象;

public final class ConcurrentCache<K, V> {
    private final int size;private final Map<K, V> eden;private final Map<K, V> longterm;public ConcurrentCache(int size) {
    this.size = size;this.eden = new ConcurrentHashMap<>(size);this.longterm = new WeakHashMap<>(size);}public V get(K k) {
    V v = this.eden.get(k);if (v == null) {
    v = this.longterm.get(k);if (v != null)this.eden.put(k, v);}return v;}public void put(K k, V v) {
    if (this.eden.size() >= size) {
    this.longterm.putAll(this.eden);this.eden.clear();}this.eden.put(k, v);}
}

3 ConcurrentHashMap

3.1 简介

ConcurrentHashMap和HashMap的实现方式类似，不同的是它采用分段锁的思想支持并发操作，因此是线程安全的。

3.2 减小锁粒度

1. 减小锁粒度指通过缩小锁定对象的范围来减少锁冲突的可能性，最终提高系统的并发能力；
2. 减小锁粒度是一种削弱多线程锁竞争的有效方法，ConcurrentHashMap并发下的安全机制就是基于该方法实现的；
3. 如果为了线程安全对整个HashMap加锁，虽然可以实现线程安全，但同时意味着只能有一个线程操作HashMap，效率上会大打折扣；
4. 而ConcurrentHashMap在内部细分为若干个小的HashMap，即Segment，默认情况下为16个，对每个Segment都单独加锁，提高了并发度，Segment的个数即为锁的并发度；

3.3 ConcurrentHashMap的实现

1. ConcurrentHashMap内部包含了一个Segment数组，Segment和HashMap类似，是数组和链表结构；
2. 每个Segment里包含并守护一个HashEntry数组，每个HashEntry是一个链表，在对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁；
3. 在操作ConcurrentHashMap时，如果需要在其中添加一个新的数据，并不是将整个HashMap加锁，而是先根据HashCode查询该数据应该被存放在哪个Segment，然后对该Segment加锁并完成put操作；
4. 在多线程环境下，如果多个线程同时进行put操作，则只要加入的数据被存放在不同的Segment中，在线程间就可以做到并行的线程安全；