LinkedHashMap特点
LinkedHashMap 是一个键有序的 HashMap，可以将 LinkedHashMap 理解为 LinkList + HashMap。
LinkedHashSet继承自HashSet，源码更少、更简单，唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。
LinkedHashMap 链表长度小于8时数据结构图为：
LinkedHashMap 链表长度大于等于8时转为红黑树：
LinkedHashMap结构
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
LinkedHashMap是HashMap的子类，自然LinkedHashMap也就继承了HashMap中所有非private的方法。
LinkedHashMap属性
// LinkedHashMap的基本数据结构 双向链表结构
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 链表头节点
transient LinkedHashMap.Entry<K,V> head;
// 链表尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 通过iterator访问时的顺序，true表示按照访问顺序，false表示按照插入顺序。
final boolean accessOrder;
成员变量中增加了 head 和 tail 两个变量，可以实现对插入元素的链表维护。
accessOrder 表示遍历 LinkedHashMap 时将按照什么顺序输出。
LinkedHashMap和HashMap的区别在于它们的基本数据结构上，LinkedHashMap的基本数据结构，也就是Entry如图：
LinkedHashMap与HashMap的Entry区别:
LinkedHashMap构造方法
// 构造方法1，构造一个指定初始容量和负载因子的、按照插入顺序的LinkedList
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
// 构造方法2，构造一个指定初始容量的LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// 构造方法3，用默认的初始化容量和负载因子创建一个LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap() {
super();
accessOrder = false;
}
// 构造方法4，通过传入的map创建一个LinkedHashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
// 构造方法5，根据指定容量、装载因子和键值对保持顺序创建一个LinkedHashMap
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedList方法分析
类源码方法层面的分析最好的方法是使用Debug一步步走一遍该方法。
get(Object key)方法
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)//直接调用了 HashMap 的 getNode 方法获取到对应的节点
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
------------------------------
// 将节点挪到链表尾部
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
// 如果 accessOrder 为true，且尾部节点不是 e 节点，那么将其挪到尾部
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;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
如果 accessOrder 为 true，那么表示访问时就要按照访问顺序去访问。而在 get 方法中，我们每访问一个节点，我们就会将该节点放入链表尾部，所以我们通过 iterator 访问链表时就是按照访问顺序得到的遍历（越早访问的越在后面）。这就是Java在LinkedHashMap中实现LRU的一个实例。使用LinkedHashMap实现一个LRU缓存也是LinkedHashMap的常见应用。
LRU 是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法。
LRU 缓存淘汰过程:
LRU算法
基于LinkedHashMap实现一个基于LRU算法的缓存设计示例：
package com.hpmp.utils;
import java.util.LinkedHashMap;
/**
* 基于LinkedHashMap实现一个基于LRU算法的缓存设计
* 自定义LruCache实现思路
* 1)有容量限制
* 2)容器满了要基于LRU算法移出元素
*/
class LruCache extends LinkedHashMap<String, Object> {
private static final long serialVersionUID = 1L;
/**
* 设计缓存的最大容量
*/
private int maxCapacity;
public LruCache(int maxCapacity) {
super(maxCapacity, 0.75f, true);
this.maxCapacity = maxCapacity;
}
/**
* 方法的返回值决定了容器在满的时是否移除元素.
* 当前集合元素数量大于设置的最大容量时:表示要移除
* 当前集合元素数量小于或等于设置的最大容量时:表示不移除
*/
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<String, Object> eldest) {
return size() > maxCapacity;
}
}
public class TestLruCache {
public static void main(String[] args) {
LruCache cache = new LruCache(3);
cache.put("A", 100);
cache.put("B", 200);
cache.put("C", 300);
System.out.println(cache);//{A=100, B=200, C=300}
cache.get("A");
System.out.println(cache);//{B=200, C=300, A=100}
cache.put("D", 400);
System.out.println(cache);//{C=300, A=100, D=400}
}
}
put(K key, V value)方法
LinkedHashMap 中并没有 put 方法的实现，直接使用HashMap的put方法实现。不过重写了put方法内部的newNode方法，afterNodeAccess方法，afterNodeInsertion方法。
/**
* 创建一个节点
* @param hash hash值
* @param key 键
* @param value 值
* @param e 下一个节点,这个是HashMap节点的属性
* @return
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//调用构造方法
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//维护链表
linkNodeLast(p);
return p;
}
/**
* 添加一个节点到末尾
* @param p 节点
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
//保存尾部节点
LinkedHashMap.Entry<K,V> last = tail;
//更新尾部节点
tail = p;
//判断之前的尾部节点是否为空
if (last == null)
//之前的尾部节点为空，说明还没有数据，设置一下头节点
head = p;
else {
//说明之前已经有数据了，将新的节点作为尾部节点连接起来
p.before = last;
last.after = p;
}
}
-----------------------------------
/**
* accessOrder为true时，将操作的节点移到链表尾部
* @param e 节点
*/
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
//accessOrder 这个参数是指在进行操作的时候，是否将操作的节点移动到链表的最后，默认false
//也就是说accessOrder为false的时候链表就是按照插入顺序维护的
//true的时候，会将最近使用的节点移动到链表最后
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;
else
//存在前置节点，将前置节点的后置节点连接到当前节点的下一个节点
b.after = a;
//判断后置节点是否为空
if (a != null)
//后置节点不为空，更新后置节点的前置节点
a.before = b;
else
//说明该节点就是尾部节点，设置前置节点为后节点
//a == null 说明p就是尾部节点？ 有点不清楚
last = b;
//统一更新尾部节点
if (last == null)
//说明只有这么一个节点
head = p;
else {
//将当前节点挂到链表末尾
p.before = last;
last.after = p;
}
//设置尾部节点
tail = p;
++modCount;
}
}
--------------------------
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//LinkedHashMap这个方法不生效
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
remove(Object key)方法
LinkedHashMap 中并没有 remove 方法的实现，直接使用HashMap的remove方法实现。不过重写其中的afterNodeRemoval方法。
/**
* 删除链表中的节点
*/
void afterNodeRemoval(Node<K,V> e) {
//获取当前节点的前置后置节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//清空前置后置节点
p.before = p.after = null;
if (b == null)
//前置节点为空，说明为头节点，更新头节点为后置节点
head = a;
else
//前置节点不为空，设置前置节点的后置节点为删除节点的后置节点
b.after = a;
if (a == null)
//后置节点为空，说明为尾部节点，更新尾部节点为其前置节点
tail = b;
else
//后置节点不为空，更新后置节点的前置节点
a.before = b;
}
LinkedHashMap的使用
public static void main(String[] args)
{
LinkedHashMap<String, String> linkedHashMap =
new LinkedHashMap<String, String>(16, 0.75f, true);//初始化
linkedHashMap.put("111", "111");//添加
linkedHashMap.put("222", "222");
linkedHashMap.put("333", "333");
linkedHashMap.put("444", "444");
loopLinkedHashMap(linkedHashMap);//遍历
linkedHashMap.get("111");//查询
loopLinkedHashMap(linkedHashMap);//遍历
linkedHashMap.put("222", "2222");
loopLinkedHashMap(linkedHashMap);//遍历
}
//遍历
public static void loopLinkedHashMap(LinkedHashMap<String, String> linkedHashMap)
{
Set<Map.Entry<String, String>> set = linkedHashMap.entrySet();
Iterator<Map.Entry<String, String>> iterator = set.iterator();
while (iterator.hasNext())
{
System.out.print(iterator.next() + "\t");
}
System.out.println();
}
注意这里的构造方法要用三个参数那个且最后的要传入true，这样才表示按照访问顺序排序。看一下代码运行结果：
111=111 222=222 333=333 444=444
222=222 333=333 444=444 111=111
333=333 444=444 111=111 222=2222
代码运行结果证明了两点：
- LinkedList是有序的
- 每次访问一个元素（get或put），被访问的元素都被提到最后面去了
网友评论