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）由于是访问模式，所以最近访问的被放到链表的尾部。
