Java集合框架2LinkedSHashMap

LinkedHashMap的定义

• 1 以jdk7为准进行说明

package java.util;
import java.io.*;
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
}

• 2 可以看到LinkedHashMap继承了HashMap，所以同样适用Hash算法决定Entry在table中的索引；同时LinkedHashMap的Entry是双向链表实现的，保证了迭代顺序和存放顺序一致。

LinkedHashMap的数据结构

• 1 通过下面代码来演示LinkedHashMap的用法

Map<String,Integer> map = new LinkedHashMap<>();
        map.put("s1", 1);
        map.put("s2", 2);
        map.put("s3", 3);
        map.put("s4", 4);
        map.put("s5", 5);
        map.put(null, 9);
        map.put("s6", 6);
        map.put("s7", 7);
        map.put("s8", 8);
        map.put(null, 11);
        for(Map.Entry<String,Integer> entry:map.entrySet())
        {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }
        System.out.println(map);

• 2 运行结果为：

s1:1
s2:2
s3:3
s4:4
s5:5
null:11
s6:6
s7:7
s8:8
{s1=1, s2=2, s3=3, s4=4, s5=5, null=11, s6=6, s7=7, s8=8}

• 3 通过结果可以看到，LinkedHashMap会记录插入的顺序，允许null的键值，当key值重复时，后面的会替换前面的。而且比HashMap多了一个头指针head（header指针是一个标记指针不存储任何数据）以及before和after两个指针。
  
• 4 当然，如果发生hash碰撞，和HashMap一样，相同的索引出会出现一个next指向的链表结构。

LinkedHashMap的其他特性

• 1 LinkedHashMap还有一个私有变量accessOrder（private final boolean accessOrder；），默认为false，表示按照插入顺序遍历；譬如开篇的例子中；如果设置为true则按照访问顺序遍历，即每一次访问也会被当做一次改变来被记录下来。

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

• 2 举个具体的例子
  1）代码如下

       Map<String,Integer> map = new LinkedHashMap<>(16,0.75f,true);
        map.put("s1", 1);
        map.put("s2", 2);
        map.put("s3", 3);
        map.put("s4", 4);
        map.put("s5", 5);
        map.put(null, 9);
        map.put("s6", 6);
        map.put("s7", 7);
        map.put("s8", 8);
        map.put(null, 11); // 此处null的key值set了第二次，也能改变数据存储的结果
        map.get("s6"); // 此处是get调用，也能改变数据存储的结果
        for(Map.Entry<String,Integer> entry:map.entrySet())
        {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }

2）运行结果

s1:1
s2:2
s3:3
s4:4
s5:5
s7:7
s8:8
null:11
s6:6

3）原因分析
LinkedHashMap工作在按照元素访问顺序排序的模式中，get()方法会修改LinkedHashMap中的链表结构，以便将最近访问的元素放置到链表的末尾。

• 3 该模式下的迭代方法只能使用上面的代码所示的方式，如果用下面的方式，则会抛异常。
  1）错误代码

for(Iterator<String> iterator = map.keySet().iterator();iterator.hasNext();) {
    String name = iterator.next();
    System.out.println(name+"->"+map.get(name));
}

运行结果：

s1->1
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(Unknown Source)
    at java.util.LinkedHashMap$KeyIterator.next(Unknown Source)
    at collections.map.LinkedHashMapTest.main(LinkedHashMapTest.java:33)

3）原因分析
ConcurrentModificationException异常一般会在集合迭代过程中被修改事抛出。不仅仅是LinkedHashMap,所有的集合都不允许在迭代器模式中修改集合的结构。一般认为，put()、remove()方法会修改集合的结构，因此不能在迭代器中使用。
但该模式下的get()方法同样会改变它的存储顺序，导致抛异常。

LinkedHashMap的典型应用

• 1 LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
• 2 实现代码如下：

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private static final long serialVersionUID = 7428629360694235373L;

    private final int maxCapacity;

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private final Lock lock = new ReentrantLock();

    public LRULinkedHashMap(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }

    @Override
    public boolean containsKey(Object key) {
        try {
            lock.lock();
            return super.containsKey(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        try {
            lock.lock();
            return super.size();
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        try {
            lock.lock();
            super.clear();
        } finally {
            lock.unlock();
        }
    }

    public Collection<Map.Entry<K, V>> getAll() {
        try {
            lock.lock();
            return new ArrayList<Map.Entry<K, V>>(super.entrySet());
        } finally {
            lock.unlock();
        }
    }

    public static void main(String[] args) {
        LRULinkedHashMap<String, String> lruMap = new LRULinkedHashMap<>(4);
        lruMap.put("first", "1");
        lruMap.put("second", "2");
        lruMap.put("third", "3");
        lruMap.put("fourth", "4");
                lruMap.put("fivth", "5");
        lruMap.get("fivth");
        lruMap.get("fourth");
        lruMap.get("third");        
                lruMap.get("second");

        for (Map.Entry<String, String> entry : lruMap.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }
}

• 3 运行结果

first:1
fourth:4
second:two
fivth:5

• 4 原因分析
  1）设置了maxCapacity，即该map只保存最多maxCapacity多个Entry。
  2）由于是访问模式，所以最近访问的被放到链表的尾部。