死磕 java集合之HashSet源碼分析

来源:https://www.cnblogs.com/tong-yuan/archive/2019/04/14/HashSet.html
-Advertisement-
Play Games

HashSet怎麼保證添加元素不重覆? HashSet是否允許null元素? HashSet是有序的嗎? HashSet是同步的嗎? 什麼是fail-fast? ...


問題

(1)集合(Collection)和集合(Set)有什麼區別?

(2)HashSet怎麼保證添加元素不重覆?

(3)HashSet是否允許null元素?

(4)HashSet是有序的嗎?

(5)HashSet是同步的嗎?

(6)什麼是fail-fast?

簡介

集合,這個概念有點模糊。

廣義上來講,java中的集合是指java.util包下麵的容器類,包括和Collection及Map相關的所有類。

中義上來講,我們一般說集合特指java集合中的Collection相關的類,不包含Map相關的類。

狹義上來講,數學上的集合是指不包含重覆元素的容器,即集合中不存在兩個相同的元素,在java裡面對應Set。

具體怎麼來理解還是要看上下文環境。

比如,面試別人讓你說下java中的集合,這時候肯定是廣義上的。

再比如,下麵我們講的把另一個集合中的元素全部添加到Set中,這時候就是中義上的。

HashSet是Set的一種實現方式,底層主要使用HashMap來確保元素不重覆。

源碼分析

屬性

    // 內部使用HashMap
    private transient HashMap<E,Object> map;

    // 虛擬對象,用來作為value放到map中
    private static final Object PRESENT = new Object();

構造方法

public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 非public,主要是給LinkedHashSet使用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

構造方法都是調用HashMap對應的構造方法。

最後一個構造方法有點特殊,它不是public的,意味著它只能被同一個包或者子類調用,這是LinkedHashSet專屬的方法。

添加元素

直接調用HashMap的put()方法,把元素本身作為key,把PRESENT作為value,也就是這個map中所有的value都是一樣的。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

刪除元素

直接調用HashMap的remove()方法,註意map的remove返回是刪除元素的value,而Set的remov返回的是boolean類型。

這裡要檢查一下,如果是null的話說明沒有該元素,如果不是null肯定等於PRESENT。

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

查詢元素

Set沒有get()方法哦,因為get似乎沒有意義,不像List那樣可以按index獲取元素。

這裡只要一個檢查元素是否存在的方法contains(),直接調用map的containsKey()方法。

public boolean contains(Object o) {
    return map.containsKey(o);
}

遍歷元素

直接調用map的keySet的迭代器。

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

全部源碼

package java.util;

import java.io.InvalidObjectException;
import sun.misc.SharedSecrets;


public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    // 內部元素存儲在HashMap中
    private transient HashMap<E,Object> map;

    // 虛擬元素,用來存到map元素的value中的,沒有實際意義
    private static final Object PRESENT = new Object();

    // 空構造方法
    public HashSet() {
        map = new HashMap<>();
    }

    // 把另一個集合的元素全都添加到當前Set中
    // 註意,這裡初始化map的時候是計算了它的初始容量的
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    // 指定初始容量和裝載因數
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // 只指定初始容量
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    // LinkedHashSet專用的方法
    // dummy是沒有實際意義的, 只是為了跟上上面那個操持方法簽名不同而已
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    
    // 迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    // 元素個數
    public int size() {
        return map.size();
    }

    // 檢查是否為空
    public boolean isEmpty() {
        return map.isEmpty();
    }

    // 檢查是否包含某個元素
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    // 添加元素
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    // 刪除元素
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    
    // 清空所有元素
    public void clear() {
        map.clear();
    }

    // 克隆方法
    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    // 序列化寫出方法
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // 寫出非static非transient屬性
        s.defaultWriteObject();

        // 寫出map的容量和裝載因數
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // 寫出元素個數
        s.writeInt(map.size());

        // 遍歷寫出所有元素
        for (E e : map.keySet())
            s.writeObject(e);
    }

    // 序列化讀入方法
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 讀入非static非transient屬性
        s.defaultReadObject();

        // 讀入容量, 並檢查不能小於0
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // 讀入裝載因數, 並檢查不能小於等於0或者是NaN(Not a Number)
        // java.lang.Float.NaN = 0.0f / 0.0f;
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // 讀入元素個數並檢查不能小於0
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        // 根據元素個數重新設置容量
        // 這是為了保證map有足夠的容量容納所有元素, 防止無意義的擴容
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // 再次檢查某些東西, 不重要的代碼忽視掉
        SharedSecrets.getJavaOISAccess()
                     .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

        // 創建map, 檢查是不是LinkedHashSet類型
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // 讀入所有元素, 並放入map中
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

    // 可分割的迭代器, 主要用於多線程並行迭代處理時使用
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}

總結

(1)HashSet內部使用HashMap的key存儲元素,以此來保證元素不重覆;

(2)HashSet是無序的,因為HashMap的key是無序的;

(3)HashSet中允許有一個null元素,因為HashMap允許key為null;

(4)HashSet是非線程安全的;

(5)HashSet是沒有get()方法的;

彩蛋

(1)阿裡手冊上有說,使用java中的集合時要自己指定集合的大小,通過這篇源碼的分析,你知道初始化HashMap的時候初始容量怎麼傳嗎?

我們發現有下麵這個構造方法,很清楚明白地告訴了我們怎麼指定容量。

假如,我們預估HashMap要存儲n個元素,那麼,它的容量就應該指定為((n/0.75f) + 1),如果這個值小於16,那就直接使用16得了。

初始化時指定容量是為了減少擴容的次數,提高效率。

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

(2)什麼是fail-fast?

fail-fast機制是java集合中的一種錯誤機制。

當使用迭代器迭代時,如果發現集合有修改,則快速失敗做出響應,拋出ConcurrentModificationException異常。

這種修改有可能是其它線程的修改,也有可能是當前線程自己的修改導致的,比如迭代的過程中直接調用remove()刪除元素等。

另外,並不是java中所有的集合都有fail-fast的機制。比如,像最終一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是沒有fast-fail的。

那麼,fail-fast是怎麼實現的呢?

細心的同學可能會發現,像ArrayList、HashMap中都有一個屬性叫modCount,每次對集合的修改這個值都會加1,在遍歷前記錄這個值到expectedModCount中,遍歷中檢查兩者是否一致,如果出現不一致就說明有修改,則拋出ConcurrentModificationException異常。


歡迎關註我的公眾號“彤哥讀源碼”,查看更多源碼系列文章, 與彤哥一起暢游源碼的海洋。

qrcode


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

-Advertisement-
Play Games
更多相關文章
  • 新聞 "Hedgehog新站點" "Bolero 0.4發佈,增加遠程認證" "FsToolkit.ErrorHandling與Cvdm.ErrorHandling合併了" "F 里的3D圖形編程與游戲開發" "有趣的3D——瀏覽器里F 3D繪製" "F CNTK:變分自動編碼器例子——從2D隱空間 ...
  • 閱讀目錄 一、迭代器 1、迭代的概念 #迭代器即迭代的工具,那什麼是迭代呢? #迭代是一個重覆的過程,每次重覆即一次迭代,並且每次迭代的結果都是下一次迭代的初始值 代碼如下: 2、為何要用迭代器?什麼是可迭代對象?什麼是迭代器對象? 3、迭代器對象的使用 4、for迴圈 5、迭代器的優缺點 ...
  • 8、Bulk API 可以把多個 或`delete bulk API`中執行。這樣可以極大地提高索引速度。 API使用如下的JSON結構: 註意,最後一行數據必須要以 結尾。發送請求時,Content Type 標頭應設置為 application /x ndjson。 可以是 ,`create d ...
  • 一、引言 有了自動配置,springboot使web開發變得簡單,這個在springboot之旅中的第一篇中就有體現,實際的開發中當然不會這麼簡單,很多時候我們都需要自己去定製一些東西。web開發的東西比較多, 我們先掌握一些必要知識點,剩下的就是CRUD開發。 快速的創建一個springboot ...
  • 軟工作業2 ——實現一個能夠對文本文件中的單詞的詞頻進行統計的控制台程式 1.Github地址: https://github.com/wangshiyaoyao/WordCont 2.PSP表格 PSP2.1 Personal Software Process Stages 預估耗時(分鐘) 實際 ...
  • 異常 異常指的是程式中的不正常現象,一般異常都是由第三方數據的使用造成的。java中每種異常現象都會有一個對應的異常類。java對異常的處理方式就是終止程式。異常機制其實是為了幫助我們找到程式中的問題。異常指的並不是語法錯誤,語法錯了,編譯不通過,不會產生位元組碼文件,根本不能運行。 異常體系 jav ...
  • 今天我們繼續學習一下Numpy庫的學習 廢話不多說 ,開始講 比如我們現在想創建一個0-14這樣一個15位的數組 可以直接寫,但是很麻煩,Numpy中就給我們了一個方便創建的方法 numpy中有一個arange函數 運行這段代碼以後,可以得到如下結果 這裡我們可以看到,我先列印了一下,np.aran ...
  • 如果系統採用前後端分離的話,項目中就需要用到網關了,為了保證系統的安全性。 前後端項目簡單架構圖: 1. 基於網關實現白名單和黑名單攔截(防止惡意請求)、ip限流。 2. API介面實現Token授權驗證。 3. 使用MD5實現API介面驗證簽名,防止抓包篡改數據。 4. 實現API介面安全加密傳輸 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...