文章前言

在集合(上)中我們詳細的講解了List的實現(xiàn)類的一些重要原理，Set的實現(xiàn)類還沒有講，但是我們簡要的看下Set下的兩個主要實現(xiàn)類的代碼：

我們會看到Set的底層是Map的實現(xiàn)類，所以我們講完Map再來看Set會變得簡單些。

Map

對于Map，得先知道它的一些特點：在Map中數(shù)據(jù)是以"key-value"的形式存在的，一個key對應一個value，俗稱鍵值。就如同我們的飲料一樣，一種飲料對應一個價格。

而對于需要了解的Map結構，先看看以下的"簡單"關系圖：

對于Map的常見接口主要有Map和TreeMap兩個，而常用的實現(xiàn)類就看HashMap、Propertied、TreeMap這三個就行了。接下來還是一樣，先看下常見接口的常用方法：

Map

清空集合的所有元素。

判斷集合中是否包含某個鍵或值。(底層調用equals方法，自定義類需要重寫)

通過指定的鍵獲取鍵包含的值。

判斷集合是否為空。

往集合中添加鍵值。

通過指定鍵來刪除對應的鍵值。

返回集合中鍵值的個數(shù)。

這兩個方法都返回了一個Set集合，之后遍歷Map時候講。

Map中還有一個重要的內部類：

這個是Map的實現(xiàn)類存取鍵值的重要的父類。

SortedMap

重點就看這個comparator方法，之后到TreeMap講。

Map的實現(xiàn)類

和Collection集合一樣，我們要了解幾個實現(xiàn)類的一些底層原理，而且Map的原理會更復雜：

HashMap

作為Map中最具有代表性的實現(xiàn)類，HashMap常用方法基本都在Map里面了。而HashMap底層的結構實際上是由數(shù)組加單向鏈表(紅黑樹)組成的。這也解釋了為什么Map是無序的，而存儲鍵值使用HashMap的Node內部類。那怎么定位到指定的數(shù)組，鏈表又怎么和數(shù)組連接起來構成一個HashMap呢？先看以下代碼：

我們新建一個HashMap集合，然后在里面添加鍵值，這時候會根據(jù)鍵的哈希值(hashcode)來確定鍵值添加到數(shù)組的位置。這也是Map無序的體現(xiàn)了，因為根據(jù)哈希值的不同，每個鍵值不知道會存儲到數(shù)組的哪個地方。而鍵的哈希值是有可能相同的，于是就會添加到數(shù)組的同一個索引下，而數(shù)組的一個索引只能存放一個元素，多個鍵值在同一個數(shù)組的索引下就變成了鏈表。當有著同一個哈希值的鍵值添加進鏈表的時候會對鏈表中的所有的鍵進行比較(equals)，如果相同就覆蓋已有鍵的值。這就是Map不可重復的由來了(所以上述的代碼鍵為3的鍵值的值其實是只有樂虎而已)。于是乎就形成了大致如下的結構：

然后JDK8的新特性：為了加快檢索效率加了一個紅黑樹。當數(shù)組的一個鏈表中的鍵值超過8個之后就會轉換為紅黑樹，當數(shù)組的一個鏈表中的鍵值少于6個之后就會恢復成鏈表。并且遵循左小右大原則(比當前節(jié)點小的元素放在節(jié)點左邊，反之右邊)。

大致上了解了HashMap的一些原理之后，我們就看看源代碼是如何實現(xiàn)的：

HashMap的常量和屬性

上圖截取了常見的常量及屬性：

DEFAULT_INITIAL_CAPACITY表示默認初始容量；

MAXIMUM_CAPACITY表示最大容量；

DEFAULT_LOAD_FACTOR表示默認加載因子(擴容講解)；

TREEIFY_THRESHOLD表示轉變?yōu)榧t黑樹的臨界值；

UNTREEIFY_THRESHOLD表示還原為鏈表的臨界值；

在屬性中用一個table的數(shù)組加一個節(jié)點類來表示Map的數(shù)據(jù)結構，用entrySet來緩存鍵值(用于entrySet方法)；size和modCount和Collection一樣來表示鍵值個數(shù)和集合被修改的次數(shù)；loadFactor表示加載因子(沒有賦值就是上述的DEFAULT_LOAD_FACTOR)。threshold表示閾值，等于容量*加載因子。

靜態(tài)內部類——Node

HashMap的實現(xiàn)鏈表的節(jié)點類：

可以看到它是實現(xiàn)了Map的內部類Map.Entry。

HashMap常用構造方法

如果是無參構造，加載因子為默認值，且其他屬性都是默認值。

如果傳入一個容量和加載因子，那么會進行判斷，都合法(容量>=0且如果容量大于最大值，容量變?yōu)樽畲笾?#xff1b;加載因子是數(shù)字且>0)就進行賦值。

如果傳入一個容量，和上述一樣，就是加載因子是默認值。

擴容機制

擴容一般發(fā)生在添加鍵值的時候，所以我們看put方法：

底層又調用了putVal方法，值得注意的是它先用一個hash方法獲得了一個哈希值：

hash方法中對哈希值的處理主要是為了減少哈希碰撞(簡要理解哈希碰撞就是對key轉換后的哈希值相同，鏈表就是來解決哈希碰撞的)。底層調用了key對象的hashCode方法。如果key為null，返回0；否則進行一些特殊運算轉換為哈希值。再看putVal方法方法：

看起來很復雜，但大體上就是如下圖：

主要看最后的元素個數(shù)大于閾值，擴容的if語句，這才是重點。通過源代碼我們可以發(fā)現(xiàn)，通過key的哈希值確定數(shù)組下標的表達式為：

(數(shù)組長度-1) & key的哈希值

HashMap在元素個數(shù)達到閾值(容量*加載因子)的時候使用resize方法擴容。而因為HashMap底層結構復雜，擴容也復雜，這里就截取一部分說明：

我們從這可以看出，當oldCap進行左移一位運算沒有超過最大容量，并且oldCap已經(jīng)大于默認容量時，新容量就變成原容量的兩倍。也就是說，如果初始化HashMap用無參構造的話，初始容量為16，加載因子為默認加載因子0.75，當元素個數(shù)>16*0.75=12的時候，就會擴容成容量為32的集合。

JDK8前的HashMap

以上說的都是JDK8后的HashMap，那之前的HashMap有什么不同呢?JDK8前的HashMap不是用節(jié)點Node存儲鍵值的，而是用Entry來儲存；并且沒有紅黑樹結構。只有數(shù)組+鏈表；發(fā)生哈希碰撞時在鏈表的頭部插入(JDK8后從鏈表的尾部插入)。由于沒有紅黑樹，我們在尋找存于某個鏈表中的鍵值時，最糟的時間復雜度為O(n),但紅黑樹因為左小右大的特性，最糟的時間復雜度為O(logn)。【n表示元素個數(shù)】

其他

經(jīng)過上述我們知道了HashMap在進行元素的一些操作時都會調用key元素的hashCode和equals方法，所以如果是我們自定義的類，需要重寫hashCode和equals方法。而重寫hashCode這里就不再講解，編譯器可以自動生成(兩者一般一起生成)。

equals之前提過是Object的方法，hashCode也是，但當時我們沒有說，現(xiàn)在我們簡要看看：

看常規(guī)協(xié)定中的前兩點我們可以知道equals和hashCode

方法一般是一起重寫的，而且如果equals方法比較兩個對象返回true，那么兩個對象的hashCode返回值也是一樣的。

在HashMap中允許key和value為null，但因為key為null的時候hash(key)返回0，任何數(shù)與0進行&(與)運算都為0，所以key為null的鍵值只會存儲在數(shù)組下標為0的位置。所以在HashMap中key為null的鍵值只有一個，但value為null的鍵值可以多個。

因為HashMap的無序不可重復，所以又有同一個鏈表/紅黑樹中的key的哈希值是一樣的，同一個鏈表/紅黑樹下的key調用equals方法進行比較一定返回false。

HashMap的底層是數(shù)組加鏈表的這種結構也被稱為哈希表/散列表。之所以要重寫hashCode是因為如果哈希值如果變成了定值，那么哈希表就會變成一個純單向鏈表/紅黑樹；哈希值如果都不一樣，那么哈希表就會變成一個純數(shù)組。而沒有重寫hashCode的話哈希表就會變成一個純數(shù)組。以上兩種情況我們都稱為散列分布不均勻。

我們在看HashMap的常量和屬性中，對于初始化容量中的注釋我們需要知道：

The default initial capacity - MUST be a power of two.

默認初始化的容量-必須是2的冪。這是不僅為了提高效率，而且是為了達到散列分布均勻。

Hashtable

Hashtable大致上都和HashMap一致，這里重點講解兩者的區(qū)別：

底層不是Node數(shù)組，而是Entry數(shù)組。

默認初始容量為11，默認加載因子為0.75

擴容機制用rehash方法，新容量是原容量的兩倍+1.

看注釋的@exception那里，會發(fā)現(xiàn)在Hashtable中不能向key或value儲存null，會報空指針異常。而且所有供外部使用的方法都有synchronized關鍵字修飾。也即是說Hashtable是線程安全的，而HashMap是非線程安全的。所以Hashtable的效率比HashMap低。并且Hashtable的哈希值直接由key的hashCode方法確定。

Properties

作為Hashtable的子類，Hashtable有的它都有了，直接看它與Hashtable的不同：

從該方法我們可以知道Properties是專門用來儲存String類型的key和value。因此也稱為屬性類。我們可以通過以上的setProperty來設置鍵值。

用getProperty來通過key獲取value。如果我們在設置鍵值的時候調用put方法傳入非字符串value的時候，那么調用getProperty就會把value轉換為null。如果調用put方法傳入非字符串key的時候那getProperty就不能用了。不過是一般是沒有人用Properties來放非字符串類型數(shù)據(jù)的。

TreeMap

對于TreeMap，也是一個挺重要的部分。作為SortedMap下的實現(xiàn)類，不僅實現(xiàn)了無序不可重復，而且實現(xiàn)了自動排序。其底層是一個紅黑樹。

鑒于紅黑樹出現(xiàn)那么多次，現(xiàn)在簡單介紹下紅黑樹的一些特點。先看看簡單的二叉查找樹：

二叉查找樹的特點就是只有左小右大的原則進行排序，因此可能會出現(xiàn)以下的情況：

這時候說它是二叉查找樹也不像，更像一個鏈表。這時候，紅黑樹就可以極大程度的解決這個問題：

從以上圖片就可以知道紅黑樹的每個節(jié)點不是紅就是黑的；根節(jié)點總是黑色的；如果節(jié)點是紅色的，那么字節(jié)點一定是黑色(反之不一定)；為了保證樹的平衡性，先根據(jù)左小右大的原則進行排序后，會對樹進行檢測其平衡性，如果不平衡，會進行一系列的旋轉，改色等操作來保持平衡。感興趣的讀者可以進入

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

這個網(wǎng)站，里面模擬了很多數(shù)據(jù)結構。

?

接下來我們就慢慢看TreeMap這個實現(xiàn)類。

基本屬性

comparator，比較器。上面的SortedMap的comparator

方法可以返回它。不過重點不是這個，是等下怎么實現(xiàn)這個比較器。root是紅黑樹的根。size紅黑樹的節(jié)點個數(shù)。modCount統(tǒng)計TreeMap結構改變次數(shù)。

Entry靜態(tài)內部類

可以看到在TreeMap中，一個Entry有著六個屬性。分別對應著我們上述的結構。left表示左節(jié)點，right表示右節(jié)點，parent表示上層節(jié)點，color表示當前節(jié)點是紅還是黑(黑為true，紅為false)。

構造方法

無參的構造方法是沒有比較器的，我們可以通過在構造方法中傳入比較器使TreeMap集合有比較器，那么有比較器和沒有比較器有什么區(qū)別呢？我們先看put方法。

排序機制

在講解排序機制前，我們先看看TreeMap能不能添加自定義的類：

我們會發(fā)現(xiàn)居然報了類型轉換異常，而且是不能轉換為Comparable類異常。

但是添加進去String類或者Integer為什么就可以了呢？其實很簡單，它們底層都實現(xiàn)了上述的Comparable接口。

接下來我們就通過put的源代碼來弄清楚為什么會報錯，并了解TreeMap底層是如何實現(xiàn)排序的：

這里就不像HashMap那樣可以看下簡單的擴容和數(shù)組下標計算方法就行，這里設計比較的機制，所以我們需要將整個代碼都看一遍。里面也有一個重要方法compare：

看上圖put方法的第14行+第17行和第26行+第30行，可以發(fā)現(xiàn)當TreeMap中有比較器的時候會調用比較器的compare方法來確定key的位置，而當TreeMap中沒有比較器的時候會先把key強制轉換為Comparable類，并使用Comparable類的compareTo方法來確定key的位置。所以到這里我們大概就可以總結出TreeMap實現(xiàn)排序的兩種方式：

1、添加進去的key對應的類必須實現(xiàn)Comparable接口。

2、自己寫一個類實現(xiàn)Comparator接口。在構造TreeMap的時候傳進去。

那里面的排序規(guī)則怎么寫呢？我們先看有比較器和沒有比較器put方法是怎么添加的我們再來確定怎么寫規(guī)則：

可以看出就是紅黑樹的結構，這時候我們就開始思考要怎么寫排序比較好了。

1

先從第一種開始：假如我有一個貓類，確定它的大小想要根據(jù)年齡的大小來排，我們就可以像以下的格式寫：

仔細思考下，是不是就和源代碼的排序規(guī)則對上了。不同的規(guī)則實現(xiàn)方式也有所不同，比如：判斷貓類對象的大小我們想先根據(jù)年齡的大小排，但如果年齡相同，想根據(jù)它的體重排，那么代碼就可以改成如下的形式：

當然如果比較規(guī)則中需要比較的有字符串類型的，可以直接調用String類實現(xiàn)的compareTo方法就可以。

2

第二種就是實現(xiàn)一個比較器了，還是按以上的貓類來看，我們簡單點，就根據(jù)年齡來確定大小，于是就有：

有沒有讀者感覺這樣實現(xiàn)Comparator接口有點麻煩呢？確定有點，但我們可以使用匿名內部類來簡化：

是不是感覺好多了？但光說沒用，我們通過Map的兩種遍歷方式來看上述實現(xiàn)比較之后的效果。

Map實現(xiàn)類的遍歷方式?

keySet

第一種就是用Map的方法keySet

這個方法返回一個關于key的Set集合，這時候map可以根據(jù)key獲取value，因此我們就可以用foreach或iterator進行遍歷：

注意用iterator的時候需要將next指向的key先取出來，如果直接用next：

因為每調用一次next方法，迭代器的指針會向后移，所以我們也發(fā)現(xiàn)了第一次輸出的cat對象對應的value是下一個cat對象對應的value。而走第二次while的時候，代碼塊里又執(zhí)行了兩次next，加上第一次while的時候走的兩次，總共有4下next，所以指針往后移了4次，當移動最后一次的時候指針沒有指向元素，因此就會報NoSuchElementException異常。

entrySet

這個方法返回一個Map.Entry的Set集合。而Map.Entry是Map的一個內部類：

需要知道的是，這里返回的是一個接口，說明用了多態(tài)，其內部是Map.Entry的實現(xiàn)類，方法肯定也實現(xiàn)了，在這里我們只需要知道我們可以通過getKey和getValue方法來獲取Map.Entry的key和value：

也是一樣用迭代器或foreach遍歷。Iterator的遍歷注意事項和上面的keySet一致。

相同的元素，把TreeMap改成HashMap就沒有排序的效果，而且key相同覆蓋value：

TreeMap續(xù)

看完了遍歷方式，我們會發(fā)現(xiàn)輸出TreeMap的鍵值的時候是根據(jù)key的從小到大規(guī)則排的，原因之一是我們在實現(xiàn)比較的時候就是實現(xiàn)左小右大，還有一點就是TreeMap在遍歷的時候是采用中序遍歷(左根右)。這里就不拓展了。而且后者我們是無法修改的，但前者我們可以修改，就是在實現(xiàn)比較的時候兩者的位置調換：

這時候就實現(xiàn)了從大到小排了。

對于TreeMap還有一點需要知道的，在以上的代碼中我們并沒有發(fā)現(xiàn)TreeMap有調用key的equals方法，所以在TreeMap中，存放自定義類的時候可以不寫equals方法，但最好還是寫上。

終于！

到這Map終于是差不多完結了，這時候我們回過頭看Set中的HashSet和TreeSet。不用慌，就看兩者底層的add方法就能說明問題(HashSet和TreeSet的add底層差不多，直接看HashSet的)：

可以看到底層調用Map的put方法那個PRESENT其實是一個用處不大的Object類：

而put方法返回的是value的值，這里直接賦值為null。

因此，我們可以認為Set是value為null的Map。所以Set的無序不可重復更多的是依賴于Map的key無序不可重復。不過還要記得Set的常用方法是在Collection里面。

	ArrayList	HashMap	TreeMap
自定義類 要求	最好重寫equals	一定需要 重寫equals和hashCode	不一定重寫 equals， 但一定要實現(xiàn)比較。

總結

以上是生活随笔為你收集整理的map集合怎么取value值最大的前三_Java之集合(下)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。