資訊專欄INFORMATION COLUMN
摘要：散列表散列表，也叫哈希表，是根據鍵而直接訪問在內存存儲位置的數據結構。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。
散列表
散列表（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萬個空間去存儲一個值，那么顯然是在浪費空間。
后續后續可能會去介紹一下二叉樹，另外對于文章有什么寫錯或者寫的不好的地方大家都可以提出來。我會持續的去寫關于前端的一些技術文章，如果大家喜歡的話可以關注一下，點個贊哦謝謝
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/100590.html
摘要：哈希表也是種數據結構，它可以提供快速的插入操作和查找操作。一個更好的散列函數為了避免碰撞，首先要確保散列表中用來存儲數據的數組其大小是個質數，這和計算散列值時使用的取余運算有關。散列函數將學生里的數字相加，使用函數計算出散列值。 什么是字典結構？ 字典是以鍵值對形式存儲數據的數據結構，就像電話號碼薄里的名字和電話號碼那樣的一一對應的關系。 javascript的Object類就是以...
摘要：我經常在業務代碼中把數據處理成這種字典的數據結構獲取的方法哈希表在學習了類之后，我們會學習散列表，也就是哈希表。 《Javascript數據結構和算法》筆記-「字典和散列表」 集合、字典、散列表存儲的都是「不重復」的數據結構 集合：我們更關注每一個元素的值，并把其作為主要元素 字典：我們用[鍵,值]的形式來存儲數據 散列表： 跟字典類似，也會是用[鍵,值]的形式來存儲數據 但是「字...
摘要：簡介哈希表又被稱為散列表，可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希，更有甚者煞有介事的對此進行區分。實現哈希表我們將要實現這個類分別實現插入查找刪除打印等方法。 1.簡介 哈希表(hash table)又被稱為散列表，可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希，更有甚者煞有介事的對此進行區分。經過簡單的搜索（wiki鏈接）發現這兩個詞是一回事。由此可見學好英語是多么重要。...
摘要：散列表其實是基于數組實現的，可以說，沒有數組就沒有散列表。根據下圖你更能理解散列表哈希函數結合上面的理解，你應該可以想到，其實散列表的關鍵就在于哈希函數的實現。 1. 什么是散列表？ 散列表（Hash Table）又叫做哈希表，是一種很常用的數據結構。散列表其實是基于數組實現的，可以說，沒有數組就沒有散列表。先來舉一個簡單的例子，來認識一下什么是散列表。 假如在學校的運動會上，每個運動...
摘要：小結實現了字典和哈希表感覺沒有想象中那么困難，當然這還是開始。 本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算法之二叉搜索樹 字典 不是新華字典哦，這里的字典也稱作_映射_，是一種數據結構，跟set集合很相似的一種數據結構，都可以用來...
閱讀 710·2021-09-29 09:34
閱讀 2561·2019-08-30 15:53
閱讀 3368·2019-08-29 17:17
閱讀 766·2019-08-29 16:08
閱讀 1129·2019-08-29 13:03
閱讀 955·2019-08-27 10:54
閱讀 693·2019-08-26 13:39
閱讀 2863·2019-08-26 13:34
