【算】從散列表到HashMap

zoomdong 發布于2019-08-15 15:12 / 2238人閱讀

數組

數組是我們比較熟悉的一種數據結構：固定大小，索引（下標）對應的槽位用以存儲數據：

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

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

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

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

把余數作為下標，存入數組。

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

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

散列函數

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

散列函數有兩個特征：

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

盡可能分散

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

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

字符串

字符串的本質是字符數組，字符在ascii碼表上就是數字。

對象

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

當然具體的算法要比取來的復雜，比如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()方法，就是我們一直在聊的散列函數！

Tips:

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

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

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

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

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

是時候讓另一種數據結構登場了——鏈表。

鏈表

數組占用相鄰的整塊內存，且固定大小；鏈表則不然，由于結構上存在指向下一個節點（內存地址）的指針，因此不要求內存地址連續，大小也不固定。

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

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

放入 Put

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

獲取 Get

根據Key值，計算hashCode。如果hashCode，也就是索引對應的槽位為空或只有一個元素，直接返回該值；如果hashCode對應的槽位中的數據為鏈表結構，對鏈表進行遍歷，直到找到與KEY equals的對象。

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

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

HashMap也是這么做的，初始值2^4=16的數組，默認0.75的擴容因子；當元素個數超過閾值，即16*0.75=12的時候，觸發resize方法進行擴容。數組大小翻倍，元素rehash后放入相應的槽位。

可以看出，散列表就是HashMap的底層結構。當然了，JDK 1.8版本對其還有紅黑樹等優化，感興趣可查閱 Java 8系列之重新認識HashMap

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

GPU云服務器云服務器 HashMap _HashMap java hashmap hashmap hashtable

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68919.html

每周一練之數據結構與算法（Dictionary 和 HashTable）

摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 Hash...

eternalshallow 2019-08-26 13:51 評論0 收藏0
每周一練之數據結構與算法（Dictionary 和 HashTable）

摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 HashTable。下面是之前分享的鏈接： 1.每周一練之數據結構與算法（Stack） 2.每周一練之數據結構與算法（LinkedList） 3.每周一練之數據結構...

ingood 2019-05-22 14:21 評論0 收藏0
散列表結構字典與集合

摘要：散列表結構字典與集合散列表散列表結構是字典和集合的一種實現方式。使用散列表存儲數據時，通過一個散列函數將鍵映射為一個數字，這個數字范圍是到列表長度。即使使用一個高效的散列函數，仍然存在將兩個鍵映射為同一個值的可能，這種現象稱為碰撞。散列表結構字典與集合散列表散列表(Hash Table)結構是字典(Dictionary)和集合(Set)的一種實現方式。散列算法的作用是盡可能快...

Bamboy 2019-07-31 11:13 評論0 收藏0
我對JS散列表的簡單學習

摘要：對散列表的簡單學習類也叫類，是類的一種散列表實現方式。鍵值散列函數散列值形成散列表地址數據鍵值對相關操作方法創建一個散列表實現一個散列函數，即將碼值相加的方法。對JS散列表的簡單學習 HashTable類也叫HashMap類，是Dictionary類的一種散列表實現方式。散列算法的作用是盡可能快的在數據結構中找到一個值。在之前的學習中，如果你想要獲得數據結構中的一個值，需要遍歷整...

lindroid 2019-08-21 15:33 評論0 收藏0