? ? ? ? ? ? ? ? ??

? ? ??

之所以把HashSet和HashMap放在一起講解，是因為二者在Java里有著相同的實現(xiàn)，前者僅僅是對后者做了一層包裝，也就是說HashSet里面有一個HashMap（適配器模式）**。因此本文將重點分析HashMap。

HashMap

HashMap實現(xiàn)了Map接口，即允許放入key為null的元素，也允許插入value為null的元素；除該類未實現(xiàn)同步外，其余跟Hashtable大致相同；跟TreeMap不同，該容器不保證元素順序，根據(jù)需要該容器可能會對元素重新哈希，元素的順序也會被重新打散，因此不同時間迭代同一個HashMap的順序可能會不同。根據(jù)對沖突的處理方式不同，哈希表有兩種實現(xiàn)方式，一種開放地址方式（Open addressing），另一種是沖突鏈表方式（Separate chaining with linked lists）。Java HashMap采用的是沖突鏈表方式。?

從上圖容易看出，如果選擇合適的哈希函數(shù)，put()和get()方法可以在常數(shù)時間內(nèi)完成。但在對HashMap進(jìn)行迭代時，需要遍歷整個table以及后面跟的沖突鏈表。因此對于迭代比較頻繁的場景，不宜將HashMap的初始大小設(shè)的過大。

有兩個參數(shù)可以影響HashMap的性能：初始容量（inital capacity）和負(fù)載系數(shù)（load factor）。初始容量指定了初始table的大小，負(fù)載系數(shù)用來指定自動擴(kuò)容的臨界值。當(dāng)entry的數(shù)量超過capacity*load_factor時，容器將自動擴(kuò)容并重新哈希。對于插入元素較多的場景，將初始容量設(shè)大可以減少重新哈希的次數(shù)。

將對象放入到HashMap或HashSet中時，有兩個方法需要特別關(guān)心：hashCode()和equals()。hashCode()方法決定了對象會被放到哪個bucket里，當(dāng)多個對象的哈希值沖突時，equals()方法決定了這些對象是否是“同一個對象”。所以，如果要將自定義的對象放入到HashMap或HashSet中，需要*@Override*hashCode()和equals()方法。

HashMap

1、為什么用HashMap？

• HashMap是一個散列桶（數(shù)組和鏈表），它存儲的內(nèi)容是鍵值對(key-value)映射

• HashMap采用了數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，能在查詢和修改方便繼承了數(shù)組的線性查找和鏈表的尋址修改

• HashMap是非synchronized，所以HashMap很快

• HashMap可以接受null鍵和值，而Hashtable則不能（原因就是equlas()方法需要對象，因為HashMap是后出的API經(jīng)過處理才可以）

2、HashMap的工作原理是什么？

• HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當(dāng)我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，計算并返回的hashCode是用于找到Map數(shù)組的bucket位置來儲存Node 對象。這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Node 。

方法

方法剖析

get()

get(Object key)方法根據(jù)指定的key值返回對應(yīng)的value，該方法調(diào)用了getEntry(Object key)得到相應(yīng)的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。算法思想是首先通過hash()函數(shù)得到對應(yīng)bucket的下標(biāo)，然后依次遍歷沖突鏈表，通過key.equals(k)方法來判斷是否是要找的那個entry。?

上圖中hash(k)&(table.length-1)等價于hash(k)%table.length，原因是HashMap要求table.length必須是2的指數(shù)，因此table.length-1就是二進(jìn)制低位全是1，跟hash(k)相與會將哈希值的高位全抹掉，剩下的就是余數(shù)了。

//getEntry()方法final Entry<K,V> getEntry(Object key) { ?...... ?int hash = (key == null) ? 0 : hash(key); ? ?for (Entry<K,V> e = table[hash&(table.length-1)];//得到?jīng)_突鏈表 ? ? ? ? e != null; e = e.next) {//依次遍歷沖突鏈表中的每個entry ? ? ? ?Object k; ? ? ? ?//依據(jù)equals()方法判斷是否相等 ? ? ? ?if (e.hash == hash && ? ? ? ? ? ?((k = e.key) == key || (key != null && key.equals(k)))) ? ? ? ? ? ?return e; ? ?} ? ?return null;}


put()

put(K key, V value)方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到，則會通過addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式為頭插法。?

//addEntry()void addEntry(int hash, K key, V value, int bucketIndex) { ? ?if ((size >= threshold) && (null != table[bucketIndex])) { ? ? ? ?resize(2 * table.length);//自動擴(kuò)容，并重新哈希 ? ? ? ?hash = (null != key) ? hash(key) : 0; ? ? ? ?bucketIndex = hash & (table.length-1);//hash%table.length ? ?} ? ?//在沖突鏈表頭部插入新的entry ? ?Entry<K,V> e = table[bucketIndex]; ? ?table[bucketIndex] = new Entry<>(hash, key, value, e); ? ?size++;}

remove()

remove(Object key)的作用是刪除key值對應(yīng)的entry，該方法的具體邏輯是在removeEntryForKey(Object key)里實現(xiàn)的。removeEntryForKey()方法會首先找到key值對應(yīng)的entry，然后刪除該entry（修改鏈表的相應(yīng)引用）。查找過程跟getEntry()過程類似。?

//removeEntryForKey()final Entry<K,V> removeEntryForKey(Object key) { ?...... ?int hash = (key == null) ? 0 : hash(key); ? ?int i = indexFor(hash, table.length);//hash&(table.length-1) ? ?Entry<K,V> prev = table[i];//得到?jīng)_突鏈表 ? ?Entry<K,V> e = prev; ? ?while (e != null) {//遍歷沖突鏈表 ? ? ? ?Entry<K,V> next = e.next; ? ? ? ?Object k; ? ? ? ?if (e.hash == hash && ? ? ? ? ? ?((k = e.key) == key || (key != null && key.equals(k)))) {//找到要刪除的entry ? ? ? ? ? ?modCount++; size--; ? ? ? ? ? ?if (prev == e) table[i] = next;//刪除的是沖突鏈表的第一個entry ? ? ? ? ? ?else prev.next = next; ? ? ? ? ? ?return e; ? ? ? ?} ? ? ? ?prev = e; e = next; ? ?} ? ?return e;}

HashSet

前面已經(jīng)說過HashSet是對HashMap的簡單包裝，對HashSet的函數(shù)調(diào)用都會轉(zhuǎn)換成合適的HashMap方法，因此HashSet的實現(xiàn)非常簡單，只有不到300行代碼。這里不再贅述。

//HashSet是對HashMap的簡單包裝public class HashSet<E>{ ?...... ?private transient HashMap<E,Object> map;//HashSet里面有一個HashMap ? ?// Dummy value to associate with an Object in the backing Map ? ?private static final Object PRESENT = new Object(); ? ?public HashSet() { ? ? ? ?map = new HashMap<>(); ? ?} ? ?...... ? ?public boolean add(E e) {//簡單的方法轉(zhuǎn)換 ? ? ? ?return map.put(e, PRESENT)==null; ? ?} ? ?......}

一、HahMap存儲對象的過程如下

1、對HahMap的Key調(diào)用hashCode()方法，返回int值，即對應(yīng)的hashCode；

2、把此hashCode作為哈希表的索引，查找哈希表的相應(yīng)位置，若當(dāng)前位置內(nèi)容為NULL，則把hashMap的Key、Value包裝成Entry數(shù)組，放入當(dāng)前位置；

3、若當(dāng)前位置內(nèi)容不為空，則繼續(xù)查找當(dāng)前索引處存放的鏈表，利用equals方法，找到Key相同的Entry數(shù)組，則用當(dāng)前Value去替換舊的Value；

4、若未找到與當(dāng)前Key值相同的對象，則把當(dāng)前位置的鏈表后移（Entry數(shù)組持有一個指向下一個元素的引用），把新的Entry數(shù)組放到鏈表表頭；

二、HashSet存儲對象的過程

往HashSet添加元素的時候，HashSet會先調(diào)用元素的hashCode方法得到元素的哈希值 ，

然后通過元素 的哈希值經(jīng)過移位等運算，就可以算出該元素在哈希表中 的存儲位置。

情況1：如果算出元素存儲的位置目前沒有任何元素存儲，那么該元素可以直接存儲到該位置上。

情況2：如果算出該元素的存儲位置目前已經(jīng)存在有其他的元素了，那么會調(diào)用該元素的equals方法與該位置的元素再比較一次

，如果equals返回的是true，那么該元素與這個位置上的元素就視為重復(fù)元素，不允許添加，如果equals方法返回的是false，那么該元素運行添加。

? ? ? ? ? ? ?

題外話：

這Typora還夸你好用還免費，這突然更新了就啪啪打臉了，那問題來了typora是啥？

Typora，異常純凈的寫作軟件。支持 Markdown 語法、一鍵導(dǎo)出為各種文檔格式、圖床一鍵上傳等核心功能，可以滿足幾乎所有同學(xué)的寫作、記錄需求。

因為界面干凈清爽、細(xì)節(jié)到位、寫作體驗巨好，這款軟件被很多同學(xué)稱為是 “藝術(shù)品” 。我自己作為 Typora 的忠實用戶，用了它之后再也沒用過別的本地寫作軟件（比如開源的 Mark Text）。我甚至可以為了它的寫作體驗，而放棄一些云端自動同步的產(chǎn)品（現(xiàn)在我都是用 Git + GitHub 私倉來管理所有的文檔了）。

再加上它是完全免費的，使得這個軟件得到了無數(shù)小伙伴的好評。

但是，就在前兩天，Typora 的作者 Abner Lee 突然宣布：升級 v1.x 正式版本后，Typora 將?收費?！折合人民幣 90 元左右，可以在最多 3 臺設(shè)備使用。不過 v1.0 前的老版本依然可以免費使用。

估計有很多同學(xué)要問了：小劉，Typora 收費了，值得買么？

我說下自己的看法：可以付費，但沒必要。

首先，我也是一名開發(fā)者，當(dāng)然理解開發(fā)免費軟件的艱辛，也對作者這么多年來持續(xù)更新免費產(chǎn)品表示 100% 的敬佩。

但是，暫且不擺對這個軟件的情懷，單純從用戶的角度來看，付費版本并沒有比免費版本多出什么功能和亮點?？匆幌鹿俜降?CHANGE LOG，發(fā)現(xiàn)只是多了個安裝包、一些數(shù)學(xué)公式編輯和 Bug 修復(fù)而已。

所以我是不會購買的。而且作者已經(jīng)那么良心了 —— 老的 beta 版本還能直接在官網(wǎng)下載、免費使用，我們當(dāng)然不能辜負(fù)作者的一片好意（狗頭）。

我希望收費之后的 Typora 可以在不影響用戶使用習(xí)慣的前提下，打磨地更好、出一些更實用的功能（比如云端同步、插件等），等到那時，我可能不僅會付費購買，還會做一波無償推廣哈哈~

總結(jié)：

1. java最基本的兩種數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表的區(qū)別：數(shù)組易于快速讀?。ㄍㄟ^for循環(huán)），不便存儲（數(shù)組長度有限制）；鏈表易于存儲，不易于快速讀取。

2. HashSet是通過HasMap來實現(xiàn)的，HashMap的輸入?yún)?shù)有Key、Value兩個組成，在實現(xiàn)HashSet的時候，保持HashMap的Value為常量，相當(dāng)于在HashMap中只對Key對象進(jìn)行處理。

3. HashMap的底層是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項對應(yīng)了一個鏈表，這種結(jié)構(gòu)稱“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體；也叫散列表、哈希表。

4. jdk1.8以前的hashmap與jdk1.8以后的hashmap

5. 你要知道兩種方式的存儲和底層邏輯和方法的使用

6. 這Typora?的作者還是很良心的v1.x以前的還是免費，而且以前的版本可以在官網(wǎng)下載，這工具來寫文章或者做筆記還是很棒的。
   

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ?