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

系列文章目錄

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

任何數(shù)據(jù)結(jié)構(gòu)的產(chǎn)生總對(duì)應(yīng)著要解決一個(gè)實(shí)際的問題, HashMap的產(chǎn)生要解決問題就是:

如何有效的 存 取 一組 key-vaule 鍵值對(duì)

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

key-value鍵值對(duì)

一組

存

取

下面我們逐個(gè)來思考:

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

class Node {
    K key;
    V value;
}

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

是不是很簡(jiǎn)單?

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

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

這里我們總結(jié)一下:

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

至于這個(gè)接口需要定義哪些方法, 我們暫不細(xì)表.

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

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

那么我們要如何存儲(chǔ)這些鍵值對(duì)的集合呢?

其實(shí)換個(gè)問法可能更容易回答:

應(yīng)該怎樣存儲(chǔ)一組對(duì)象?

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

在java中, 存儲(chǔ)一個(gè)對(duì)象的集合無外乎兩種方式:

數(shù)組

鏈表

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

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

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

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

Node[] table;

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

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

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

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

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

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

這里插一句,使用Hash算法同樣補(bǔ)足了數(shù)組插入和刪除性能差的短板, 我們知道, 數(shù)組之所以插入刪除性能差是因?yàn)樗琼樞虼鎯?chǔ)的, 在一個(gè)位置插入節(jié)點(diǎn)或者刪除節(jié)點(diǎn)需要一個(gè)個(gè)移動(dòng)它的后續(xù)節(jié)點(diǎn)來騰出位或者覆蓋位置.

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

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

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

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

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

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

至此, 我們對(duì)key-value鍵值對(duì)的表示變?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;
    }
    ...
}

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

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

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

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

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

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

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

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

再說回?cái)U(kuò)容, 有的同學(xué)就要問了, 咱上面不是將數(shù)組的每一個(gè)元素轉(zhuǎn)變成鏈表了嗎? 就算此時(shí)節(jié)點(diǎn)數(shù)超過了數(shù)組大小, 新加的節(jié)點(diǎn)會(huì)存在數(shù)組某一個(gè)位置的鏈表里啊, 鏈表的大小不限, 可以存儲(chǔ)任意數(shù)量的節(jié)點(diǎn)啊!

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

如果我們?cè)噲D指望利用鏈表來擴(kuò)容的話, 當(dāng)一個(gè)存儲(chǔ)桶的中的鏈表越來越大, 在這個(gè)鏈表上的查找性能就會(huì)很差(退化成順序查找了)

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

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

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

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

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

關(guān)于HashMap的設(shè)計(jì)思路, 我們可以用一句話來概括:

不忘初心 !

我們?cè)O(shè)計(jì)HashMap的初心是什么呢, 是找到一種方法, 可以存儲(chǔ)一組鍵值對(duì)的集合, 并實(shí)現(xiàn)快速的查找.

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

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

==> 引入Hash算法又導(dǎo)致了Hash沖突

==> 為了解決Hash沖突, 我們采用鏈地址法, 在沖突位置轉(zhuǎn)為使用鏈表存儲(chǔ).

==> 鏈表存儲(chǔ)過多的節(jié)點(diǎn)又導(dǎo)致了在鏈表上節(jié)點(diǎn)的查找性能的惡化

==> 為了優(yōu)化查找性能, 我們?cè)阪湵黹L度超過8之后轉(zhuǎn)而將鏈表轉(zhuǎn)變成紅黑樹, 以將 o(n)復(fù)雜度的查找效率提升至o(log n)

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

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

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

(完)

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

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