1、認(rèn)識(shí) HashMap 和 HashSet

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

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

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

因?yàn)?Set 的底層就是 Map，那么這里我們就來(lái)驗(yàn)證下 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é)習(xí)，你就會(huì)明白。

2、哈希表

2.1 什么是哈希表

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

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

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

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

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

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

2.2 哈希沖突

2.2.1 概念

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

簡(jiǎn)單來(lái)說(shuō)，不同的關(guān)鍵字通過(guò)相同的哈希函數(shù)計(jì)算出相同的哈希地址（前面我們稱為 index），這種現(xiàn)象就被稱為哈希沖突或哈希碰撞！ 

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

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

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

常見(jiàn)的哈希函數(shù)：

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

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

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

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

負(fù)載因子 α = 哈希表中元素個(gè)數(shù) / 哈希表的長(zhǎng)度

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

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

2.2.4 Java中解決哈希沖突 - 開(kāi)散列/哈希桶

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

開(kāi)散列又叫鏈地址法，或開(kāi)鏈法，其實(shí)簡(jiǎn)單來(lái)說(shuō)就是一個(gè)數(shù)組加鏈表的結(jié)構(gòu)。如圖：

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

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è)構(gòu)造方法相信都不難理解，第一個(gè)無(wú)參構(gòu)造方法，默認(rèn)負(fù)載因子是 0.75，第二個(gè)構(gòu)造方法是你可以傳一個(gè) Map 進(jìn)去，構(gòu)造出一個(gè)新的 Map，負(fù)載因子仍然是默認(rèn)的 0.75， 第三個(gè)構(gòu)造方法就是指定開(kāi)辟的容量了(并不是你想象那樣簡(jiǎn)單哦，面試題講解)，這個(gè)很簡(jiǎn)單，第四個(gè)構(gòu)造方法指定容量并且自定義負(fù)載因子。

在 HashMap 中，實(shí)例化對(duì)象的時(shí)候并不會(huì)默認(rèn)開(kāi)辟空間(指定空間除外)。

3.2 HashMap 是如何插入元素的？

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

這里我們通過(guò)查看 put 方法的源碼，來(lái)帶大家一層層揭開(kāi)這個(gè)面紗：

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

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

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

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

接著我們?cè)偻驴?，putVal 方法里面的邏輯，這里代碼比較長(zhǎng)，我們分段演示：

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

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

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

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

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

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

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

最后部分：

這里有效元素個(gè)數(shù)自增，如果超過(guò)了數(shù)組長(zhǎng)度，則重新判斷是否擴(kuò)容（兩倍擴(kuò)容）。 afterNodeInsertion 也不用管，LinkedHashMap中的，這里也沒(méi)有實(shí)際用途。

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

3.3 哈希表下的鏈表，何時(shí)會(huì)樹(shù)化？

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

樹(shù)化的前提是，鏈表的長(zhǎng)度大于等于 8，就會(huì)樹(shù)化，因?yàn)槭菑?binCount 是從 0 開(kāi)始的，所以 TREEIFY_THRESHOLD - 1。那么鏈表的長(zhǎng)度大于等于 8，一定會(huì)從鏈表變成紅黑樹(shù)嗎？我們往后看：

第一個(gè) if 當(dāng)哈希表為空，或者表(數(shù)組)的長(zhǎng)度小于64，只進(jìn)行擴(kuò)容即可，不會(huì)轉(zhuǎn)換成樹(shù)，當(dāng)哈希表的長(zhǎng)度大于 64，才有可能轉(zhuǎn)換成紅黑樹(shù)。

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

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

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

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

4.2 hashCode 和 equals 的區(qū)別

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

當(dāng)我們重寫 hashCode 的時(shí)候，是調(diào)用 Objects 里面的 hash 方法：

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

舉個(gè)例子，person1 和 person2 兩個(gè)對(duì)象的 hashCode 完全不一樣，但通過(guò) hash 函數(shù)得到的 hash 值是相同的！而 hashCode 也是通過(guò) hash 出來(lái)的，即對(duì)象的 hashCode 可以稱為 hash 值，所以得出，兩個(gè)對(duì)象的 hashCode 相同，但是這兩個(gè)對(duì)象不一定相同。

對(duì)于 persong1.equals(person2) 的值為 true 的情況，則代表這兩個(gè)對(duì)象里面的值都是一樣的，所以 equals 為 ture，兩個(gè)一模一樣的對(duì)象，最終的 hash 值肯定也是一樣的，并且 HashMap 也是調(diào)用 key 中的 equals() 方式來(lái)進(jìn)行判斷是否有重復(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é)：

兩個(gè)對(duì)象的 HashCode 相同，不代表這兩個(gè)對(duì)象完全相同。

兩個(gè)對(duì)象的 equals 的結(jié)果為 true，則代表這兩個(gè)對(duì)象完全相同。

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

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

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

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

5、性能分析

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

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

最新評(píng)論