Java你可能不知道的事(3)HashMap

来源:http://www.cnblogs.com/yangqiangyu/archive/2016/03/14/5276629.html
-Advertisement-
Play Games

HashMap對於做Java的小伙伴來說太熟悉了。估計你們每天都在使用它。它為什麼叫做HashMap？它的內部是怎麼實現的呢？為什麼我們使用的時候很多情況都是用String作為它的key呢？帶著這些疑問讓我們來瞭解HashMap！ HashMap是一個用”KEY”-“VALUE”來實現數據存儲的類。


概述

HashMap對於做Java的小伙伴來說太熟悉了。估計你們每天都在使用它。它為什麼叫做HashMap？它的內部是怎麼實現的呢？為什麼我們使用的時候很多情況都是用String作為它的key呢？帶著這些疑問讓我們來瞭解HashMap！

HashMap介紹

1、介紹

HashMap是一個用”KEY”-“VALUE”來實現數據存儲的類。你可以用一個”key”去存儲數據。當你想獲得數據的時候，你可以通過”key”去得到數據。所以你可以把HashMap當作一個字典。 那麼HashMap的名字從何而來呢？其實HashMap的由來是基於Hasing技術(Hasing),Hasing就是將很大的字元串或者任何對象轉換成一個用來代表它們的很小的值，這些更短的值就可以很方便的用來方便索引、加快搜索。

在講解HashMap的存儲過程之前還需要提到一個知識點 
我們都知道在Java中每個對象都有一個hashcode()方法用來返回該對象的 hash值。HashMap中將會用到對象的hashcode方法來獲取對象的hash值。

2、關係

圖1展示了HashMap的類結構關係。

圖1

HashMap繼承了AbstractMap，並且支持序列化和反序列化。由於實現了Clonable介面，也就支持clone()方法來複制一個對象。今天主要說HashMap的內部實現，這裡就不對序列化和clone做講解了。

3、內部介紹

HashMap內部實現原理圖

上面的圖很清晰的說明瞭HashMap內部的實現原理。就好比一個籃子，籃子里裝了很多蘋果，蘋果里包含了自己的信息和另外一個蘋果的引用

1、和上圖顯示的一樣，HashMap內部包含了一個Entry類型的數組table， table里的每一個數據都是一個Entry對象。

2、再來看table裡面存儲的Entry類型，Entry類里包含了hashcode變數，key,value 和另外一個Entry對象。為什麼要有一個Entry對象呢？其實如果你看過linkedList的源碼，你可能會知道這就是一個鏈表結構。通過我找到你，你再找到他。不過這裡的Entry並不是LinkedList，它是單獨為HashMap服務的一個內部單鏈表結構的類。

3、那麼Entry是一個單鏈表結構的意義又是什麼呢？在我們瞭解了HashMap的存儲過程之後，你就會很清楚了，接著讓我們來看HashMap怎麼工作的。

HashMap的存儲過程

下麵分析一段代碼的HashMap存儲過程。（這裡只是作為演示的例子，並沒有真實的去取到了Hash值，如果你有需要可以通過Debug來得到key的Hash值）

        HashMap hashMap = new HashMap();//line1
        hashMap.put("one","hello1");//line2
        hashMap.put("two","hello2");//line3
        hashMap.put("three","hello3");//line4
        hashMap.put("four","hello4");//line5
        hashMap.put("five","hello5");//line6
        hashMap.put("six","hello6");//line7
        hashMap.put("seven","hello7");//line8

 

put操作的偽代碼可以表示如下：

public V put(K key, V value){
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //在table[i]的地方添加一個包含hash,key,value信息的Entry類。
}

 

下麵我們來看上面代碼的過程 
1、line1創建了一個HashMap，所以我們來看構造函數

/**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

空構造函數調用了它自己的另一個構造函數，註釋說明瞭構建了一個初始容量的空HashMap,那我們就來看它另外一個構造函數。

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

void init() {
    }

 

上面的代碼只是簡單的給loadFactor（其實是數組不夠用來擴容的）和threshold(內部數組的初始化容量),init()是一個空方法。所以現在數組table還是一個空數組。

 /**
     * An empty table instance to share when the table is not inflated.
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 

2、接下來到了line2的地方， hashMap.put(“one”,”hello1”);在這裡先提一下put方法源碼：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);//如果是空的，載入
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);獲取hash值
        int i = indexFor(hash, table.length);生成索引
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //遍歷已存在的Entry，如果要存入的key和hash值都一樣就覆蓋。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //添加一個節點
        addEntry(hash, key, value, i);
        return null;
    }

 

源碼很簡單，先判斷table如果是空的，就初始化數組table,接著如果key是null就單獨處理。否則的話就得到key的hash值再生成索引，這裡用了indexFor()方法生成索引是因為:hash值一般都很大，是不適合我們的數組的。來看indexFor方法

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

就是一個&操作，這樣返回的值比較小適合我們的數組。

繼續 line2put操作，因為開始table是空數組，所以會進入 inflateTable(threshold)方法，其實這個方法就是出實話數組容量，初始化長度是16,這個長度是在開始的構造方法賦值的。 
所以，現在空數組變成了長度16的數組了，就像下圖一樣。 
這裡寫圖片描述

接著由於我們的key不為null,到了獲取hash值和索引，這裡假設int hash = hash(key)和int i = indexFor(hash, table.length)生成的索引i為hash=2306996，i = 4;那麼就會在table索引為4的位置新建一個Entry，對應的代碼是addEntry(hash, key, value, i);到此結果如下圖： 
這裡寫圖片描述

新建的Entry內部的變數分別是,hash,key,value,和指向下一節點的next Entry。

3、繼續來看line3，line3和line2一樣，而且數組不為空直接hash(key)和index。所以直接看圖了 
這裡寫圖片描述

4、到了line4，這裡line4情況有點特殊，我們假設line4里key生成的hashcode產生的index也為4，比如hash(“three”) 的值 63281940 
hash&(15)產生的index為4。這種情況由於之前的位置已經有Entry了，所以遍歷Entry如果key和hashcode都相同，就直接替換，否則新添加一個Entry,來看一下對應源碼

public V put(K key, V value) {
        ...//一些代碼
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //for迴圈里判斷如果hash和key都一樣直接替換。

        modCount++;
        addEntry(hash, key, value, i);//沒有重覆的話就addEntry
        return null;
    }

 

上面代碼先判斷是否需要替換，不需要就調用了addEntry方法。來看addEntry

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }//判斷數組容量是否足夠，不足夠擴容

        createEntry(hash, key, value, bucketIndex);
    }

 

裡面又調用了createEntry

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
        //獲取當前節點，然後新建一個含有當前hash,key,value信息的一個節點，並且該節點的Entry指向了前一個Entry並賦值給table[index],成為了最新的節點Entry,同時將size加1。
    }

 

到這裡相信大家很清楚了。來看看圖： 
這裡寫圖片描述

5、到這裡之後的代碼都在上面的分析情況當中。我就不一一畫圖了，直接給出程式執行到最後的圖 
line5到line8

代碼hashcodeindexkeyvaluenext
hashMap.put(“four”,”hello4”); 54378290 9 four hello4 null
hashMap.put(“five”,”hello5”); 39821723 8 five hello5 null
hashMap.put(“six”,”hello6”); 86726537 4 six hello6 line4產生的Entry
hashMap.put(“seven”,”hello7”); 28789082 2 seven hello7 line3產生的Entry

結果圖如下： 
這裡寫圖片描述

到此put 操作就結束了,再來看看取

HashMap的取值過程

我們通過hashMap.get(K key) 來獲取存入的值，key的取值很簡單了。我們通過數組的index直接找到Entry，然後再遍歷Entry，當hashcode和key都一樣就是我們當初存入的值啦。看源碼：

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

 

調用getEntry(key)拿到entry ,然後返回entry的value,來看getEntry(key)方法

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

 

按什麼規則存的就按什麼規則取，獲取到hash,再獲取index,然後拿到Entry遍歷，hash相等的情況下，如果key相等就知道了我們想要的值。

再get方法中有null的判斷，null取hash值總是0,再getNullKey(K key)方法中，也是按照遍歷方法來查找的。

到這你肯定明白了為什麼HashMap可以用null做key。

瞭解的存儲取值過程和內部實現，其它的方法自己看看源碼很好理解，在此就不一一解釋了。

幾個問題

問題1、HashMap是基於key的hashcode的存儲的，如果兩個不同的key產生的hashcode一樣取值怎麼辦？ 
看了上面的分析，你肯定知道，再數組裡面有鏈表結構的Entry來實現，通過遍歷所有的Entry，比較key來確定到底是哪一個value;

問題2、HashMap是基於key的hashcode的存儲的，如果兩個key一樣產生的hashcode一樣怎麼辦？ 
在put操作的時候會遍歷所有Entry，如果有key相等的則替換。所以get的時候只會有一個

問題3、我們總是習慣用一個String作為HashMap的key，這是為什麼呢？其它的類可以做為HashMap的key嗎？ 
這裡因為String是不可以變的，並且java為它實現了hashcode的緩存技術。我們在put和get中都需要獲取key的hashcode，這些方法的效率很大程度上取決於獲取hashcode的，所以用String的原因：1、它是不可變的。2、它實現了hashcode的緩存，效率更高。如果你對String不瞭解可以看：Java你可能不知道的事－String

問題4、可變的對象能作為HashMap的key嗎？ 
可變的對象是可以當做HashMap的key的，只是你要確保你可變變數的改變不會改變hashcode。比如以下代碼

public class TestMemory {

    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        TestKey testKey = new TestKey();
        testKey.setAddress("sdfdsf");//line3
        hashMap.put(testKey,"hello");
        testKey.setAddress("sdfsdffds");//line5
        System.out.println(hashMap.get(testKey));
    }
}

public class TestKey {
    String name;
    String address;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getAddress() {
        return address;
    }

    public void setAddress(String address) {
        this.address = address;
    }

    @Override
    public int hashCode() {
        if (name==null){
            return 0;
        }
        return name.hashCode();
    }
}

 

上面的代碼line3到line5對象里的address做了改變，但是由於hashCode是基於name來生成的，name沒變，所以依然能夠正常找到value。但是如果把setAdress換成name,get就會返回null。這就是為什麼我們選擇String的原因。

到這裡相信你對HashMap內部已經非常清楚了，如果本篇文章對你有幫助記得點贊和評論，或者關註我，我會繼續更新文章，感謝支持！


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • C#基本語法學習（一）
    1、C#常量數據類型只能是原始數據類型：int、bool、char、double、string等。 2、C#中用訪問修飾符來說明變數的可訪問性，其值可以是：private、protected、internal、protected internal和public。 public：訪問不受限制，在任意地
  • Linq專題之提高編碼效率—— 第三篇 你需要知道的枚舉類
       眾所周知，如果一個類可以被枚舉，那麼這個類必須要實現IEnumerable介面，而恰恰我們所有的linq都是一個繼承自IEnumerable介面的匿名類， 那麼問題就來了，IEnumerable使了何等神通讓這些集合類型可以被自由的枚舉？？？   一： 探索IEnumerable 首先我們看看
  • WCF學習之旅——第一個WCF示例（二）
    我們可以通過代碼和配置文件的方式完成所有的服務寄宿工作。在Hosting項目中的Program.cs文件中的Main方法中，通過代碼實現對 BookService的WCF服務應用的寄宿實現。
  • 微軟Dynamics 使用葡萄城的Wijmo 5提供移動端用戶界面
    葡萄城近日與微軟公司達成合作，將Wijmo 產品線的HTML5和JaveScript 控制項融合到微軟Dynamics CRMOnline 2016版中
  • 怎麼解析json串在.net中
    以前知道一種解析json串的方法，覺得有點麻煩。就從別的地方搜到了另一種 string json = vlt.getlist(); JObject jo = JObject.Parse(json); var data = jo.getValue("data").ToObject<T>(); T就是對
  • 抓取分析網頁批量下載評書(上)之搜索有聲小說
    一、背景       母親喜歡聽評書，跟著廣播每天一集總覺得不過癮，於是2010年給她買了一個帶記憶體，能播放MP3的音箱，從此給她找評書便成了我的責任和義務。       一開始開始還好，單先生說的書多，找起來不困難， 但隨著聽的越多，加上聽慣了單先生的，其他人的母親都不喜歡，即便單先生的，類似白眉
  • 關於ASPOSE.WORD使用上的一個小問題
    最近實習期間負責了公司某個項目的一個功能模塊裡面的word導出功能，使用的是ASPOSE.WORD類庫，但是經常導出時候會遇到圖中的問題，大概意思就是兩個表格不能跨在一起，調試了好幾次還是沒發現具體的原因，但是有一個小技巧可以避免。就是在出現問題的結束域和開始域之間加個一個換行，就是回車，問題就解決
  • 報錯：LINQ to Entities 不識別方法
      大致是：var products = db.Products.Select(new ProductVm{Name=SomeMethod() });針對IQueryable集合的查詢操作會被LINQ Provider編譯成SQL語句，此時，是無法識別方法的。解決辦法：把數據放到記憶體中，再調用方法v
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類