欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)之HashMap和HashSet

 更新時間:2023年03月24日 17:24:35   作者:程序猿教你打籃球  
這篇文章主要介紹了HashMap和HashSet,什么是哈希表以及HashMap的部分源碼解讀,想了解更多的小伙伴,可以參考閱讀本文

1、認識 HashMap 和 HashSet

在上期中,學(xué)習到 TreeMap 和 TreeSet,因為他們實現(xiàn)了 SortedMap 和 SortedSet 接口(本質(zhì)是 實現(xiàn)了 NavigableMap 和 NavigableSet),表示你創(chuàng)建的 TreeMap 或 TreeSet,必須是可排序的,也就是里面的元素是可比較的。

HashSet 的底層也是 HashMap,跟上期 TreeSet 大同小異,感興趣可以去看看源碼。

本期的 HashMap 和 HashSet 并沒有繼承上述所說的倆個接口,也即表示 HashMap 和 HashSet 中的 key 可以不重寫 compareTo 方法,由此也能得出,HashMap 與 HashSet 不關(guān)于 key 有序!

因為 Set 的底層就是 Map,那么這里我們就來驗證下 TreeSet 關(guān)于 key 有序,而 HashSet 不關(guān)于 key 有序。

public class Test {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();
        Set<String> hashSet = new HashSet<>();;
        treeSet.add("0012");
        treeSet.add("0083");
        treeSet.add("0032");
        treeSet.add("0057");
        System.out.print("TreeSet: ");
        for (String s : treeSet) {
            System.out.print(s + " ");
        }
        hashSet.add("0012");
        hashSet.add("0083");
        hashSet.add("0032");
        hashSet.add("0057");
        System.out.print("\nHashSet: ");
        for (String s : hashSet) {
            System.out.print(s + " ");
        }
    }
}

打印結(jié)果

為什么 HashMap 和 HashSet 不關(guān)于 key 有序呢?隨著往文章后續(xù)學(xué)習,你就會明白。

2、哈希表

2.1 什么是哈希表

之前的學(xué)習中,如果我們要查找一個元素,肯定是要經(jīng)過比較的,那有沒有一種辦法,可以不用經(jīng)過比較,直接就能拿到呢?

如果我們能構(gòu)造一種存儲結(jié)構(gòu),通過一種函數(shù) (hashFunc) 使元素的存儲位置與函數(shù)得出的關(guān)鍵碼之間能夠建立一一映射的關(guān)系,那么在查找某個元素的時候,就能通過這個函數(shù)來很快的找到該元素所在的位置。

這種函數(shù)就叫做哈希(散列)函數(shù),上述所說構(gòu)造出來的結(jié)構(gòu),叫做哈希表或者稱為散列表。

插入元素的時候:根據(jù)元素的關(guān)鍵碼,Person中關(guān)鍵碼可能是 age,這個具體情況具體分析,上述例子只是在插入整型的時候,通過關(guān)鍵碼通過哈希函數(shù)得到的 index 就是要插入的位置。

搜索元素的時候:對元素的關(guān)鍵碼,通過哈希函數(shù)得出的 index 位置,與該位置的關(guān)鍵碼比較,若倆個關(guān)鍵碼相同,則搜索成功。

采取上面的方法,確實能避免多次關(guān)鍵碼的比較,搜索的效率也提高的,但是問題來了,拿上述圖的情況來舉例子的話,我接著還要插入一個元素 15,該怎么辦呢?

2.2 哈希沖突

2.2.1 概念

接著上面的例子來說,如果要插入 15,使用哈希函數(shù)出來的 index = 5,但是此時的 5,下標的位置已經(jīng)有元素存在了,這種情況我們就稱為哈希沖突!

簡單來說,不同的關(guān)鍵字通過相同的哈希函數(shù)計算出相同的哈希地址(前面我們稱為 index),這種現(xiàn)象就被稱為哈希沖突或哈希碰撞! 

2.2.2 設(shè)計合理哈希函數(shù) - 避免沖突

如果哈希函數(shù)設(shè)計的不夠合理,是可能會引起哈希沖突的。

哈希函數(shù)的定義域,必須包括所需存儲的全部關(guān)鍵碼,哈希函數(shù)計算出來的地址,應(yīng)能均勻的分布在整個空間中,哈希函數(shù)不能設(shè)計太過于復(fù)雜。(工作中一般用不著我們親自設(shè)計)

常見的哈希函數(shù):

直接定制法:取關(guān)鍵字的某個線性函數(shù)作為哈希地址:hash = A * key + B, 這樣比較簡單,但是需要事先知道關(guān)鍵字的分布情況,適合于查找比較小且連續(xù)的情況。

除留余數(shù)法:設(shè)哈希表中允許的地址數(shù)為 m,取一個不大于 m 的數(shù),但接近或等于 m 的質(zhì)數(shù) p 作為除數(shù),即哈希函數(shù):hash = key % p,(p <= m)。

還有其他的方法感興趣可以查閱下相關(guān)資料,這兩個只是比較常見的方法了,當然,就算哈希函數(shù)設(shè)計的再優(yōu)秀,只是產(chǎn)生哈希的沖突概率沒那么高,但是仍然避免不了哈希沖突的問題,于是又有了一個降低沖突概率的辦法,調(diào)節(jié)負載因子。

2.2.3 調(diào)節(jié)負載因子 - 避免沖突

負載因子 α = 哈希表中元素個數(shù) / 哈希表的長度

哈希表的長度沒有擴容是定長的,即 α 與 元素的個數(shù)是成正比的,當 α 越大,即代碼哈希表中的元素個數(shù)越多,元素越多,發(fā)生哈希沖突的概率就增加了,因此 α 越小,哈希沖突的概率也就越小。所以我們應(yīng)該嚴格控制負載因子的大小,在 Java 中,限制了負載因子最大為 0.75,當超過了這個值,就要進行擴容哈希表,重新哈希(重新將各個元素放在新的位置上)。

所以負載因子越大,沖突率越高,我們就需要降低負載因子來變相的降低沖突率,哈希表中元素個數(shù)不能改變,所以只能給哈希表擴容了。

2.2.4 Java中解決哈希沖突 - 開散列/哈希桶

上面講述的都是避免沖突的方法,其實還往往不夠,不管怎么避免,還是會有沖突的可能性,那么通常我們解決哈希沖突有兩種辦法,分別是 閉散列 和 開散列 那么今天我們主要介紹 Java 中的開散列是如何解決的,感興趣可以下來自己了解下閉散列。

開散列又叫鏈地址法,或開鏈法,其實簡單來說就是一個數(shù)組加鏈表的結(jié)構(gòu)。如圖:

如上圖我們可得出,通過哈希函數(shù)得出的地址相同的關(guān)鍵碼放在一起,這樣的每個子集合稱為桶,接著桶中的元素用鏈表的結(jié)構(gòu)組織起來,,每個鏈表的頭節(jié)點存放在哈希表中。

3、HashMap 的部分源碼解讀

3.1 HashMap 的構(gòu)造方法

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
 
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
 
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
 
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;
    this.threshold = tableSizeFor(initialCapacity);
}

這幾個構(gòu)造方法相信都不難理解,第一個無參構(gòu)造方法,默認負載因子是 0.75,第二個構(gòu)造方法是你可以傳一個 Map 進去,構(gòu)造出一個新的 Map,負載因子仍然是默認的 0.75, 第三個構(gòu)造方法就是指定開辟的容量了(并不是你想象那樣簡單哦,面試題講解),這個很簡單,第四個構(gòu)造方法指定容量并且自定義負載因子。

在 HashMap 中,實例化對象的時候并不會默認開辟空間(指定空間除外)。

3.2 HashMap 是如何插入元素的?

前面對 HashMap 的講解,已經(jīng)大概了解了一點,但是 HashMap 底層的哈希函數(shù)是如何設(shè)定的呢?而且 Map 中不能有重復(fù)值的情況,是利用什么來判斷這兩個值是相同的值呢?

這里我們通過查看 put 方法的源碼,來帶大家一層層揭開這個面紗:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

進入到 put 方法,隨之調(diào)用了 putVal 方法,而第一個參數(shù)就是我們哈希函數(shù)的實現(xiàn)了,我們轉(zhuǎn)到hash() 方法中:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

通過哈希函數(shù),能看出,首先調(diào)用 key 的hashCode 方法,接著無符號右移 16 位,即將 key 的高16位 與 低 16位 異或得到的 hash 值,通過這個也就在說明,我們?nèi)绻亲远x類型的話,比如 Person,那么一定要重寫 hashCode 方法,不然則是調(diào)用 Object 里的 hashCode 方法了。

接著我們再往下看,putVal 方法里面的邏輯,這里代碼比較長,我們分段演示:

這里就是判斷哈希表是否為有元素,如果表為 null 或者 哈希表的長度為 0,就會初始化數(shù)組(Node類型的數(shù)組),即調(diào)用 resize() 方法。初始哈希表的長度是 16,臨界閾值為 16 * 0.75 = 12,也就是數(shù)組元素達到 12個即會擴容。往后走代碼:

這里作用是通過 hash 值得到索引 i,也就是數(shù)組的下標,判斷這個位置是否有元素了,如果沒有則直接 new 一個節(jié)點放到該處。反之走 else 就表示該數(shù)組下標已經(jīng)有元素了。

如果得到的 i 索引處有元素,則需要判斷當前下標元素的 hash 值是否與我們要插入的元素 hash 值相同,如果相同,接著判斷 下標元素的 key 與我們要插入元素的 key一樣,或者通過 equals 方法比較是一樣了,則表示是同一個元素,則不用插入了,e 保存這個已經(jīng)存在的元素。到這里也能發(fā)現(xiàn),這其實就是 Map 底層不能有重復(fù) key 的原因了。

那如果他們不相同的情況下,就會判斷該下標 i 的位置值是不是紅黑樹的節(jié)點(到了一定條件哈希桶中的元素會采用紅黑樹來組織數(shù)據(jù)),如果是,則采用紅黑樹的方式進行插入元素,這里我們就不往里面看了。

最后都不滿足的情況,也就是元素不相同,并且不是紅黑樹結(jié)構(gòu),則走后面的 else,首先這個 else 里面是個死循環(huán),要想退出,必須滿足兩個條件,① 找到了可以插入的地方,② 在哈希桶中發(fā)現(xiàn)了相同的元素。

比較該數(shù)組索引 i 下標的下一個節(jié)點,如果為 null,則直接插入該節(jié)點,如果鏈表長度大于8,則可能需要樹化,也就是轉(zhuǎn)換成紅黑樹,如果找到了相同的 key,則不用插入直接跳出循環(huán)。

上面的 else 走完后,如果存在添加相同的元素的時候,e 則不為 null,只需要將待添加元素的 value 值賦值給原本存在元素的 value 值即可,也就是更新一下元素的 value 值。afterNodeAccess 方法不用管,是使用 LinkedHashMap 實現(xiàn)的一個操作,這里并沒有使用。

最后部分:

這里有效元素個數(shù)自增,如果超過了數(shù)組長度,則重新判斷是否擴容(兩倍擴容)。 afterNodeInsertion 也不用管,LinkedHashMap中的,這里也沒有實際用途。

總結(jié):HashMap 的 put 方法,是根據(jù) key 的 hashCode 來計算 hash 值的,即我們要在自定義類型中重寫 HashCode 方法,再者,是根據(jù) equals 來判斷 key 是否相同,也表示著我們同時需要去重寫 equals 方法。

3.3 哈希表下的鏈表,何時會樹化?

在上述講解 put 方法的時候,發(fā)現(xiàn)插入元素的時候,數(shù)組索引位置的鏈表不止一個元素的時候會判斷是否要轉(zhuǎn)換成紅黑樹,那么具體要達到什么條件才能轉(zhuǎn)換成紅黑樹呢?我們直接看上述的 treeifyBin 方法即可。

樹化的前提是,鏈表的長度大于等于 8,就會樹化,因為是從 binCount 是從 0 開始的,所以 TREEIFY_THRESHOLD - 1。那么鏈表的長度大于等于 8,一定會從鏈表變成紅黑樹嗎?我們往后看:

第一個 if 當哈希表為空,或者表(數(shù)組)的長度小于64,只進行擴容即可,不會轉(zhuǎn)換成樹,當哈希表的長度大于 64,才有可能轉(zhuǎn)換成紅黑樹。

所以我們最終得出,HashMap 中哈希表下的鏈表,當鏈表長度大于等于 8,并且哈希表的長度大于等于 64 則會將此鏈表轉(zhuǎn)換成紅黑樹。 

4、相關(guān)面試題

4.1 鏈表轉(zhuǎn)換成紅黑樹如何比較?

前面我們學(xué)過 TreeMap TreeSet 底層就是紅黑樹,里面的元素必須是可比較的,那哈希表下的鏈表轉(zhuǎn)換成紅黑樹之后,沒有重寫 compareTo 怎么辦呢?這里會按照 key 的哈希值來進行比較,所以就算轉(zhuǎn)換成紅黑樹后,也不會關(guān)于 key 有序,再者可能只是哈希表其中一個索引位置下的結(jié)構(gòu)是紅黑樹,其他的仍然可能是鏈表。

4.2 hashCode 和 equals 的區(qū)別

hashCode 是虛擬出對象的地址,底層是 native 封裝的,即 C/C++實現(xiàn)的,而 equals 則是比較兩個對象是否相同。

當我們重寫 hashCode 的時候,是調(diào)用 Objects 里面的 hash 方法:

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

舉個例子,person1 和 person2 兩個對象的 hashCode 完全不一樣,但通過 hash 函數(shù)得到的 hash 值是相同的!而 hashCode 也是通過 hash 出來的,即對象的 hashCode 可以稱為 hash 值,所以得出,兩個對象的 hashCode 相同,但是這兩個對象不一定相同。

對于 persong1.equals(person2) 的值為 true 的情況,則代表這兩個對象里面的值都是一樣的,所以 equals 為 ture,兩個一模一樣的對象,最終的 hash 值肯定也是一樣的,并且 HashMap 也是調(diào)用 key 中的 equals() 方式來進行判斷是否有重復(fù)的 key 值。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age &&
            Objects.equals(name, person.name);
}

總結(jié):

兩個對象的 HashCode 相同,不代表這兩個對象完全相同。

兩個對象的 equals 的結(jié)果為 true,則代表這兩個對象完全相同。

4.3 以下代碼分配的內(nèi)存是多少?

public static void main(String[] args) {
    Map<Integer, Integer> map = new HashMap<>(25);
}

如果你天真的回答是 25 個數(shù)組元素大小,那就錯了,我們點進去構(gòu)造方法,發(fā)現(xiàn)是調(diào)用另一個構(gòu)造方法,在接著點進去,看到最后一行代碼即 tableSizeFor 方法:

這里就沒必要慢慢算了,實際就是給你找到一個離 cap 最近的 2 的 n 次方數(shù),取值范圍得大于等于 cap,例如上述 25 則實際開辟的就是 1  2  4  8  16  32  64....,那么上述代碼實際開辟的大小就是 32 個數(shù)組空間大小。

5、性能分析

雖然哈希表一直在和沖突做斗爭,但在實際使用過程中,我們認為哈希表的沖突率是不高的,沖突個數(shù)是可控的, 也就是每個桶中的鏈表的長度是一個常數(shù),所以,通常意義下,我們認為哈希表的插入/刪除/查找時間復(fù)雜度是 O(1) 。 

以上就是Java數(shù)據(jù)結(jié)構(gòu)之HashMap和HashSet的詳細內(nèi)容,更多關(guān)于HashMap和HashSet的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • Java中i++的一些問題總結(jié)

    Java中i++的一些問題總結(jié)

    這篇文章主要給大家介紹了關(guān)于Java中i++的一些問題,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
    2020-12-12
  • SpringBoot配置 Druid 三種方式(包括純配置文件配置)

    SpringBoot配置 Druid 三種方式(包括純配置文件配置)

    本文給大家分享在項目中用純 YML(application.yml 或者 application.properties)文件、Java 代碼配置 Bean 和注解三種方式配置 Alibaba Druid 用于監(jiān)控或者查看 SQL 狀況的相關(guān)知識,感興趣的朋友一起看看吧
    2021-10-10
  • Spring中@Value注解獲取不到配置值問題及解決

    Spring中@Value注解獲取不到配置值問題及解決

    這篇文章主要介紹了Spring中@Value注解獲取不到配置值問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-09-09
  • EL表達式的隱式對象_動力節(jié)點Java學(xué)院整理

    EL表達式的隱式對象_動力節(jié)點Java學(xué)院整理

    這篇文章主要介紹了EL表達式的隱式對象,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-07-07
  • 一文了解自定義MVC框架實現(xiàn)

    一文了解自定義MVC框架實現(xiàn)

    這篇文章主要為大家詳細介紹一下MVC框架自定義實現(xiàn)過程,文中的示例代碼講解詳細,對我們學(xué)習或工作有一定幫助,需要的可以參考一下
    2022-07-07
  • 一起聊聊Java中13種鎖的實現(xiàn)方式

    一起聊聊Java中13種鎖的實現(xiàn)方式

    分布式系統(tǒng)時代,線程并發(fā),資源搶占,"鎖"?慢慢變得很重要。那么常見的鎖都有哪些?本文就來和大家聊聊Java中13種鎖的實現(xiàn)方式,感興趣的可以了解一下
    2022-08-08
  • Java中的日期時間處理及格式化處理

    Java中的日期時間處理及格式化處理

    這篇文章主要介紹了Java中的日期時間處理及格式化處理方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-08-08
  • gateway基本配置教程

    gateway基本配置教程

    路由(Route)由一個ID,一個目標URI(最終路由到的url地址),一組斷言(匹配條件判斷)和一組過濾器定義,這篇文章主要介紹了gateway基本配置,需要的朋友可以參考下
    2023-05-05
  • SpringBoot與Spring中數(shù)據(jù)緩存Cache超詳細講解

    SpringBoot與Spring中數(shù)據(jù)緩存Cache超詳細講解

    我們知道內(nèi)存讀取速度遠大于硬盤讀取速度,當需要重復(fù)獲取相同數(shù)據(jù)時,一次一次的請求數(shù)據(jù)庫或者遠程服務(wù),導(dǎo)致在數(shù)據(jù)庫查詢或者遠程方法調(diào)用上小號大量的時間,最終導(dǎo)致程序性能降低,這就是數(shù)據(jù)緩存要解決的問題,學(xué)過計算機組成原理或者操作系統(tǒng)的同學(xué)們應(yīng)該比較熟悉
    2022-10-10
  • 詳解IntelliJ IDEA中TortoiseSVN修改服務(wù)器地址的方法

    詳解IntelliJ IDEA中TortoiseSVN修改服務(wù)器地址的方法

    這篇文章主要介紹了詳解IntelliJ IDEA中TortoiseSVN修改服務(wù)器地址的方法,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-12-12

最新評論