資訊專欄INFORMATION COLUMN
摘要：散列表其實是基于數(shù)組實現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。根據(jù)下圖你更能理解散列表哈希函數(shù)結(jié)合上面的理解，你應(yīng)該可以想到，其實散列表的關(guān)鍵就在于哈希函數(shù)的實現(xiàn)。
1. 什么是散列表？
散列表（Hash Table）又叫做哈希表，是一種很常用的數(shù)據(jù)結(jié)構(gòu)。散列表其實是基于數(shù)組實現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。先來舉一個簡單的例子，來認(rèn)識一下什么是散列表。
假如在學(xué)校的運動會上，每個運動員的胸前都會標(biāo)識自己的號碼，編號是1，2，3……，這樣的話，我們可以很容易的將運動員信息存儲在數(shù)組當(dāng)中，運動員的編號就是數(shù)組的下標(biāo)。但是會存在這樣一種情況，假如運動員的編號不是順序排列的，而是需要加上更多的信息，比如年級，班級，例如一個運動員的編號是15030711，15是年級，03是專業(yè)，07是班級，11是順序號，這樣的話我們該怎么存儲運動員信息呢？
其實也不難，我們只需要截取運動員編號的最后兩位，作為數(shù)組的下標(biāo)存儲在數(shù)組中，當(dāng)需要根據(jù)編號查詢信息的時候，我們也同樣截取編號最后兩位來進(jìn)行查詢。這就是很典型的散列思想。
選手的編號叫做 鍵 ， 把運動員編號轉(zhuǎn)換為數(shù)組下標(biāo)的方法叫做 散列函數(shù)（或哈希函數(shù)）， 通過散列函數(shù)計算得到的值叫做 散列值（或哈希值） 。
根據(jù)下圖你更能理解散列表：
2. 哈希函數(shù)
結(jié)合上面的理解，你應(yīng)該可以想到，其實散列表的關(guān)鍵就在于哈希函數(shù)的實現(xiàn)。哈希函數(shù)，顧名思義，其實就是一個函數(shù)，key 就是鍵值，經(jīng)過 hash(key) 得到的值就是哈希值。
哈希函數(shù)的設(shè)計有三個原則：
通過哈希函數(shù)計算得到的哈希值是一個非負(fù)的整數(shù)。
如果 key1 = key2，那么 hash(key1) = hash(key2)。
如果 key1 != key2，那么 hash(key1) != hash(key2)。
前面兩點其實很好理解，第一點，要求是一個非負(fù)的整數(shù)，這是因為數(shù)組的下標(biāo)是從 0 開始的，第二點，如果 key 相同，那么通過哈希函數(shù)得到的哈希值也相同。
第三點稍微有點不好理解，key1 不等于 key2，那么哈希值也是不相等的，這只是一種理想的狀況，但是在實際情況中，無法避免這種哈希沖突 。
3. 哈希沖突
哈希沖突，又叫哈希碰撞，是哈希函數(shù)可能會遇到的問題，即不同的 key 值經(jīng)過哈希函數(shù)計算之后，可能得到相同的哈希值，那么這種狀況該怎么解決呢？一般是通過兩種方式：
開放尋址法
鏈表法
開放尋址法可以通過線性探測這種方式來實現(xiàn)，比如我們的一個 key 經(jīng)過哈希函數(shù)得到哈希值之后，相應(yīng)的存儲位置已經(jīng)被占用，那么我們遍歷散列表，找到一個空閑的位置，將數(shù)據(jù)插入。
例如下圖，標(biāo)記為黃色的是已經(jīng)有數(shù)據(jù)，標(biāo)記為紅色的是空閑空間，一個 key 經(jīng)過 hash 哈希函數(shù)之后的存儲位置為 2，但是下標(biāo)為 2 的的地方已經(jīng)有數(shù)據(jù)了，所以就重新探測一個空的位置。
第二種方式是鏈表法，這種方式會更加簡單，也更加適用。例如下圖，在每一存儲位置，都會有相應(yīng)的鏈表，如果哈希值相同，我們直接將數(shù)據(jù)存放在存儲位置對應(yīng)的鏈表中。
但是這種方式也可能會存在問題，比如說哈希函數(shù)設(shè)計的不合理，導(dǎo)致大量的數(shù)據(jù)都集中在一條鏈表中，這樣的話，數(shù)據(jù)的插入和查找速度就會急劇退化為O(n)。針對這種情況，我們可以使用更加優(yōu)秀的動態(tài)數(shù)據(jù)結(jié)構(gòu)代替鏈表，例如紅黑樹、跳表等。這樣，就算數(shù)據(jù)全都集中在一個節(jié)點上，數(shù)據(jù)的查詢效率也不會下降得太厲害。
4. 散列表的具體應(yīng)用
其實，散列表和鏈表在很多時候都是結(jié)合在一起使用的，接下來就看看散列表的兩個具體應(yīng)用：LRU（最近最少使用策略，Least Recently Used）緩存淘汰算法和 Java 的 LinkedHashMap。
1.LRU 緩存淘汰算法
首先，該怎么理解 LRU，即最近最少使用策略呢？舉個簡單的例子，比如你買了很多書，書架上漸漸放滿了，當(dāng)你有新的書的時候，需要將原來的書拿掉一些，騰出新的位置來。這樣的話，你肯定會拿掉那些最近很少使用到的那些書，這就是一種最近最少使用策略。
其實可以用單鏈表實現(xiàn)一個LRU緩存淘汰算法，具體可以這樣做：我們維護(hù)一個有限的緩存空間，如果空間不夠，需要淘汰緩存的話，我們直接將鏈表頭部的數(shù)據(jù)刪除即可。當(dāng)要緩存某個數(shù)據(jù)的時候，我們需要查找這個數(shù)據(jù)，如果找到了，將其放置在鏈表尾部，如果沒找到，則將數(shù)據(jù)插入到鏈表尾部。因為涉及到的查找操作需要遍歷鏈表，時間復(fù)雜度是O(n)，所以我們可以用散列表加上雙向鏈表來實現(xiàn)，將時間復(fù)雜度降為O(1)。具體該怎么實現(xiàn)呢？
先來看看下面實現(xiàn)的圖：
首先，如果空間不夠，我們直接將雙向鏈表頭部的元素刪除；查找一個元素，我們可以在接近 O(1) 的時間復(fù)雜度找到該元素，并且將其插入到鏈表的尾部；刪除一個元素，由于雙向鏈表保存了上一個鏈表的指針，所以能夠在O(1) 的時間內(nèi)刪除；添加一個元素，如果此元素已經(jīng)在鏈表中，則直接將該元素插入到鏈表尾部，如果不在鏈表中，直接將元素插入到鏈表尾部，如果緩存滿了，則刪除鏈表頭部元素之后才添加。
2.LinkedHashMap
如果熟悉 Java 的話，肯定會經(jīng)常用到 LinkedHashMap 這個容器，它與 HashMap 唯一的區(qū)別就是，LinkedHashMap 能夠按照插入次序依次遍歷得到數(shù)據(jù)，這個功能是怎么實現(xiàn)的呢？其實和上面的結(jié)構(gòu)圖很類似，插入到 HashMap 中的數(shù)據(jù)用雙向鏈表連接起來，然后按照遍歷鏈表的方法依次得到數(shù)據(jù)，這樣就能夠?qū)崿F(xiàn)有序輸出數(shù)據(jù)了。
好了，散列表就基本上講完了。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/73947.html
摘要：什么是散列表和散列函數(shù)哈希表，也叫散列表，是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。根據(jù)鍵值從散列表中移除值。請實現(xiàn)散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習(xí)題，上周忘記發(fā)啦，這周是復(fù)習(xí) Dictionary 和 Hash...
摘要：什么是散列表和散列函數(shù)哈希表，也叫散列表，是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。將字典的所有鍵名以數(shù)組的形式返回。根據(jù)鍵值從散列表中移除值。這是第五周的練習(xí)題，上周忘記發(fā)啦，這周是復(fù)習(xí) Dictionary 和 HashTable。 下面是之前分享的鏈接： 1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（Stack） 2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList） 3.每周一練 之 數(shù)據(jù)結(jié)構(gòu)...
摘要：定義散列表是字典鍵值對的一種實現(xiàn)方式。根據(jù)鍵值從散列表中移除值。分離鏈接分離鏈接法在散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面。一個表現(xiàn)良好的散列函數(shù)應(yīng)該有較好的插入和查找性能且有較低的沖突可能性。 定義 散列表是字典（鍵、值對）的一種實現(xiàn)方式。每次在字典中獲取一個值，都需要重復(fù)遍歷字典，如果用散列表，字典中的每個key都對應(yīng)一個確定的位置，從而不再需要遍歷。以電子郵件地址簿為例...
摘要：小結(jié)實現(xiàn)了字典和哈希表感覺沒有想象中那么困難，當(dāng)然這還是開始。 本系列所有文章：第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹 字典 不是新華字典哦，這里的字典也稱作_映射_，是一種數(shù)據(jù)結(jié)構(gòu)，跟set集合很相似的一種數(shù)據(jù)結(jié)構(gòu)，都可以用來...
摘要：在字典中，存儲的是鍵，值，集合可以看作值，值的形式存儲元素，字典也稱為映射方法描述備注向字典中添加新元素通過某個鍵值從字典中移除對應(yīng)的數(shù)據(jù)值判斷某個鍵值是存在于這個字典中通過鍵值獲取對應(yīng)的數(shù)據(jù)值返回字典所有元素的數(shù)量刪除字典中所有元素將字典 在字典中，存儲的是[鍵，值]，集合可以看作[值，值]的形式存儲元素，字典也稱為映射 方法 描述 備注 set(key,...
閱讀 863·2023-04-25 15:13
閱讀 1479·2021-11-22 12:03
閱讀 880·2021-11-19 09:40
閱讀 1983·2021-11-17 09:38
閱讀 1800·2021-11-08 13:18
閱讀 703·2021-09-02 15:15
閱讀 1813·2019-08-30 15:54
閱讀 2788·2019-08-30 11:12
