.jpg)
linkedhashmap與hashmap的區(qū)別在于前者維護(hù)插入順序，后者不保證順序。1.linkedhashmap繼承hashmap并用雙向鏈表記錄順序，遍歷時按插入順序訪問；2.hashmap查找效率更高但無序；3.當(dāng)需要順序或?qū)崿F(xiàn)lru緩存時應(yīng)使用linkedhashmap；4.linkedhashmap通過accessorder參數(shù)和removeeldestentry方法支持lru策略；5.其迭代性能略低于hashmap但空間開銷稍大。
LinkedHashMap在Java中主要作用是提供一個可以記住鍵值對插入順序的Map實(shí)現(xiàn)。這意味著當(dāng)你遍歷LinkedHashMap時，你會按照元素被添加到Map中的順序訪問它們。這在某些需要維護(hù)元素順序的場景下非常有用。
保持插入順序的Map實(shí)現(xiàn)
LinkedHashMap繼承自HashMap，但它通過維護(hù)一個雙向鏈表來記錄元素的插入順序。因此，它在HashMap的基礎(chǔ)上增加了順序性。
立即學(xué)習(xí)“Java免費(fèi)學(xué)習(xí)筆記（深入）”；
LinkedHashMap與HashMap的區(qū)別是什么？什么時候應(yīng)該使用LinkedHashMap？
HashMap不保證元素的順序，而LinkedHashMap保證元素的插入順序。當(dāng)你需要按照元素插入的順序來遍歷Map時，應(yīng)該使用LinkedHashMap。例如，LRU緩存的實(shí)現(xiàn)就非常適合使用LinkedHashMap。HashMap查找效率更高（平均情況下），但是不保證順序。LinkedHashMap在迭代時會有額外的開銷，因?yàn)樗枰S護(hù)鏈表。
具體來說，如果你的應(yīng)用場景對順序沒有要求，且性能是首要考慮因素，那么HashMap可能是更好的選擇。但如果順序很重要，或者你需要實(shí)現(xiàn)一些特殊的緩存策略（如LRU），那么LinkedHashMap就是理想的選擇。
LinkedHashMap是如何實(shí)現(xiàn)保持插入順序的？
LinkedHashMap內(nèi)部維護(hù)了一個雙向鏈表，它連接了所有Map中的Entry。每次插入或訪問元素時，LinkedHashMap會更新這個鏈表，以保證鏈表中元素的順序與插入順序一致。
具體來說，LinkedHashMap內(nèi)部的Entry類除了包含key、value和hash值外，還包含before和after兩個指針，分別指向鏈表中的前一個和后一個Entry。當(dāng)put一個新的鍵值對到LinkedHashMap中時，新的Entry會被添加到鏈表的末尾。當(dāng)訪問一個已存在的鍵值對時，如果AccessOrder設(shè)置為true（默認(rèn)是false，即保持插入順序），那么這個Entry會被移動到鏈表的末尾。
如何使用LinkedHashMap實(shí)現(xiàn)一個簡單的LRU緩存？
LRU (Least Recently Used) 緩存是一種常見的緩存淘汰策略，它會移除最近最少使用的元素。使用LinkedHashMap可以很容易地實(shí)現(xiàn)一個LRU緩存。
import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrder = true this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } public static void main(String[] args) { LRUCache<String, Integer> cache = new LRUCache<>(3); cache.put("A", 1); cache.put("B", 2); cache.put("C", 3); System.out.println(cache); // {A=1, B=2, C=3} cache.get("A"); System.out.println(cache); // {B=2, C=3, A=1} cache.put("D", 4); System.out.println(cache); // {C=3, A=1, D=4} B被移除了 } }
這段代碼的關(guān)鍵在于LinkedHashMap的構(gòu)造函數(shù)中的accessOrder = true，以及重寫removeEldestEntry方法。當(dāng)accessOrder為true時，每次訪問元素都會將其移動到鏈表末尾。removeEldestEntry方法會在每次put新元素時被調(diào)用，如果返回true，則會移除鏈表頭部的元素，也就是最久未使用的元素。
LinkedHashMap的性能如何？與HashMap相比有什么差異？
LinkedHashMap在插入和刪除操作上的性能與HashMap相似，都是O(1)（平均情況下）。但是，由于LinkedHashMap需要維護(hù)一個雙向鏈表，所以在迭代時會有額外的開銷。HashMap的迭代時間復(fù)雜度是O(capacity)，而LinkedHashMap的迭代時間復(fù)雜度是O(size)，其中capacity是HashMap的容量，size是Map中元素的數(shù)量。因此，當(dāng)Map中的元素數(shù)量遠(yuǎn)小于容量時，LinkedHashMap的迭代性能可能會更好。
總的來說，如果對順序有要求，且Map中的元素數(shù)量不大，那么LinkedHashMap的性能是可以接受的。但如果對性能要求非常高，且不需要保證順序，那么HashMap可能更適合。另外，需要注意的是，LinkedHashMap的空間復(fù)雜度略高于HashMap，因?yàn)樗枰~外的空間來存儲鏈表節(jié)點(diǎn)。
.png)
