本篇文章給大家帶來的內容是關於JavaScript中散列表(哈希表)的詳細介紹(代碼示例),有一定的參考價值,有需要的朋友可以參考一下,希望對你有所幫助。
散列表
散列表(Hash table,也叫哈希表),是根據鍵(Key)而直接訪問在內存存儲位置的數據結構。也就是說,它通過計算一個關於鍵值的函數,將所需查詢的數據映射到表中一個位置來訪問記錄,這加快了查找速度。這個映射函數稱做散列函數,存放記錄的數組稱做散列表。
我們從上圖開始分析
- 有一個集合U,裡面分別是1000,10,152,9733,1555,997,1168
- 右側是一個10個插槽的列表(散列表),我們需要把集合U中的整數存放到這個列表中
- 怎麼存放,分別存在哪個槽裡?這個問題就是需要通過一個散列函數來解決了。我的存放方式是取10的餘數,我們對應這圖來看
- 1000%10=0,10%10=0 那麼1000和10這兩個整數就會被存儲到編號為0的這個槽中
- 152%10=2那麼就存放到2的槽中
- 9733%10=3 存放在編號為3的槽中
通過上面簡單的例子,應該會有一下幾點一個大致的理解
- 集合U,就是可能會出現在散列表中的鍵
- 散列函數,就是你自己設計的一種如何將集合U中的鍵值通過某種計算存放到散列表中,如例子中的取餘數
- 散列表,存放著通過計算後的鍵
那麼我們在接著看一般我們會怎麼去取值呢?
比如我們存儲一個key為1000,value為'張三' ---> {key:1000,value:'張三'}
從我們上述的解釋,它是不是應該存放在1000%10的這個插槽裡。
當我們通過key想要找到value張三,是不是到key%10這個插槽裡找就可以了呢?到了這裡你可以停下來思考一下。
散列的一些術語(可以簡單的看一下)
- 散列表中所有可能出現的鍵稱作全集U
- 用M表示槽的數量
- 給定一個鍵,由散列函數計算它應該出現在哪個槽中,上面例子的散列函數h=k%M,散列函數h就是鍵k到槽的一個映射。
- 1000和10都被存到了編號0的這個槽中,這種情況稱之為碰撞。
看到這裡不知道你是否大致理解了散列函數是什麼了沒。通過例子,再通過你的思考,你可以回頭在讀一遍文章頭部關於散列表的定義。如果你能讀懂了,那麼我估計你應該是懂了。
常用的散列函數
處理整數 h=>k%M (也就是我們上面所舉的例子)
處理字符串:
function h_str(str,M){
return [...str].reduce((hash,c)=>{
hash = (31*hash + c.charCodeAt(0)) % M
},0)
}
hash算法不是這裡的重點,我也沒有很深入的去研究,這裡主要還是去理解散列表是個怎樣的數據結構,它有哪些優點,它具體做了怎樣一件事。
而hash函數它只是通過某種算法把key映射到列表中。
構建散列表
通過上面的解釋,我們這裡做一個簡單的散列表
散列表的組成
- M個槽
- 有個hash函數
- 有一個add方法去把鍵值添加到散列表中
- 有一個delete方法去做刪除
- 有一個search方法,根據key去找到對應的值
初始化
- 初始化散列表有多少個槽
- 用一個數組來創建M個槽
class HashTable {
constructor(num=1000){
this.M = num;
this.slots = new Array(num);
}
}
散列函數
處理字符串的散列函數,這裡使用字符串是因為,數值也可以傳換成字符串比較通用一些
先將傳遞過來的key值轉為字符串,為了能夠嚴謹一些
將字符串轉換為數組, 例如'abc' => [...'abc'] => ['a','b','c']
分別對每個字符的charCodeAt進行計算,取M餘數是為了剛好對應插槽的數量,你總共就10個槽,你的數值%10 肯定會落到 0-9的槽裡
h(str){
str = str + '';
return [...str].reduce((hash,c)=>{
hash = (331 * hash + c.charCodeAt()) % this.M;
return hash;
},0)
}
添加
調用hash函數得到對應的存儲地址(就是我們之間類比的槽)
因為一個槽中可能會存多個值,所以需要用一個二維數組去表示,比如我們計算得來的槽的編號是0,也就是slot[0],那麼我們應該往slot[0] [0]裡存,後面進來的同樣是編號為0的槽的話就接著往slot[0] [1]裡存
add(key,value) {
const h = this.h(key);
// 判斷這個槽是否是一個二維數組, 不是則創建二維數組
if(!this.slots[h]){
this.slots[h] = [];
}
// 將值添加到對應的槽中
this.slots[h].push(value);
}
刪除
通過hash算法,找到所在的槽
通過過濾來刪除
delete(key){
const h = this.h(key);
this.slots[h] = this.slots[h].filter(item=>item.key!==key);
}
查找
通過hash算法找到對應的槽
用find函數去找同一個key的值
返回對應的值
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;
}
總結
講到這裡,散列表的數據結構已經講完了,其實我們每學一種數據結構或算法的時候,不是去照搬實現的代碼,我們要學到的是思想,比如說散列表它究竟做了什麼,它是一種存儲方式,可以快速的通過鍵去查找到對應的值。那麼我們會思考,如果我們設計的槽少了,在同一個槽裡存放了大量的數據,那麼這個散列表它的搜索速度肯定是會大打折扣的,這種情況又應該用什麼方式去解決,又或者是否用其他的數據結構的代替它。
補充一個小知識點
v8引擎中的數組 arr = [1,2,3,4,5] 或 new Array(100) 我們都知道它是開闢了一塊連續的空間去存儲,而arr = [] , arr[100000] = 10 這樣的操作它是使用的散列,因為這種操作如果連續開闢100萬個空間去存儲一個值,那麼顯然是在浪費空間。
以上就是JavaScript中散列表(哈希表)的詳細介紹(代碼示例)的詳細內容,更多請關注其它相關文章!
更多技巧請《轉發 + 關注》哦!
閱讀更多 科技i關注 的文章
關鍵字: 數據結構 列表 JavaScript