Java集合中的LinkedHashMap使用解析
前言
HashMap是根據(jù)key的hash值進行散列存儲的，每個節(jié)點間是無序的。而LinkedHashMap可以實現(xiàn)有序的存儲鍵值對。
LinkedHashMap是繼承于HashMap的，所以它的很多屬性和方法都是HashMap中的，那么它是怎么實現(xiàn)有序存儲的呢？
1、屬性
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
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);
}
}三個重要屬性:head、tail、accessOrder，一個重要結構：基礎Entry
從注釋中都可以看出他們的用途，head節(jié)點指向最先存進map的鍵值對，tail節(jié)點指向最后存進map的鍵值對
節(jié)點Entry繼承自HashMap的基礎節(jié)點Node，然后又新增了屬性before和after，看名字就知道它們是用來和前后節(jié)點串成雙向鏈表的。
accessOrder決定了鏈表中鍵值對是依照什么順序來相互串聯(lián)的，true表示鍵值對的訪問順序，false表示插入順序，默認是false。
自此，LinkedHashMap的思想就出來了，本身還是和HashMap一樣都是根據(jù)Hash求索引，散列等等。同時它自身的每個節(jié)點又根據(jù)訪問順序或者插入順序串聯(lián)成雙向鏈表，head、tail指向鏈表的頭和尾。
那么它是怎么實現(xiàn)有序存儲的呢？
2、方法
看下它的方法，發(fā)現(xiàn)它沒有覆寫put方法，只覆寫了get方法
看下HashMap中的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}關鍵就在newNode這個地方（當然newNode在HashMap中不止此處會用到），LinkedHashMap復寫了這個方法。
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;
}
// link at the end of list
//新生成的節(jié)點放到雙向鏈表的隊尾
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;
}
}所以，每個新的節(jié)點生成的時候，都會把它和前一個節(jié)點串聯(lián)起來，而且隊首head指向第一個生成的節(jié)點，隊尾tail指向最新生成的節(jié)點。
看個例子
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<>();
map.put("k1", "v1");
map.put("k2", "v2");
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
}執(zhí)行過程如下：
這里只做示意，如果后面hash沖突，需要在桶上加節(jié)點或樹節(jié)點，按照順序也是會和前后的節(jié)點進行串聯(lián)，和上圖的原理類似。
這是按照插入順序進行排序的。如果想按訪問順序進行排序，則需要調用另一個構造函數(shù)。
可以看到，當指定訪問順序進行排序的時候，最新被訪問的節(jié)點會被放到鏈表的末尾。
如何實現(xiàn)呢？看下HashMap的put方法
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("k1", "v1");
map.put("k2", "v2");
map.put("k3", "v3");
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
map.get("k2");
for (Map.Entry entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
//其他構造函數(shù)會將accessOrder設置為false
this.accessOrder = accessOrder;
}輸出結果為：
key:k1, value:v1
key:k2, value:v2
key:k3, value:v3
key:k1, value:v1
key:k3, value:v3
key:k2, value:v2
HashMap中專門定義了三個給LinkedHashMap覆寫的方法，用于做一些后處理。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }覆寫的這三個方法都是在進行完基本的鍵值對插入刪除操作后，對雙向鏈表進行調整。
如afterNodeInsertion方法就是在Hash數(shù)組插入新的Node節(jié)點后，根據(jù)緩存機制（removeEldestEntry默認是緩存機制不生效，可以覆寫實現(xiàn)自己的緩存機制）決定是否刪除雙向鏈表head節(jié)點所指向的節(jié)點。
當鍵值對第一次put進來時，如果是生成新的節(jié)點調用afterNodeInsertion，則此時和插入順序一致，該節(jié)點位于隊尾。當調用get方法時
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)//訪問順序排序會調用后處理，將節(jié)點調整到隊尾
afterNodeAccess(e);
return e.value;
}此時會調用afterNodeAccess方法，將訪問的這個節(jié)點調整到隊尾。
如果在put時，更新某個節(jié)點的value，此時也會調用afterNodeAccess，即實現(xiàn)了一旦某個節(jié)點被訪問（插入、獲取、更新）時，該節(jié)點被調整到隊尾。
刪除時，會調用afterNodeRemoval將節(jié)點從雙向鏈表中移除，和之前的原來類似，不再展開。
3、用途
LinkedHashMap能用來做什么呢，由于它自身維護了一個雙向鏈表，保證節(jié)點的順序是按照插入或者訪問的順序連接的，所以這種特性在某些場景下就很有用，比如LRU。
什么是LRU，Least Recently Used，最近最少使用。比如一個Map我最多允許存放10個鍵值對，那么當?shù)?1個鍵值對要插入的時候，我要把已有的10個中里使用頻率最低的一個移除。
@Slf4j
public class MapTest {
public static void main(String[] args) {
LRUExample<String, String> lruExample = new LRUExample<>(4);
int i = 0;
for (; i < 4; i++) {
lruExample.put("k" + i, "v" + i);
}
log.info("插入完4個鍵值對后");
Set<Map.Entry<String, String>> entries = lruExample.entrySet();
for (Map.Entry<String, String> entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
lruExample.get("k1");
log.info("訪問k1后");
for (Map.Entry<String, String> entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
lruExample.put("k5", "v5");
log.info("插入完第5個鍵值對后");
for (Map.Entry<String, String> entry : entries) {
log.info("key:{}, value:{}", entry.getKey(), entry.getValue());
}
}
}
class LRUExample<K, V> extends LinkedHashMap<K, V> {
final int maxSize;
LRUExample(int maxSize) {
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
}輸出結果為：
插入完4個鍵值對后
key:k0, value:v0
key:k1, value:v1
key:k2, value:v2
key:k3, value:v3
訪問k0后
key:k1, value:v1
key:k2, value:v2
key:k3, value:v3
key:k0, value:v0
插入完第5個鍵值對后
key:k2, value:v2
key:k3, value:v3
key:k0, value:v0
key:k5, value:v5
當插入到第5個時，此時訪問頻率最低的就是head節(jié)點指向的k1-v1，所以當k5-v5插入的時候，觸發(fā)了緩存清除時，k0-v0被移除，k5-v5加入到隊尾。
到此這篇關于Java集合中的LinkedHashMap使用解析的文章就介紹到這了,更多相關Java集合LinkedHashMap內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
spring boot集成mongodb的增刪改查的示例代碼
這篇文章主要介紹了spring boot集成mongodb的增刪改查的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
下面小編就為大家?guī)硪黄趈ava中的PO VO DAO BO POJO(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
本文主要介紹了Java反射機制的相關知識。具有很好的參考價值，下面跟著小編一起來看下吧2017-03-03
小時候經常在諾基亞上玩的一個小游戲-貪吃蛇，你還記得嗎？本篇帶你重溫一下把它實現(xiàn)，做的比較簡單,但還是可以玩的.感興趣的朋友快來看看吧2022-05-05
JDBC之PreparedStatement類中預編譯的綜合應用解析
SQL 語句被預編譯并存儲在 PreparedStatement 對象中。然后可以使用此對象多次高效地執(zhí)行該語句2013-07-07
Java開發(fā)SpringBoot集成接口文檔實現(xiàn)示例
這篇文章主要為大家介紹了Java開發(fā)SpringBoot如何集成接口文檔的實現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2021-10-10
這里為大家整理了Java的基礎語法學習筆記,包括關鍵詞、運算符與基本的流程控制語句寫法等,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了Java中包的概念和用法,結合具體案例形式分析了java包的概念、原理、使用方法及相關操作注意事項,需要的朋友可以參考下2019-09-09
SpringBoot項目報錯:"Error?starting?ApplicationContext....
這篇文章主要給大家介紹了關于SpringBoot項目報錯:“Error?starting?ApplicationContext.?To?display?the?conditions?report?re-run?...”的解決辦法,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2022-08-08
最新IntelliJ?IDEA?2022配置?Tomcat?8.5?的詳細步驟演示
這篇文章主要介紹了IntelliJ?IDEA?2022?詳細配置?Tomcat?8.5?步驟演示,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-08-08