HashMap为了实现快速查询和存储数据，使用散列函数将键值映射到散列表中的位置。因此，HashMap中的数据都是无序的。而在一些场景中，使用HashMap无法满足要求。例如使用HashMap做缓存时，如果使用LRU（最近最少使用，将最久没有使用的数据调出缓存）更新算法，就需要记录下map中元素的访问顺序，将最长时间没有使用的元素踢出缓存。如果只使用HashMap的话，我们就需要做一些额外的工作了。LinkedHashMap比较适合应用于这样的场景。它是一个有序的HashMap,能记录元素的插入顺序或者访问顺序。
LinkedHashMap的常用方式如下：
LinkedHashMap<String, String> map = new LinkedHashMap<>();
map.put("tom", "apple");
map.put("jerry", "orange");
map.put("amy", "banana");
map.forEach((o, v) -> System.out.println(o + "->" + v));
output:
tom->apple
jerry->orange
amy->banana
从输出结果看出，迭代的顺序就是元素的插入顺序。如果想要记录元素的访问顺序，可以使用另一个构造函数：
LinkedHashMap<String, String> lkMap = new LinkedHashMap<>(4, 0.75f, true);
lkMap.put("tom", "apple");
lkMap.put("jerry", "orange");
lkMap.put("amy", "banana");
lkMap.get("jerry");
lkMap.get("tom");
lkMap.put("james", "pear");
lkMap.put("paul", "apple");
lkMap.forEach((o, v) -> System.out.println(o + "->" + v));
output:
amy->banana
jerry->orange
tom->apple
james->pear
paul->apple
这次的输出就是元素的访问顺序了。
LinkedHashMap是如何实现有序HashMap的呢？还是通过源码来看LinkedHashMap的实现方式。
先看看put方法的逻辑。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//LinkedHashMap重写了该方法。
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
/**
* 当map中的元素被修改或者调用的时候会执行这个方法。
* 如果map是访问顺序的, 这个方法就将entry移到header链表的尾部; 否则，什么都不做.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//判断访问顺序
if (lm.accessOrder) {
lm.modCount++;
//移除当前元素
remove();
//加到header链表尾部，链表是双向链表，尾部插入元素只要O(1)时间，
addBefore(lm.header);
}
}
/**
* 重写了createEntry方法.在表中加入Entry元素时，在header链表的尾部加入该元素。
*/
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
e.addBefore(header);
size++;
}
和HashMap一样，在LinkedHashMap中插入一个元素有两种可能，第一种是key值已经在原来的map中了；第二种是key值不在原来的map中。在第一种情况下，LinkedHashMap除了替换map中的旧值外，还会根据accessOrder决定是否记录元素的访问顺序。如果accessOrder是false的话，recordAccess方法什么都不做。反之，它将当前被访问的元素移除，并加入到header的前面(addBefore(lm.header);)。在第二种情况下，LinkedHashMap除了将元素存储到map中以外，还会将元素放到header的前面(e.addBefore(header);)。
这里header是什么？header的定义如下：
/**
* 双向链表的头指针.
*/
private transient Entry<K,V> header;
它是双向链表的头指针。这个双向链表是记录元素顺序的关键因素，当recordAccess是false的时候，header链表保存的是map中元素的插入顺序，新加入的元素保存到链表的尾部；当recordAccess是true的时候，header链表保存的是map中元素的访问顺序，最新访问的元素在链表的尾部。
之前一直疑惑，从链表中删除元素的复杂度是O(n)（主要是从链表中确定当前元素的复杂度就是O(n)）,例如recordAccess方法需要将被访问元素从当前header链表中移除，即remove方法，那需要先在链表中定位到当前的元素吧。实际上，remove方法只用O(1)时间就完成了删除操作。Remove方法的代码如下:
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}
它只是将当前节点的前后节点连接起来，也就是用O(1)时间就完成了删除操作。
remove方法为什么能如此高效的完成这些操作？还得看Entry的结构。LinkedHashMap中的Entry继承了HashMap的Entry，除此之外，它还增加了两个引用，指向当前entry元素的前后元素。具体代码如下：
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// 迭代时的双向链表.
Entry<K,V> before, after;
private void remove() {
//...
}
private void addBefore(Entry<K,V> existingEntry) {
//...
}
void recordAccess(HashMap<K,V> m) {
//...
}
在map中，这个Entry起到了两个作用，一是作为map中的元素，这个和在HashMap中的作用一样；另一个是header链表中的节点，用于记录元素的顺序。Entry的巧妙设计是在O(1)时间内完成删除操作的关键因素。例如在recoreAccess方法中，已经根据HashMap快速定位到当前元素，接下来只要操作当前元素的before, after引用就能完成链表的删除和添加操作。这种思想其实数据库索引的设计中也有体现（不详细展开了）。
相对来说，get方法就比较简单了。代码如下，不多做解释了。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
源码看下来，发现LinkedHashMap的关键是Entry结构的设计。LinkedHashMap的Entry在HashMap的Entry结构中添加了before, after引用，使得LinkedHashMap充分结合了HashMap快速查找的特点和链表有序的特点。
网友评论