第9講 對(duì)比hashtable、hashmap、treemap有什么不同_h

1、2018/5/26極客時(shí)間 | Java核心技術(shù)36講第9講 | 對(duì)比Hashtable、HashMap、TreeMap有什么不同？2018-05-24 楊曉峰Map 是廣義 Java 集合框架中的另外一部分，HashMap 作為框架中使用頻率最高的類型之一， 它本身以及相關(guān)類型自然也是面試考察的熱點(diǎn)。今天我要問(wèn)你的問(wèn)題是，對(duì)比 Hashtable、HashMap、TreeMap 有什么不同？談?wù)勀銓?duì)HashMap 的掌握。典型回答Hashtable、HashMap、TreeMap 都是最常見(jiàn)的一些 Map 實(shí)現(xiàn)，是以鍵值對(duì)的形式存儲(chǔ)和操作數(shù)據(jù)的容器類型。Hashtable 是早期 Java

2、類庫(kù)提供的一個(gè)哈希表實(shí)現(xiàn)，本身是同步的，不支持 null 鍵和值，由于同步導(dǎo)致的性能開銷，所以已經(jīng)很少被推薦使用。HashMap 是應(yīng)用更加廣泛的哈希表實(shí)現(xiàn)，行為上大致上與 HashTable 一致，主要區(qū)別在于HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進(jìn)行 put 或者 get 操/column/article/80531/15第9講 | 對(duì)比Hashtable、HashMap、TreeMap有什么不同？朗讀人：黃洲君1216 | 5.62M2018/5/26極客時(shí)間 | Java核心技術(shù)36講作，可以達(dá)

3、到常數(shù)時(shí)間的性能，所以它是絕大部分利用鍵值對(duì)存取場(chǎng)景的首選，比如，實(shí)現(xiàn)一個(gè)用戶 ID 和用戶信息對(duì)應(yīng)的運(yùn)行時(shí)存儲(chǔ)結(jié)構(gòu)。TreeMap 則是基于紅黑樹的一種提供順序訪問(wèn)的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時(shí)間復(fù)雜度，具體順序可以由指定的 Comparator 來(lái)決定，或者根據(jù)鍵的自然順序來(lái)判斷?？键c(diǎn)分析上面的回答，只是對(duì)一些基本特征的簡(jiǎn)單總結(jié)，針對(duì) Map 相關(guān)可以擴(kuò)展的問(wèn)題很多，從各種數(shù)據(jù)結(jié)構(gòu)、典型應(yīng)用場(chǎng)景，到程序設(shè)計(jì)實(shí)現(xiàn)的技術(shù)考量，尤其是在 Java 8 里，HashMap 本身發(fā)生了非常大的變化，這些都是經(jīng)常考察的方面

4、。很多朋友向我反饋，面試官似乎鐘愛(ài)考察 HashMap 的設(shè)計(jì)和實(shí)現(xiàn)細(xì)節(jié)，所以今天我會(huì)增加相應(yīng)的源碼解讀，主要專注于下面幾個(gè)方面：理解 Map 相關(guān)類似整體結(jié)構(gòu)，尤其是有序數(shù)據(jù)結(jié)構(gòu)的一些要點(diǎn)。從源碼去分析 HashMap 的設(shè)計(jì)和實(shí)現(xiàn)要點(diǎn)，理解容量、負(fù)載因子等，為什么需要這些參數(shù)，如何影響 Map 的性能，實(shí)踐中如何取舍等。理解樹化改造的相關(guān)原理和改進(jìn)原因。除了典型的代碼分析，還有一些有意思的并發(fā)相關(guān)問(wèn)題也經(jīng)常會(huì)被提到，如 HashMap 在并發(fā)環(huán)境可能出現(xiàn)無(wú)限循環(huán)占用 CPU、size 不準(zhǔn)確等詭異的問(wèn)題。我認(rèn)為這是一種典型的使用錯(cuò)誤，因?yàn)?HashMap 明確聲明不是線程安全的數(shù)據(jù)結(jié)構(gòu)，如

5、果忽略這一點(diǎn)，簡(jiǎn)單用在多線程場(chǎng)景里，難免會(huì)出現(xiàn)問(wèn)題。理解導(dǎo)致這種錯(cuò)誤的原因，也是深入理解并發(fā)程序運(yùn)行的好辦法。對(duì)于具體發(fā)生了什么，你可以參考這篇很久以前的分析，里面甚至提供了示意圖，我就不再重復(fù)別人寫好的內(nèi)容了。知識(shí)擴(kuò)展1.Map 整體結(jié)構(gòu)首先，我們先對(duì) Map 相關(guān)類型有個(gè)整體了解，Map 雖然通常被包括在 Java 集合框架里，但是其本身并不是狹義上的集合類型（Collection），具體你可以參考下面這個(gè)簡(jiǎn)單類圖。/column/article/80532/152018/5/26極客時(shí)間 | Java核心技術(shù)36講Hashtable 比較特

6、別，作為類似 Vector、Stack 的早期集合相關(guān)類型，它是擴(kuò)展了 Dictionary類的，類結(jié)構(gòu)上與 HashMap 之類明顯不同。HashMap 等其他 Map 實(shí)現(xiàn)則是都擴(kuò)展了 AbstractMap，里面包含了通用方法抽象。不同Map 的用途，從類圖結(jié)構(gòu)就能體現(xiàn)出來(lái)，設(shè)計(jì)目的已經(jīng)體現(xiàn)在不同接口上。大部分使用 Map 的場(chǎng)景，通常就是放入、訪問(wèn)或者刪除，而對(duì)順序沒(méi)有特別要求，HashMap在這種情況下基本是最好的選擇。HashMap 的性能表現(xiàn)非常依賴于哈希碼的有效性，請(qǐng)務(wù)必掌握 hashCode 和 equals 的一些基本約定，比如：equals 相等，hashCode 一定要

7、相等。重寫了 hashCode 也要重寫 equals。hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致。equals 的對(duì)稱、反射、傳遞等特性。這方面內(nèi)容網(wǎng)上有很多資料，我就不在這里詳細(xì)展開了。針對(duì)有序 Map 的分析內(nèi)容比較有限，我再補(bǔ)充一些，雖然 LinkedHashMap 和 TreeMap 都可以保證某種順序，但二者還是非常不同的。LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實(shí)現(xiàn)是通過(guò)為條目（鍵值對(duì)）維護(hù)一個(gè)雙向鏈表。注意，通過(guò)特定構(gòu)造函數(shù)，我們可以創(chuàng)建反映訪問(wèn)順序的實(shí)例，所謂的/column/ar

8、ticle/80533/152018/5/26極客時(shí)間 | Java核心技術(shù)36講put、get、compute 等，都算作“訪問(wèn)”。這種行為適用于一些特定應(yīng)用場(chǎng)景，例如，我們構(gòu)建一個(gè)空間占用敏感的資源池，希望可以自動(dòng)將最不常被訪問(wèn)的對(duì)象釋放掉，這就可以利用 LinkedHashMap 提供的機(jī)制來(lái)實(shí)現(xiàn)，參考下面的示例：/column/article/80534/15import java.util.LinkedHashMap; import java.util.Map;public class LinkedHashMapSample publi

9、c static void matring args) LinkedHashMap accessOrderedMap = new LinkedHashMap(16, 0.75F, true) Overrideprotected boolean removeEldestEntry(Map.Entry eldest) / 實(shí)現(xiàn)自 return size() 3;accessOrderedMap.put(Project1, Valhalla); accessOrderedMap.put(Project2, Panama); accessOrderedMap.put(Project3, Loom);

10、accessOrderedMap.forEach( (k,v) - System.out.println(k +: + v););/ 模擬訪問(wèn)accessOrderedMap.get(Project2); accessOrderedMap.get(Project2); accessOrderedMap.get(Project3);System.out.println(Iterate over should be not affected:); accessOrderedMap.forEach( (k,v) - System.out.println(k +: + v););/ 觸發(fā)刪除 acce

11、ssOrderedMap.put(Project4, Mission Control); System.out.println(Oldest entry should be removed:); accessOrderedMap.forEach( (k,v) - / 遍歷順序不變 System.out.println(k +: + v););2018/5/26極客時(shí)間 | Java核心技術(shù)36講對(duì)于 TreeMap，它的整體順序是由鍵的順序關(guān)系決定的，通過(guò) Comparator 或Comparable（自然順序）來(lái)決定。我在上一講留給你的思考題提到了，構(gòu)建一個(gè)具有優(yōu)先級(jí)的調(diào)度系統(tǒng)的問(wèn)題，其本質(zhì)

12、就是個(gè)典型的優(yōu)先隊(duì)列場(chǎng)景，Java 標(biāo)準(zhǔn)庫(kù)提供了基于二叉堆實(shí)現(xiàn)的 PriorityQueue，它們都是依賴于同一種排序機(jī)制，當(dāng)然也包括 TreeMap 的馬甲 TreeSet。類似 hashCode 和 equals 的約定，為了避免模棱兩可的情況，自然順序同樣需要符合一個(gè)約定，就是 compareTo 的返回值需要和 equals 一致，否則就會(huì)出現(xiàn)模棱兩可情況。我們可以分析 TreeMap 的 put 方法實(shí)現(xiàn)：從代碼里，你可以看出什么呢？ 當(dāng)我不遵守約定時(shí)，兩個(gè)不符合唯一性（equals）要求的對(duì)象被當(dāng)作是同一個(gè)（因?yàn)椋琧ompareTo 返回 0），這會(huì)導(dǎo)致歧義的行為表現(xiàn)。2.Hash

13、Map 源碼分析前面提到，HashMap 設(shè)計(jì)與實(shí)現(xiàn)是個(gè)非常高頻的面試題，所以我會(huì)在這進(jìn)行相對(duì)詳細(xì)的源碼解讀，主要圍繞：HashMap 內(nèi)部實(shí)現(xiàn)基本點(diǎn)分析。容量（capcity）和負(fù)載系數(shù)（load factor）。/column/article/80535/15public V put(K key, V value) Entry t = cmp = pareTo(t.key); if (cmp 0)t = t.right;elsereturn t.setValue(value);/ .2018/5/26樹化 。極客時(shí)間 | Java核

14、心技術(shù)36講首先，我們來(lái)一起看看 HashMap 內(nèi)部的結(jié)構(gòu)，它可以看作是數(shù)組（Node table）和鏈表結(jié)合組成的復(fù)合結(jié)構(gòu)，數(shù)組被分為一個(gè)個(gè)桶（bucket），通過(guò)哈希值決定了鍵值對(duì)在這個(gè)數(shù)組的尋址；哈希值相同的鍵值對(duì)，則以鏈表形式存儲(chǔ)，你可以參考下面的示意圖。這里需要注意的是，如果鏈表大小超過(guò)閾值（TREEIFY_THRESHOLD, 8），圖中的鏈表就會(huì)被改造為樹形結(jié)構(gòu)。從非拷貝構(gòu)造函數(shù)的實(shí)現(xiàn)來(lái)看，這個(gè)表格（數(shù)組）似乎并沒(méi)有在最初就初始化好，僅僅設(shè)置了一些初始值而已。所以，我們深刻懷疑，HashMap 也許是按照 lazy-load 原則，在首次使用時(shí)被初始化（拷貝構(gòu)造函數(shù)除外，我這里

15、僅介紹最通用的場(chǎng)景）。既然如此，我們?nèi)タ纯?put 方法實(shí)現(xiàn)，似乎只有一個(gè) putVal 的調(diào)用：/column/article/80536/15public V put(K key, V value) return putVal(hash(key), key, value, false, true);public HashMap(int initialCapacity, float loadFactor)/ .this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCa

16、pacity);2018/5/26極客時(shí)間 | Java核心技術(shù)36講看來(lái)主要的似乎藏在 putVal 里面，到底有什么呢？為了節(jié)省空間，我這里只截取了putVal 比較關(guān)鍵的幾部分。從 putVal 方法最初的幾行，我們就可以發(fā)現(xiàn)幾個(gè)有意思的地方：如果表格是 null，resize 方負(fù)責(zé)初始化它，這從 tab = resize() 可以看出。resize 方法兼顧兩個(gè)職責(zé)，創(chuàng)建初始存儲(chǔ)表格，或者在容量不滿足需求的時(shí)候，進(jìn)行擴(kuò)容（resize）。在放置新的鍵值對(duì)的過(guò)程中，如果發(fā)生下面條件，就會(huì)發(fā)生擴(kuò)容。具體鍵值對(duì)在哈希表中的位置（數(shù)組 index）取決于下面的位運(yùn)算：仔細(xì)觀察哈希值的源頭，我

17、們會(huì)發(fā)現(xiàn)，它并不是 key 本身的 hashCode，而是來(lái)自于HashMap 內(nèi)部的另外一個(gè) hash 方法。注意，為什么這里需要將高位數(shù)據(jù)移位到低位進(jìn)行異或/column/article/80537/15i = (n - 1) & hashif (+size threshold) resize();final V putVal(int hash, K key, V value, boolean onlyIfAbent, boolean evit) Node tab; Node p; int , i;if (tab = table) = nul

18、l | (n = tab.length) = 0) n = (tab = resize().legth;if (p = tabi = (n - 1) & hash) = ull) tabi = newNode(hash, key, value, nll);else / .if (binCount = TREEIFY_THRESHOLD - 1) / -1 for first treeifyBin(tab, hash);/.2018/5/26極客時(shí)間 | Java核心技術(shù)36講運(yùn)算呢？這是因?yàn)橛行?shù)據(jù)計(jì)算出的哈希值差異主要在高位，而 HashMap 里的哈希尋址是忽略容量以上的高位的，那么這種處

19、理就可以有效避免類似情況下的哈希碰撞。我前面提到的鏈表結(jié)構(gòu)（這里叫 bin），會(huì)在達(dá)到一定門限值時(shí)，發(fā)生樹化，我稍后會(huì)分析為什么 HashMap 需要對(duì) bin 進(jìn)行處理?？梢钥吹剑琾utVal 方法本身邏輯非常集中，從初始化、擴(kuò)容到樹化，全部都和它有關(guān)，推薦你閱讀源碼的時(shí)候，可以參考上面的主要邏輯。我進(jìn)一步分析一下身兼多職的 resize 方法，很多朋友都反饋經(jīng)常被面試官追問(wèn)它的源碼設(shè)計(jì)。/column/article/80538/15final Node resize() / .else if (newCap = oldCap 1) = DE

20、FAULT_INITIAL_CAPAITY)newThr = oldThr 0) / initial capacity was placed in threshold newCap = oldThr;else / zero initial threshold signifies using defaultsfults newCap = DEFAULT_INITIAL_CAPAITY;newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY； if (newThr =0) float ft = (float)newCap * loadF

21、ator;newThr = (newCap MAXIMUM_CAPACITY & ft (float)MAXIMUM_CAPACITY ?(int)ft : Integethreshold = neThr;Node newTab = (Node)new Nodenewap; table = n； static final int hash(Object kye) int h;return (key = null) ? 0 : (h = key.hashCode() (h 16;2018/5/26極客時(shí)間 | Java核心技術(shù)36講依據(jù) resize 源碼，不考慮情況（容量理論最大極限由 MAX

22、IMUM_CAPACITY 指定，數(shù)值為 130，也就是 2 的 30 次方），我們可以歸納為：門限值等于（負(fù)載因子）x（容量），如果構(gòu)建 HashMap 的時(shí)候沒(méi)有指定它們，那么就是依據(jù)相應(yīng)的默認(rèn)常量值。門限通常是以倍數(shù)進(jìn)行調(diào)整 （newThr = oldThr 元素?cái)?shù)量 / 移動(dòng)到新的數(shù)組結(jié)構(gòu) e 數(shù)組結(jié)構(gòu) 2018/5/26極客時(shí)間 | Java核心技術(shù)36講如果確實(shí)需要調(diào)整，建議不要設(shè)置超過(guò) 0.75 的數(shù)值，因?yàn)闀?huì)顯著增加沖突，降低 HashMap的性能。如果使用太小的負(fù)載因子，按照上面的公式，預(yù)設(shè)容量值也進(jìn)行調(diào)整，否則可能會(huì)導(dǎo)致更加頻繁的擴(kuò)容，增加無(wú)謂的開銷，本身訪問(wèn)性能也會(huì)受影響

23、。我們前面提到了樹化改造，對(duì)應(yīng)邏輯主要在 putVal 和 treeifyBin 中。上面是精簡(jiǎn)過(guò)的 treeifyBin 示意，綜合這兩個(gè)方法，樹化改造的邏輯就非常清晰了，可以理解為，當(dāng) bin 的數(shù)量大于 TREEIFY_THRESHOLD 時(shí)：如果容量小于 MIN_TREEIFY_CAPACITY，只會(huì)進(jìn)行簡(jiǎn)單的擴(kuò)容。如果容量大于 MIN_TREEIFY_CAPACITY ，則會(huì)進(jìn)行樹化改造。那么，為什么 HashMap 要樹化呢？本質(zhì)上這是個(gè)安全問(wèn)題。因?yàn)樵谠胤胖眠^(guò)程中，如果一個(gè)對(duì)象哈希沖突，都被放置到同一個(gè)桶里，則會(huì)形成一個(gè)鏈表，我們知道鏈表查詢是線性的，會(huì)嚴(yán)重影響存取的性能。而在

24、現(xiàn)實(shí)世界，構(gòu)造哈希沖突的數(shù)據(jù)并不是非常復(fù)雜的事情，惡意代碼就可以利用這些數(shù)據(jù)大量與服務(wù)器端交互，導(dǎo)致服務(wù)器端 CPU 大量占用，這就構(gòu)成了哈希碰撞拒絕服務(wù)攻擊，國(guó)內(nèi)一線互聯(lián)網(wǎng)公司就發(fā)生過(guò)類似攻擊。今天我從 Map 相關(guān)的幾種實(shí)現(xiàn)對(duì)比，對(duì)各種 Map 進(jìn)行了分析，講解了有序集合類型容易混淆的地方，并從源碼級(jí)別分析了 HashMap 的基本結(jié)構(gòu)，希望對(duì)你有所幫助。一課一練關(guān)于今天我們討論的題目你做到心中有數(shù)了嗎？留一道思考題給你，解決哈希沖突有哪些典型方法呢？/column/article/805310/15final void treeifyBin

25、(Node tab, int hash) int n, index; Node e;if (tab = null | (n = tab.length) MIN_TREEIFY_CAPACITY) resize();else if (e = tabindex = (n - 1) & hash) != null) / 樹化改造邏輯 2018/5/26極客時(shí)間 | Java核心技術(shù)36講請(qǐng)你在留言區(qū)寫寫你對(duì)這個(gè)問(wèn)題的思考，我會(huì)選出經(jīng)過(guò)認(rèn)真思考的留言，送給你一份學(xué)習(xí)鼓勵(lì)金，歡迎你與我一起討論。你的朋友是不是也在準(zhǔn)備面試呢？你可以“請(qǐng)朋友讀”，把今天的題目分享給好友，或許你能幫到他。版權(quán)歸極客邦科技所有

26、，未經(jīng)許可不得轉(zhuǎn)載精選留言17公眾號(hào):代碼榮耀Hashtable、HashMap、TreeMap心得三者均實(shí)現(xiàn)了Map接口，存儲(chǔ)的內(nèi)容是基于key-value的鍵值對(duì)映射，一個(gè)映射不能有重復(fù)的 鍵，一個(gè)鍵最多只能映射一個(gè)值。（1）元 素 特 性HashTable中的key、value都不能為null；HashMap中的key、value可以為null，很顯然只能有一個(gè)key為null的鍵值對(duì)，但是允許有多個(gè)值為null的鍵值對(duì)；TreeMap中當(dāng)未實(shí)現(xiàn) Co mparator 接口時(shí)，key 不可以為null；當(dāng)實(shí)現(xiàn) Comparator 接口時(shí)，若未對(duì)null情況進(jìn)行判斷，則key不可以為n

27、ull，反之亦然。（2） 順 序 特 性HashTable、HashMap具有無(wú)序特性。TreeMap是利用紅黑樹來(lái)實(shí)現(xiàn)的（樹中的每個(gè)節(jié)點(diǎn)的值，都會(huì)大于或等于它的左子樹種的所有節(jié)點(diǎn)的值，并且小于或等于它的右子樹中的所有節(jié)點(diǎn)的值），實(shí)現(xiàn)了SortMap接口，能夠?qū)Ρ４娴挠涗浉鶕?jù)鍵進(jìn)行排序。所以一般需要排序的情況下是選擇TreeMap來(lái)進(jìn)行，默認(rèn)為升序排序方式（深度優(yōu)先搜索），可自定義實(shí)現(xiàn)Com parator接口實(shí)現(xiàn)排序方式。/column/article/805311/152018/5/26極客時(shí)間 | Java核心技術(shù)36講（3）初始化與增長(zhǎng)方

28、式初始化時(shí)：HashTable在不指定容量的情況下的默認(rèn)容量為11，且不要求底層數(shù)組的容量一 定要為2的整數(shù)次冪；HashMap默認(rèn)容量為16，且要求容量一定為2的整數(shù)次冪。擴(kuò)容時(shí)：Hashtable將容量變?yōu)樵瓉?lái)的2倍加1；HashMap擴(kuò)容將容量變?yōu)樵瓉?lái)的2倍。（4） 線 程 安 全 性HashTable其方法函數(shù)都是同步的（采用synchronized修飾），不會(huì)出現(xiàn)兩個(gè)線程同時(shí)對(duì)數(shù)據(jù)進(jìn)行操作的情況，因此保證了線程安全性。也正因?yàn)槿绱耍诙嗑€程運(yùn)行環(huán)境下效率表現(xiàn)非常低下。因?yàn)楫?dāng)一個(gè)線程訪問(wèn)HashTable的同步方法時(shí)，其他線程也訪問(wèn)同步方法就會(huì)進(jìn)入阻塞狀態(tài)。比如當(dāng)一個(gè)線程在添加數(shù)據(jù)時(shí)候

29、，另外一個(gè)線程即使執(zhí)行獲取其他數(shù)據(jù)的操作也必須被阻塞，大大降低了程序的運(yùn)行效率，在新版本中已被廢棄，不推薦使用。HashMap不支持線程的同步，即任一時(shí)刻可以有多個(gè)線程同時(shí)寫HashMap;可能會(huì)導(dǎo)致數(shù)據(jù)的不一致。如果需要同步（1）可以用Collections的synchronizedMap方法；（2）使用Co ncurrentHashMap類，相較于HashTable鎖住的是對(duì)象整體， ConcurrentHashMap基于lo ck實(shí)現(xiàn)鎖分段技術(shù)。首先將Map存放的數(shù)據(jù)分成一段一段的存儲(chǔ)方式，然后給每一段數(shù)據(jù)分配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段的數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)

30、。ConcurrentHashMap不僅保證了多線程運(yùn)行環(huán)境下的數(shù)據(jù)訪問(wèn)安全性，而且性能上有 長(zhǎng)足的提升。(5) 一 段 話 HashMapHashMap基于哈希思想，實(shí)現(xiàn)對(duì)數(shù)據(jù)的讀寫。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來(lái)計(jì)算hashcode，讓后找到bucket位置來(lái)儲(chǔ)存值對(duì)象。當(dāng)獲取對(duì)象時(shí)，通過(guò)鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象。HashMap使用鏈表來(lái)解決碰撞問(wèn)題，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中。 HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象。當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同時(shí)，它們會(huì)儲(chǔ)存在同一個(gè)

31、bucket位置的鏈表中，可通過(guò)鍵對(duì)象的equals()方法用來(lái)找到鍵值對(duì)。如果鏈表大小超過(guò)閾值（TREEIFY_THRESHOLD, 8），鏈表就會(huì)被改造為樹形結(jié)構(gòu)。2018-05-244天涼好個(gè)秋解決哈希沖突的常用方法有：開放定址法基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)，以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈 希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p2，直到找出一個(gè)不沖突的哈希地址pi ，將相應(yīng)元素存入其中。再哈希法這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)： Hi=RH1（key） i=1，2，k當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時(shí)，再計(jì)算Hi=RH2（

32、key），直到?jīng)_突不再產(chǎn)生。 這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。/column/article/805312/152018/5/26極客時(shí)間 | Java核心技術(shù)36講鏈地址法這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況。建立公共溢出區(qū)這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元 素，一律填入溢出表。2018-05-244j.c.這是面試必問(wèn)題。什么時(shí)候也能講講紅黑樹的樹化具體過(guò)程，那個(gè)旋轉(zhuǎn)一直沒(méi)搞懂。另外tre eifyBin這個(gè)單詞的詞面意思是什么？2018-05-24灰飛灰豬不會(huì)灰飛.煙滅這是1.7的hashmap吧？2018-05-2410代碼狂徒針對(duì)負(fù)載因子，您所指的存太滿會(huì)影響性能是指什么？畢竟已經(jīng)開辟了相應(yīng)內(nèi)存空間的，沒(méi) 什么不用呢？2018-05-24作者回復(fù)沖突可能會(huì)增加,影響查詢之類性能，當(dāng)然看具體的需求2018-05-250代碼狂徒為什么不是一開始就樹化，而是要等到一定程度再樹化，鏈表一開始就是消耗查找性能啊