Кратко
LinkedHashMap наследует HashMap, его работа похожа на HashMap, и его структура аналогична. Самое большое отличие от HashMap заключается в том, что атрибуты «до» и «после» добавляются к записи узла, чтобы поддерживать порядок и сделать его упорядоченным. Пример, отсортированный по порядку размещения:
public static void main(String[] args) {
System.out.println("**********HashMap***********");
Map hashMap = new HashMap();
hashMap.put("Marvel", "漫威");
hashMap.put("Deadpool", "死侍");
hashMap.put("Hulk", "绿巨人");
hashMap.put("Thor", "雷神");
hashMap.put("Wolverine", "金刚狼");
for (Iterator it = hashMap.entrySet().iterator(); it.hasNext(); ) {
Map.Entry obj = (Map.Entry)it.next();
System.out.println(obj.getKey() + "-" +obj.getValue());
}
System.out.println("**********LinkedHashMap***********");
Map linkedHashMap = new LinkedHashMap();
linkedHashMap.put("Marvel", "漫威");
linkedHashMap.put("Deadpool", "死侍");
linkedHashMap.put("Hulk", "绿巨人");
linkedHashMap.put("Thor", "雷神");
linkedHashMap.put("Wolverine", "金刚狼");
for (Iterator it = linkedHashMap.entrySet().iterator(); it.hasNext(); ) {
Map.Entry obj = (Map.Entry)it.next();
System.out.println(obj.getKey() + "-" +obj.getValue());
}
}
вывод:
**********HashMap***********
Thor-雷神
Deadpool-死侍
Wolverine-金刚狼
Marvel-漫威
Hulk-绿巨人
**********LinkedHashMap***********
Marvel-漫威
Deadpool-死侍
Hulk-绿巨人
Thor-雷神
Wolverine-金刚狼
Анализ исходного кода
Поле LinkedHashMap
final boolean accessOrder; //是否按照访问顺序，true:访问顺序，false:插入顺序
transient LinkedHashMap.Entry head; //双向链表头节点
transient LinkedHashMap.Entry tail; //双向链表尾结点
/**
* 节点类继承了HashMap.Node，改成双向链表
* next表示桶上连接的Entry顺序
* before、after插入前后，插入顺序(维护双向链表)
*/
static class Entry extends HashMap.Node {
Entry before, after;
}
Метод строительства
Первые четыре порядка вставки по умолчанию, последний может указывать порядок, порядок доступа, когда accessOrder имеет значение true, порядок вставки, когда false
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化容量
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化容量和负载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//利用另一个map来构建
public LinkedHashMap(Map m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//指定初始化容量、负载因子和是否按照访问顺序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
положить метод
LinkedHashMap следует методу put HashMap, но переписывает его методы newNode(), afterNodeAccess(), afterNodeInsertion().
Node newNode(int hash, K key, V value, Node e) {
//调用LinkedHashMap的entry构造方法
LinkedHashMap.Entry p =
new LinkedHashMap.Entry(hash, key, value, e);
linkNodeLast(p);
return p;
}
/**
* 将新增节点置于链表尾部
*/
private void linkNodeLast(LinkedHashMap.Entry p) {
//获取当前链表尾部节点
LinkedHashMap.Entry last = tail;
//将p设为尾部节点
tail = p;
//若当前集合为空，p既是头节点又是尾节点
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
Как видно из приведенного выше исходного кода, linkedHashMap дополнительно поддерживает двусвязный список.
Рассмотрим метод afterNodeAccess(), в методе put, если в текущей коллекции есть ключевой объект для замены значения, будет вызван afterNodeAccess:
/**
* 将当前被访问的节点移至双向链表尾部
*/
void afterNodeAccess(Node e) { // move node to last
LinkedHashMap.Entry last;
//若accessOrder为true且原尾节点不是节点e
if (accessOrder && (last = tail) != e) {
//将节点e强转为双向链表节点p，获取p插入前后的节点
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
//因为需要将e置于链表尾部，所以将其after属性设为null
p.after = null;
//对于双向链表，若p的前驱节点为空，头节点设为p的后继
if (b == null)
head = a;
else
//否则将p前驱节点的后继节点设为p的后继节点
b.after = a;
//若p的后继节点不为null，将p的后继节点的前驱节点设为p的前驱节点
if (a != null)
a.before = b;
else
//否则将p的前驱节点设为尾结点
last = b;
//若原尾节点为空，将p设为头节点
if (last == null)
head = p;
else {
//否则将p的前驱节点改为原尾节点，原尾节点的后继节点改为p
p.before = last;
last.after = p;
}
//尾节点改为p
tail = p;
++modCount;
}
}
Когда в методе put добавляется новый узел, в конце будет вызываться метод afterNodeInsertion().Исходный код выглядит следующим образом:
/**
* 删除双向链表头节点
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//默认返回false
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
void afterNodeInsertion(boolean evict) и boolean removeEldestEntry(Map.Entry
получить метод
LinkedHashMap переопределяет свой метод get()
public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
По сравнению с операцией получения HashMap, у linkedHashMap есть еще одна операция: если accessOrder имеет значение true, будет вызван метод afterNodeAccess(). Выше упоминался метод afterNodeAccess(). Следует отметить, что modCount будет изменяться в этом методе, то есть при итерации LinkedHashMap. порядок итераций изменился.
метод удаления
LinkedHashMap следует методу HashMap remove(), но переписывает его метод afterNodeRemoval().
/**
* 将节点e从双向链表中删除
*/
void afterNodeRemoval(Node e) { // unlink
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
//待删除节点p的前驱后继节点都置空
p.before = p.after = null;
//若前驱节点为空，则将p后继节点设为头节点
if (b == null)
head = a;
//否则将p后继节点设为p前驱节点的后继节点
else
b.after = a;
//若p后继节点为空，则将p的前驱节点设为尾结点
if (a == null)
tail = b;
//否则p前驱节点设为p后继节点的前驱节点
else
a.before = b;
}
Реализовать буферный механизм с LinkedHashMap
FIFO
FIFO (First In First Out): первый пришел, первый ушел, то же самое, что и очередь. Например, покупатель, стоящий в очереди к кассе в супермаркете, выпишет товар первым и уйдет первым.
Реализация FIFO: LinkedHashMap по умолчанию (accessOrder имеет значение false) — сортировка в соответствии с сохраненными данными, удовлетворяющая принципу «первым пришел — первым обслужен», пример выглядит следующим образом:
public class FIFOCache extends LinkedHashMap {
private final int maxSize;//限制数据
public FIFOCache(int maxSize) {
super();//调用父类默认构造方法，accessOrder为false
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
Map fifoCache = new FIFOCache(10);//限定10个
for (int i = 0; i < 10; i++) {
fifoCache.put(i, i);
}
System.out.println("初始情况:" + fifoCache.toString());
fifoCache.put(6, 6);//访问已存在数据
System.out.println("已存在数据被访问后:" + fifoCache.toString());
fifoCache.put(10, 10);
System.out.println("新增一个数据后:" + fifoCache.toString());
}
}
вывод:
初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
已存在数据被访问后:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
新增一个数据后:{1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10}
Из результатов вывода он удовлетворяет правилу FIFO и сортируется в соответствии с порядком вставки.Если попадут какие-либо данные в кэш, правило FIFO не будет нарушено. Если добавляются данные вне кеша, первые вставленные данные будут удалены.
LRU
public class LRUCache extends LinkedHashMap {
private final int maxSize;
public LRUCache(int maxSize){
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
Map fifoCache = new LRUCache(10);//限定10个
for (int i = 0; i < 10; i++) {
fifoCache.put(i, i);
}
System.out.println("初始情况:" + fifoCache.toString());
fifoCache.put(6, 6);//访问已存在数据
fifoCache.get(3);
System.out.println("已存在数据被访问后:" + fifoCache.toString());
fifoCache.put(10, 10);
System.out.println("新增一个数据后:" + fifoCache.toString());
}
}
вывод:
初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
已存在数据被访问后:{0=0, 1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3}
新增一个数据后:{1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3, 10=10}
Из результатов вывода видно, что правила LRU соблюдены.
Суммировать
LinkedHashMap почти такой же, как HashMap.Самое большое отличие состоит в том, что класс узла имеет больше свойств до и после.Дополнительное обслуживание двусвязного списка используется для достижения порядка вставки (по умолчанию) или сортировки порядка доступа
Ссылаться на
https://blog.csdn.net/u012403290/article/details/68926201