• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • Java LinkedHashMap

    Java LinkedHashMap

    前言

    Map是我們在實際使用過程中常用的集合,HashMap在Java的實際開發中出鏡率很高,它通過hash算法實現了高效的非線程安全的集合,它有一個缺點就是,用戶插入集合的數據時無序,在我們需要一些有序的map的時候,我們就需要引入另外一個集合:LinkedHashMap。
    LinkedHashMap是一個有序的非線程安全的集合,它是HashMap的子類,基本特性跟HashMap一致。
    本文基于java 1.7

    LinkedHashMap的原理

    LinkedHashMap是如何實現有序的呢?它實際上實在HashMap的基礎上,維護了一個雙向鏈表,有這個鏈表來保證插入的有序性。
    LinkedHashMap增加了一個head節點,這個節點本省是空的,用來雙向鏈表的頭節點,后續的節點都在head節點之后插入。
    LinkedHashMap在HashMap Entry類的基礎上,增加了after和before用來標識鏈表的方向,Entry類見下:
    這里寫圖片描述
    LinkedHashMap的類圖:
    這里寫圖片描述

    LinkedHashMap的構造

    LinkedHashMap支持2種模式的雙向鏈表,一種就是我們常用的按照插入順序的鏈表,另外一種是LRU的鏈表,按照訪問順序排序。

        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            //accessOrder:true access-order; false insertion-order
            this.accessOrder = accessOrder;
        }

    插入

    LinkedHashMap使用父類的put方法,插入數據,基本流程一致,想參考的可以參看上一篇博客Java hashmap,只是在addEntry調用自己的實現:

        void addEntry(int hash, K key, V value, int bucketIndex) {
            //調用父類的addEntry,在父類的addEntry方法中會調用LinkedHashMap的createEntry來創建節點
            super.addEntry(hash, key, value, bucketIndex);
    
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }
        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;
            //重點部分,用來實現雙向鏈表,在尾部插入,由于header的before指向了尾部,這里調用header來進行插入
            e.addBefore(header);
            size++;
        }
    
        private void addBefore(Entry<K,V> existingEntry) {
            //existingEntry表示head節點,當前節點的后一個節點是head
                after  = existingEntry;
                //當前節點的前一個節點是head的前一個節點,就是尾節點
                before = existingEntry.before;
                //尾節點的后一個節點是當前插入的節點
                before.after = this;
                //將head.befor指向當前節點
                after.before = this;
            }

    通過addBefore,就構成了用來保存插入順序的雙向鏈表

    獲取

    LinkedHashMap的get跟它的父類基本一致,只是當accessOrder設置為true時,需要調整鏈表的順序。

        public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
            //記錄訪問順序,當accessOrder為true時生效,設置為false,不起作用
            e.recordAccess(this);
            return e.value;
        }
        void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    //true,LRU,調整訪問順序
                    lm.modCount++;
                    //在鏈表上將當前節點移除
                    remove();
                    //將當前節點重新添加到鏈表尾部
                    addBefore(lm.header);
                }
            }
    版權聲明:本文為joniers原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/joniers/article/details/73614674

    智能推薦

    Java集合之LinkedHashMap詳解

    簡介 LinkedHashMap繼承自HashMap,與HashMap有著類似的存儲結構,LinkedHashMap類聲明如下: 它繼承于HashMap,實現了Map接口。 LinkedHashMap是非線程安全的,只是用于單線程環境下。 LinkedHashMap與HashMap的核心結構都相同,但是HashMap是無序的,即我們通過迭代HashMap所得到的元素順序并不是它們最初放置到Hash...

    5.Java容器-LinkedHashMap

    LinkedHashMap概述        LinkedHashMap是HashMap的子類,內部使用雙向鏈表進行順序的維護,內部類Entry為HashMap的Node的子類;        底層是散列表和雙向鏈表,插入的順序是有序的(底層鏈表致使有序),和HashMap一樣,允許key和value為null,初始容...

    【Java集合】--LinkedHashMap源碼解析

    文章目錄 簡介 繼承體系 數據結構 源碼解析 1.屬性 2.構造方法 LinkedHashMap() LinkedHashMap(int initialCapacity) LinkedHashMap(int initialCapacity, float loadFactor) LinkedHashMap(Map<? extends K, ? extends V> m) LinkedHa...

    Java 集合 (8) -- LinkedHashMap 類

    文章目錄 1. 簡介 2. 繼承體系 3. 字段 4. 內部類 5. 構造器 6. 常用方法 7. 擴展 1. 簡介 HashMap 是無序的,也就是說,迭代 HashMap 所得到的元素順序并不是它們最初放置到 HashMap 的順序;HashMap 的這一缺點往往會造成諸多不便,因為在有些場景中,我們確需要用到一個可以保持插入順序的 Map。慶幸的是,JDK 為我們解決了這個問題,它為 Has...

    Java LinkedHashMap 和 LRU算法

    什么是LRU算法 LRU(Least Recently Used),也就是最近最少使用。一種有限的空間資源管理的解決方案,會在空間資源不足的情況下移除掉最近沒被使用過的數據,以保證接下來需要的空間資源。 在現在通用的操作系統中為了解決內存不足這個問題,提出了虛擬內存這種解決方案,其實虛擬內存也就是將機器的內存分為多個頁面(提個小問題,一個頁面包含了多少kb的空間?),內存中只存放當前需要的頁面信息...

    猜你喜歡

    Java - 提高-源碼(4) - LinkedHashMap

    LinkedHashMap源碼解析 源碼解析對應JDK1.7 JDK1.7源碼下載地址:JDK1.7源碼下載 JDK 源碼注釋 Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashM...

    Java_LinkedHashMap工作原理

    Hash table and linked list implementation of the Map interface,with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all ...

    Java集合類學習--LinkedHashMap

    概述 LinkedHashMap 繼承了 HashMap。LinkedHashMap內部維護了一個雙向鏈表,能保證元素按插入的順序訪問,也能以訪問順序訪問,可以用來實現LRU緩存策略。 LinkedHashMap可以看成是 LinkedList + HashMap。 LinkedHashMap 的類繼承結構圖: 我們知道 HashMap 是無序的,即迭代器的順序與插入順序沒什么關系。而 Linke...

    Java源碼系列3——LinkedHashMap

    什么是LinkedHashMap? LinkedHashMap 是 HashMap 的有序實現。LinkedHashMap 用一條雙向鏈表來維護順序,迭代的時候也使用自己實現的迭代器。 輸出 底層數組結構 HashMap的底層是由數組,鏈表,紅黑樹組成的。數組用來存儲節點,當出現哈希碰撞時使用鏈表存儲,當鏈表超過一定長度后會優化成紅黑樹。 LinkedHashMap 的底層除了繼承自 HashMa...

    hive 導出數據之一列多行,轉為一行多列

    需求:提取數據 說明:原數據是一列多行,需要轉化為一行多列 待查詢表為:temp_05 待查詢數據為: 待查詢數據如圖: 需要提取的數據表頭如下: 預定日期 昨日價格 前天價格 2018-02-01 2018-02-02 2018-02-03 2018-02-04 可用提數 SQL 數據如圖: 以下為嘗試過程 數據如圖: 數據如圖: 數據如圖: 數據如圖:...

    精品国产乱码久久久久久蜜桃不卡