摘要：前言系列文章目錄我們都不陌生也是面試幾乎必問的考點本系列我們來深入思考有關的設計思想和實現(xiàn)細節(jié)解決了什么問題任何數(shù)據(jù)結構的產(chǎn)生總對應著要解決一個實際的問題的產(chǎn)生要解決問題就是如何有效的存取一組鍵值對鍵值對是最常使用的數(shù)據(jù)形式如何有效地存

系列文章目錄

HashMap我們都不陌生, 也是java面試幾乎必問的考點, 本系列我們來深入思考有關HashMap的設計思想和實現(xiàn)細節(jié).

任何數(shù)據(jù)結構的產(chǎn)生總對應著要解決一個實際的問題, HashMap的產(chǎn)生要解決問題就是:

如何有效的 存 取 一組 key-vaule 鍵值對

key-value鍵值對是最常使用的數(shù)據(jù)形式, 如何有效地存取他們是眾多語言都需要關注的問題. 注意這里有四個關鍵字:

key-value鍵值對

一組

存

取

下面我們逐個來思考:

在java這種面向?qū)ο蟮恼Z言中, 表示一個數(shù)據(jù)結構自然要用到類, 由于對于鍵值對的數(shù)據(jù)類型事先并不清楚, 顯而易見這里應該要用泛型, 則, 表示key-value鍵值對最簡單的形式可以是:

class Node {
    K key;
    V value;
}

這里我們自定義一個Node類, 它只有兩個屬性, 一個 key屬性表示鍵, 一個value屬性表示值, 則這個類就代表了一個 key-value鍵值對.

是不是很簡單?

當然, 我們還需要定義一些方法來操縱這兩個屬性, 例如get和set方法等,不過根據(jù)設計原則, 我們應該面向接口編程, 所以應該定義一個接口來描述需要執(zhí)行的操作, 這個接口就是Entry, 它只不過是對于Node這個類的抽象, 在java中, 這個接口定義在Map這個接口中, 所以上面的類可以改為:

class Node implements Map.Entry{
    K key;
    V value;
}

這里我們總結一下:

我們定義了一個Node類來表示一個鍵值對, 為了面向接口編程, 我們抽象出一個 Entry接口, 并使Node類實現(xiàn)了這個接口.

至于這個接口需要定義哪些方法, 我們暫不細表.

這樣, 到目前為止, 我們完成了對于 key-value 鍵值對的表示.

在常見的業(yè)務邏輯中, 我們常常需要處理一組鍵值對的集合, 將一組鍵值對存儲在一處, 并根據(jù)key值去查找對應的value.

那么我們要如何存儲這些鍵值對的集合呢?

其實換個問法可能更容易回答:

應該怎樣存儲一組對象?

(畢竟鍵值對已經(jīng)被我們表示為Node對象了)

在java中, 存儲一個對象的集合無外乎兩種方式:

數(shù)組

鏈表

關于數(shù)組和鏈表的優(yōu)缺點大家已經(jīng)耳熟能詳了:

數(shù)組大小有限, 查找性能好, 插入和刪除性能差

鏈表大小不限, 查找性能差, 插入和刪除性能好

這里應該選哪種形式呢? 那得看實際的應用了, 在使用鍵值對時, 查找和插入,刪除等操作都會用到, 但是在實際的應用場景中, 對于鍵值對的查找操作居多, 所以我們當然選擇數(shù)組形式.

Node[] table;

總結: 我們選擇數(shù)組形式來存儲key-value對象.

為了便于下文描述, 我們將數(shù)組的下標稱為索引(index), 將數(shù)組中的一個存儲位置稱為數(shù)組的一個存儲桶(bucket).

前面已經(jīng)講到, 我們選擇數(shù)組形式來存儲key-value對象, 以利用其優(yōu)良的查找性能, 數(shù)組之所以查找迅速, 是因為可以根據(jù)索引(數(shù)組下標)直接定位到對應的存儲桶(數(shù)組所存儲對象的位置.)
但是實際應用中, 我們都是通過key值來查找value值, 怎么辦呢?

一種方式就是遍歷數(shù)組中的每一個對象, 查看它的key是不是我們要找的key, 但是很明顯, 這種方式效率低下(而且這不就是鏈表的順序查找方式嗎?) 完全違背了我們選擇數(shù)組來存儲鍵值對的初衷.

為了利用索引來查找, 我們需要建立一個 key -> index 的映射關系, 這樣每次我們要查找一個 key時, 首先根據(jù)映射關系, 計算出對應的數(shù)組下標, 然后根據(jù)數(shù)組下標, 直接找到對應的key-value對象, 這樣基本能以o(1)的時間復雜度得到結果.

這里, 將key映射成index的方法稱為hash算法, 我們希望它能將 key均勻的分布到數(shù)組中.

這里插一句,使用Hash算法同樣補足了數(shù)組插入和刪除性能差的短板, 我們知道, 數(shù)組之所以插入刪除性能差是因為它是順序存儲的, 在一個位置插入節(jié)點或者刪除節(jié)點需要一個個移動它的后續(xù)節(jié)點來騰出位或者覆蓋位置.

使用hash算法后, 數(shù)組不再按順序存儲, 插入刪除操作只需要關注一個存儲桶即可, 而不需要額外的操作.

這個問題其實是由上一個問題引出的, 雖然我們要求hash算法能將key均勻的分布到數(shù)組中, 但是它只能盡量做到, 并不是絕對的, 更何況我們的數(shù)組大小是有限的, 保不齊我們的hash算法將就兩個不同的key映射成了同一個index值, 這就產(chǎn)生了hash沖突, 也就是兩個Node要存儲在數(shù)組的同一個位置該怎么辦?

解決hash沖突的方法有很多, 在HashMap中我們選擇鏈地址法, 即在產(chǎn)生沖突的存儲桶中改為單鏈表存儲.(拓展閱讀: 解決哈希沖突的常用方法 )

其實, 最理想的效果是，Entry數(shù)組中每個位置都只有一個元素，這樣，查詢的時候效率最高，不需要遍歷單鏈表，也不需要通過equals去比較Key，而且空間利用率最大。

鏈地址法使我們的數(shù)組轉變成了鏈表的數(shù)組:

(圖片來自網(wǎng)絡)

至此, 我們對key-value鍵值對的表示變?yōu)?

class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    
    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...
}

我們知道, 鏈表查找只能通過順序查找來實現(xiàn), 因此, 時間復雜度為o(n), 如果很不巧, 我們的key值被Hash算法映射到一個存儲桶上, 將會導致存儲桶上的鏈表長度越來越長, 此時, 數(shù)組查找退化成鏈表查找, 則時間復雜度由原來的o(1) 退化成 o(n).

為了解決這一問題, 在java8中, 當鏈表長度超過 8 之后, 將會自動將鏈表轉換成紅黑樹, 以實現(xiàn) o(log n) 的時間復雜度, 從而提升查找性能.

(圖片來自網(wǎng)絡)

前面已經(jīng)說到, 數(shù)組的大小是有限的, 在新建的時候就要指定, 如果加入的節(jié)點已經(jīng)到了數(shù)組容量的上限, 已經(jīng)沒有位置能夠存儲key-value鍵值對了, 此時就需要擴容.

但是很明顯, 我們不會等到火燒眉毛了才想起來要擴容, 在實際的應用中, 數(shù)組空間已使用3/4之后, 我們就會括容.

為什么是0.75呢, 官方文檔的解釋是:

the default load factor (.75) offers a good tradeoff between time and space costs.

想要更深入的理解可以看這里.

再說回擴容, 有的同學就要問了, 咱上面不是將數(shù)組的每一個元素轉變成鏈表了嗎? 就算此時節(jié)點數(shù)超過了數(shù)組大小, 新加的節(jié)點會存在數(shù)組某一個位置的鏈表里啊, 鏈表的大小不限, 可以存儲任意數(shù)量的節(jié)點啊!

沒錯, 理論上來說這樣確實是可行的, 但這又違背了我們一開始使用數(shù)組來存儲一組鍵值對的初衷, 還記得我們選擇數(shù)組的原因是什么嗎? 為了利用索引快速的查找!

如果我們試圖指望利用鏈表來擴容的話, 當一個存儲桶的中的鏈表越來越大, 在這個鏈表上的查找性能就會很差(退化成順序查找了)

為此, 在數(shù)組容量不足時, 為了繼續(xù)維持利用數(shù)組索引查找的優(yōu)良性能, 我們必須對數(shù)組進行擴容.

鏈表存在的意義只是為了解決hash沖突, 而不是為了增大容量. 事實上, 我們希望鏈表的長度越短越好, 或者最好不要出現(xiàn)鏈表.

上一節(jié)我們討論了擴容的時機, 接下來的另一問題就是每次多增加多少空間.

我們知道, 數(shù)組的擴容是一個很耗費CPU資源的動作, 需要將原數(shù)組的內(nèi)容復制到新數(shù)組中去, 因此頻繁的擴容必然會導致性能降低, 所以不可能數(shù)組滿了之后, 每多加一個node, 我們就擴容一次.
但是, 一次擴容太大, 導致大量的存儲空間用不完, 勢必又造成很大的浪費, 因此, 必須根據(jù)實際情況設定一個合理的擴容大小.

在HashMap的實現(xiàn)中, 每次擴容我們都會將新數(shù)組的大小設為原數(shù)組大小的兩倍.

關于HashMap的設計思路, 我們可以用一句話來概括:

不忘初心 !

我們設計HashMap的初心是什么呢, 是找到一種方法, 可以存儲一組鍵值對的集合, 并實現(xiàn)快速的查找.

==> 為了實現(xiàn)快速查找, 我們選擇了數(shù)組而不是鏈表. 以利用數(shù)組的索引實現(xiàn)o(1)復雜度的查找效率.

==> 為了利用索引查找, 我們引入Hash算法, 將 key 映射成數(shù)組下標: key -> Index

==> 引入Hash算法又導致了Hash沖突

==> 為了解決Hash沖突, 我們采用鏈地址法, 在沖突位置轉為使用鏈表存儲.

==> 鏈表存儲過多的節(jié)點又導致了在鏈表上節(jié)點的查找性能的惡化

==> 為了優(yōu)化查找性能, 我們在鏈表長度超過8之后轉而將鏈表轉變成紅黑樹, 以將 o(n)復雜度的查找效率提升至o(log n)

可見, 每一次結構的調(diào)整, 都是始終圍繞我們的初心:

實現(xiàn)快速的查找

來進行的, 始終不忘這一點, 在每一次出現(xiàn)問題的時候, 一切的選擇是不是看起來就很自然了?(≧?≦)?

(完)

下一篇: 深入理解HashMap(二): 關鍵源碼逐行分析之hash算法

查看更多系列文章：系列文章目錄