資訊專(zhuān)欄INFORMATION COLUMN
摘要：散列表散列表，也叫哈希表，是根據(jù)鍵而直接訪(fǎng)問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表。
散列表
散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪(fǎng)問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢(xún)的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，這加快了查找速度。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表。
我們從上圖開(kāi)始分析
有一個(gè)集合U，里面分別是1000，10，152，9733，1555，997，1168
右側(cè)是一個(gè)10個(gè)插槽的列表（散列表），我們需要把集合U中的整數(shù)存放到這個(gè)列表中
怎么存放，分別存在哪個(gè)槽里？這個(gè)問(wèn)題就是需要通過(guò)一個(gè)散列函數(shù)來(lái)解決了。我的存放方式是取10的余數(shù)，我們對(duì)應(yīng)這圖來(lái)看
1000%10=0，10%10=0 那么1000和10這兩個(gè)整數(shù)就會(huì)被存儲(chǔ)到編號(hào)為0的這個(gè)槽中
152%10=2那么就存放到2的槽中
9733%10=3 存放在編號(hào)為3的槽中
通過(guò)上面簡(jiǎn)單的例子，應(yīng)該會(huì)有一下幾點(diǎn)一個(gè)大致的理解
集合U，就是可能會(huì)出現(xiàn)在散列表中的鍵
散列函數(shù)，就是你自己設(shè)計(jì)的一種如何將集合U中的鍵值通過(guò)某種計(jì)算存放到散列表中，如例子中的取余數(shù)
散列表，存放著通過(guò)計(jì)算后的鍵
那么我們?cè)诮又匆话阄覀儠?huì)怎么去取值呢？
比如我們存儲(chǔ)一個(gè)key為1000，value為"張三" ---> {key:1000,value:"張三"}
從我們上述的解釋?zhuān)遣皇菓?yīng)該存放在1000%10的這個(gè)插槽里。
當(dāng)我們通過(guò)key想要找到value張三，是不是到key%10這個(gè)插槽里找就可以了呢？到了這里你可以停下來(lái)思考一下。
散列表中所有可能出現(xiàn)的鍵稱(chēng)作全集U
用M表示槽的數(shù)量
給定一個(gè)鍵，由散列函數(shù)計(jì)算它應(yīng)該出現(xiàn)在哪個(gè)槽中，上面例子的散列函數(shù)h=k%M,散列函數(shù)h就是鍵k到槽的一個(gè)映射。
1000和10都被存到了編號(hào)0的這個(gè)槽中，這種情況稱(chēng)之為碰撞。
看到這里不知道你是否大致理解了散列函數(shù)是什么了沒(méi)。通過(guò)例子，再通過(guò)你的思考，你可以回頭在讀一遍文章頭部關(guān)于散列表的定義。如果你能讀懂了，那么我估計(jì)你應(yīng)該是懂了。
常用的散列函數(shù)處理整數(shù) h=>k%M （也就是我們上面所舉的例子）
處理字符串：
function h_str(str,M){
return [...str].reduce((hash,c)=>{
hash = (31*hash + c.charCodeAt(0)) % M
},0)
}
hash算法不是這里的重點(diǎn)，我也沒(méi)有很深入的去研究，這里主要還是去理解散列表是個(gè)怎樣的數(shù)據(jù)結(jié)構(gòu)，它有哪些優(yōu)點(diǎn)，它具體做了怎樣一件事。
而hash函數(shù)它只是通過(guò)某種算法把key映射到列表中。
通過(guò)上面的解釋?zhuān)覀冞@里做一個(gè)簡(jiǎn)單的散列表
散列表的組成M個(gè)槽
有個(gè)hash函數(shù)
有一個(gè)add方法去把鍵值添加到散列表中
有一個(gè)delete方法去做刪除
有一個(gè)search方法，根據(jù)key去找到對(duì)應(yīng)的值
初始化- 初始化散列表有多少個(gè)槽 - 用一個(gè)數(shù)組來(lái)創(chuàng)建M個(gè)槽
class HashTable {
constructor(num=1000){
this.M = num;
this.slots = new Array(num);
}
}
散列函數(shù)
處理字符串的散列函數(shù)，這里使用字符串是因?yàn)椋瑪?shù)值也可以傳換成字符串比較通用一些
先將傳遞過(guò)來(lái)的key值轉(zhuǎn)為字符串，為了能夠嚴(yán)謹(jǐn)一些
將字符串轉(zhuǎn)換為數(shù)組, 例如"abc" => [..."abc"] => ["a","b","c"]
分別對(duì)每個(gè)字符的charCodeAt進(jìn)行計(jì)算，取M余數(shù)是為了剛好對(duì)應(yīng)插槽的數(shù)量，你總共就10個(gè)槽,你的數(shù)值%10 肯定會(huì)落到 0-9的槽里
h(str){
str = str + "";
return [...str].reduce((hash,c)=>{
hash = (331 * hash + c.charCodeAt()) % this.M;
return hash;
},0)
}
添加
調(diào)用hash函數(shù)得到對(duì)應(yīng)的存儲(chǔ)地址(就是我們之間類(lèi)比的槽)
因?yàn)橐粋€(gè)槽中可能會(huì)存多個(gè)值，所以需要用一個(gè)二維數(shù)組去表示，比如我們計(jì)算得來(lái)的槽的編號(hào)是0，也就是slot[0]，那么我們應(yīng)該往slot[0] [0]里存，后面進(jìn)來(lái)的同樣是編號(hào)為0的槽的話(huà)就接著往slot[0] [1]里存
add(key,value) {
const h = this.h(key);
// 判斷這個(gè)槽是否是一個(gè)二維數(shù)組, 不是則創(chuàng)建二維數(shù)組
if(!this.slots[h]){
this.slots[h] = [];
}
// 將值添加到對(duì)應(yīng)的槽中
this.slots[h].push(value);
}
刪除
通過(guò)hash算法,找到所在的槽
通過(guò)過(guò)濾來(lái)刪除
delete(key){
const h = this.h(key);
this.slots[h] = this.slots[h].filter(item=>item.key!==key);
}
查找
通過(guò)hash算法找到對(duì)應(yīng)的槽
用find函數(shù)去找同一個(gè)key的值
返回對(duì)應(yīng)的值
search(key){
const h = this.h(key);
const list = this.slots[h];
const data = list.find(x=> x.key === key);
return data ? data.value : null;
}
總結(jié)
講到這里，散列表的數(shù)據(jù)結(jié)構(gòu)已經(jīng)講完了，其實(shí)我們每學(xué)一種數(shù)據(jù)結(jié)構(gòu)或算法的時(shí)候，不是去照搬實(shí)現(xiàn)的代碼，我們要學(xué)到的是思想，比如說(shuō)散列表它究竟做了什么，它是一種存儲(chǔ)方式，可以快速的通過(guò)鍵去查找到對(duì)應(yīng)的值。那么我們會(huì)思考，如果我們?cè)O(shè)計(jì)的槽少了，在同一個(gè)槽里存放了大量的數(shù)據(jù)，那么這個(gè)散列表它的搜索速度肯定是會(huì)大打折扣的，這種情況又應(yīng)該用什么方式去解決，又或者是否用其他的數(shù)據(jù)結(jié)構(gòu)的代替它。
補(bǔ)充一個(gè)小知識(shí)點(diǎn)v8引擎中的數(shù)組 arr = [1,2,3,4,5] 或 new Array(100) 我們都知道它是開(kāi)辟了一塊連續(xù)的空間去存儲(chǔ)，而arr = [] , arr[100000] = 10 這樣的操作它是使用的散列，因?yàn)檫@種操作如果連續(xù)開(kāi)辟100萬(wàn)個(gè)空間去存儲(chǔ)一個(gè)值，那么顯然是在浪費(fèi)空間。
后續(xù)后續(xù)可能會(huì)去介紹一下二叉樹(shù)，另外對(duì)于文章有什么寫(xiě)錯(cuò)或者寫(xiě)的不好的地方大家都可以提出來(lái)。我會(huì)持續(xù)的去寫(xiě)關(guān)于前端的一些技術(shù)文章，如果大家喜歡的話(huà)可以關(guān)注一下，點(diǎn)個(gè)贊哦謝謝
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/100590.html
摘要：哈希表也是種數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作。一個(gè)更好的散列函數(shù)為了避免碰撞，首先要確保散列表中用來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)組其大小是個(gè)質(zhì)數(shù)，這和計(jì)算散列值時(shí)使用的取余運(yùn)算有關(guān)。散列函數(shù)將學(xué)生里的數(shù)字相加，使用函數(shù)計(jì)算出散列值。 什么是字典結(jié)構(gòu)？ 字典是以鍵值對(duì)形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，就像電話(huà)號(hào)碼薄里的名字和電話(huà)號(hào)碼那樣的一一對(duì)應(yīng)的關(guān)系。 javascript的Object類(lèi)就是以...
摘要：我經(jīng)常在業(yè)務(wù)代碼中把數(shù)據(jù)處理成這種字典的數(shù)據(jù)結(jié)構(gòu)獲取的方法哈希表在學(xué)習(xí)了類(lèi)之后，我們會(huì)學(xué)習(xí)散列表，也就是哈希表。 《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和散列表」 集合、字典、散列表存儲(chǔ)的都是「不重復(fù)」的數(shù)據(jù)結(jié)構(gòu) 集合：我們更關(guān)注每一個(gè)元素的值，并把其作為主要元素 字典：我們用[鍵,值]的形式來(lái)存儲(chǔ)數(shù)據(jù) 散列表： 跟字典類(lèi)似，也會(huì)是用[鍵,值]的形式來(lái)存儲(chǔ)數(shù)據(jù) 但是「字...
摘要：簡(jiǎn)介哈希表又被稱(chēng)為散列表，可能是翻譯的問(wèn)題好多書(shū)上一會(huì)兒稱(chēng)散列一會(huì)兒稱(chēng)哈希，更有甚者煞有介事的對(duì)此進(jìn)行區(qū)分。實(shí)現(xiàn)哈希表我們將要實(shí)現(xiàn)這個(gè)類(lèi)分別實(shí)現(xiàn)插入查找刪除打印等方法。 1.簡(jiǎn)介 哈希表(hash table)又被稱(chēng)為散列表，可能是翻譯的問(wèn)題好多書(shū)上一會(huì)兒稱(chēng)散列一會(huì)兒稱(chēng)哈希，更有甚者煞有介事的對(duì)此進(jìn)行區(qū)分。經(jīng)過(guò)簡(jiǎn)單的搜索（wiki鏈接）發(fā)現(xiàn)這兩個(gè)詞是一回事。由此可見(jiàn)學(xué)好英語(yǔ)是多么重要。...
摘要：散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說(shuō)，沒(méi)有數(shù)組就沒(méi)有散列表。根據(jù)下圖你更能理解散列表哈希函數(shù)結(jié)合上面的理解，你應(yīng)該可以想到，其實(shí)散列表的關(guān)鍵就在于哈希函數(shù)的實(shí)現(xiàn)。 1. 什么是散列表？ 散列表（Hash Table）又叫做哈希表，是一種很常用的數(shù)據(jù)結(jié)構(gòu)。散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說(shuō)，沒(méi)有數(shù)組就沒(méi)有散列表。先來(lái)舉一個(gè)簡(jiǎn)單的例子，來(lái)認(rèn)識(shí)一下什么是散列表。 假如在學(xué)校的運(yùn)動(dòng)會(huì)上，每個(gè)運(yùn)動(dòng)...
摘要：小結(jié)實(shí)現(xiàn)了字典和哈希表感覺(jué)沒(méi)有想象中那么困難，當(dāng)然這還是開(kāi)始。 本系列所有文章：第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章：學(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ù) 字典 不是新華字典哦，這里的字典也稱(chēng)作_映射_，是一種數(shù)據(jù)結(jié)構(gòu)，跟set集合很相似的一種數(shù)據(jù)結(jié)構(gòu)，都可以用來(lái)...
閱讀 712·2021-09-29 09:34
閱讀 2565·2019-08-30 15:53
閱讀 3371·2019-08-29 17:17
閱讀 771·2019-08-29 16:08
閱讀 1132·2019-08-29 13:03
閱讀 960·2019-08-27 10:54
閱讀 694·2019-08-26 13:39
閱讀 2864·2019-08-26 13:34
