【算】從散列表到HashMap

zoomdong 發(fā)布于2019-08-15 15:12 / 2237人閱讀

數(shù)組

數(shù)組是我們比較熟悉的一種數(shù)據(jù)結(jié)構(gòu)：固定大小，索引（下標(biāo)）對應(yīng)的槽位用以存儲數(shù)據(jù)：

我們要在數(shù)組中查找一個值，比如紅框圈中的 元素5 ，可以通過遍歷或者排序后二分的方式達(dá)到目的。沒有更快捷的查找方式了嗎？顯然是有的，比如Map。
我們對存 / 取動一動腦筋，還是上圖的那些元素，假如我們這樣存：

此時，想獲取 元素5 很容易，直接array[5]就可以，但問題也同樣突出，數(shù)組的length變得很大。這個例子中，最大的元素是79，還可以接受，如果最大元素是98277呢？更大呢？

我們以取余數(shù)的方式作為變通：對于元素集合{8,1,5,6,82,33}，還將這些元素放入最開始的length為6 的數(shù)組中。分別對元素除6取余，計算結(jié)果如下：

8->2 1->1 5->5 6->0 82->4 33->3

把余數(shù)作為下標(biāo)，存入數(shù)組。

此時，我們想在數(shù)組中查找是否存在元素5，只需對要查找的值——元素5，按數(shù)組的length取余5%6=5，直接array[5]即可。

這里的按數(shù)組的length取余，扮演的就是散列函數(shù)的角色！

散列函數(shù)

什么是散列函數(shù)？可以理解為，將元素盡可能分散的打入到數(shù)組中的函數(shù)。

散列函數(shù)有兩個特征：

對同一個元素，每次計算得到的值相同。比如上面的取余函數(shù)，5%6總是等于5。

盡可能分散

同時也有兩個疑問，分別看下：

問題1：數(shù)字可以取余，字符串和對象的散列函數(shù)怎么搞？

字符串

字符串的本質(zhì)是字符數(shù)組，字符在ascii碼表上就是數(shù)字。

對象

對象是各種屬性構(gòu)成的，這些屬性包括基本類型、字符串等等。

當(dāng)然具體的算法要比取來的復(fù)雜，比如String的hashCode算法：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

沒錯，各種hashCode()方法，就是我們一直在聊的散列函數(shù)！

Tips:

圍繞hashCode有幾道經(jīng)典面試題，正值跳槽季，給大家安利一下：

1.Object的hashCode是不是內(nèi)存地址？
2.什么情況下會覆寫hashCode()方法？你有沒有覆寫過這個方法？
3.如果對象A equals 對象B，則對象A和對象B的hashCode是否相等？反過來，對象A和對象B的hashCode值相等，equals是否返回true？

問題2：不同元素的散列函數(shù)計算結(jié)果相同，怎么解決？

到目前為止，一切很順利。length=6的數(shù)組完成了對集合{8,1,5,6,82,33}所有元素的安置，但這是最簡單的情況。如果再增加一個數(shù)字，就選西方人認(rèn)為不怎么吉利的 13 好了，取余計算13%6=1，原本應(yīng)該放在索引為1的槽上，而我們的數(shù)組現(xiàn)在已經(jīng)滿員了。

這就是hash沖突的問題，怎么解決？顯然直接覆蓋并不合理，那樣會丟掉原有的元素1。想想HashMap，如果發(fā)生了hash沖突，就丟棄原有值，這種做法使用者肯定無法接收。

是時候讓另一種數(shù)據(jù)結(jié)構(gòu)登場了——鏈表。

鏈表

數(shù)組占用相鄰的整塊內(nèi)存，且固定大小；鏈表則不然，由于結(jié)構(gòu)上存在指向下一個節(jié)點（內(nèi)存地址）的指針，因此不要求內(nèi)存地址連續(xù)，大小也不固定。

因為結(jié)構(gòu)的緣故，鏈表在插入、刪除方面更有優(yōu)勢，修改指針指向即可；而數(shù)組在快速定位某槽位上更具優(yōu)勢，鏈表只能從頭遍歷。

加入鏈表后，散列表升級成這樣：

放入 Put

元素13放入時，計算hashCode為1（姑且按取余的方式進(jìn)行理解）。如果索引為1的槽位為空，直接放入元素；如果索引為1的槽位已經(jīng)存在元素，將該槽位存儲結(jié)構(gòu)變更為鏈表。

獲取 Get

根據(jù)Key值，計算hashCode。如果hashCode，也就是索引對應(yīng)的槽位為空或只有一個元素，直接返回該值；如果hashCode對應(yīng)的槽位中的數(shù)據(jù)為鏈表結(jié)構(gòu)，對鏈表進(jìn)行遍歷，直到找到與KEY equals的對象。

如果hash沖突比較多，會發(fā)生什么情況？

鏈表的無限擴(kuò)張，會使得查詢變得緩慢，我們最初不就是想用散列表解決快速查找的問題嗎？如上圖這種情況，散列表幾乎失去了意義，又回到了遍歷查找的時代，這也是散列函數(shù)盡可能將元素均勻分布的原因。怎么解決？數(shù)組快要滿時，對其擴(kuò)容！

HashMap也是這么做的，初始值2^4=16的數(shù)組，默認(rèn)0.75的擴(kuò)容因子；當(dāng)元素個數(shù)超過閾值，即16*0.75=12的時候，觸發(fā)resize方法進(jìn)行擴(kuò)容。數(shù)組大小翻倍，元素rehash后放入相應(yīng)的槽位。

可以看出，散列表就是HashMap的底層結(jié)構(gòu)。當(dāng)然了，JDK 1.8版本對其還有紅黑樹等優(yōu)化，感興趣可查閱 Java 8系列之重新認(rèn)識HashMap

ok，本篇文章到此就告一段落了，下一篇我們探討下圖的經(jīng)典問題——最短路徑，敬請關(guān)注！