javascript hash是什麼

在javascript中，hash指的是哈希表，是一種根據關鍵字直接存取記憶體儲存位置的資料結構；透過雜湊表，資料元素的存放位置和資料元素的關鍵字之間建立起某種對應關係，建立這種對應關係的函數稱為雜湊函數。

本教學操作環境：windows7系統、javascript1.8.5版、Dell G3電腦。

javascript hash的基本概念：

#哈希表（hash table ）是一種根據關鍵字直接存取記憶體儲存位置的數據結構，透過雜湊表，資料元素的存放位置和資料元素的關鍵字之間建立起某種對應關係，建立這種對應關係的函數稱為雜湊函數。

雜湊表的建構方法：

假設要儲存的資料元素數量是n，設定一個長度為m(m > n)的連續儲存單元，分別以每個資料元素的關鍵字Ki(0

從數學的角度看，哈希函數實際上是關鍵字到內存單元的映射，因此我們希望通過哈希函數通過盡量簡單的運算使得哈希函數計算出的花溪地址盡量均勻的背影射到一系列的記憶體單元中，建構雜湊函數有三個要點：（1）運算過程要盡量簡單高效，以提高哈希表的插入和檢索效率；（2）哈希函數應該具有較好的雜湊型，以降低雜湊衝突的機率；第三，雜湊函數應具有較大的壓縮性，以節省記憶體。

常用方法：

• 直接位址法：以關鍵字的某個線性函數值為雜湊位址，可以表示為hash(K)=aK C;優點是不會產生衝突，缺點是空間複雜度可能會較高，適用於元素較少的情況。
• 除留餘數法：它是由資料元素關鍵字除以某個常數所留的餘數為雜湊位址，該方法計算簡單，適用範圍廣，是經常使用的一種雜湊函數，可以表示為：
  hash(K=K mod C;該方法的關鍵是常數的選取，一般要求是接近或等於哈希表本身的長度，研究理論表明，該常數選素數時效果最好
• 數字分析法：此方法是取資料元素關鍵字中某些取值較均勻的數字作為雜湊位址的方法，這樣可以盡量避免衝突，但是此方法只適合所有關鍵字已知的情況，對於想要設計出更通用的哈希表並不適用。
• 平方求和法：對當前字符串轉換為Unicode值，並求出這個值的平方，去平方值中間的幾位為目前數字的hash值，具體取幾位元要取決於目前雜湊表的大小。
• 分段求和法：根據目前雜湊表的位數把所要插入的數值分成若干段，把若干段相加，捨去調最高位結果就是這個值的雜湊值。

雜湊衝突的解：

在構造哈希表時，存在這樣的問題：對於兩個不同的關鍵字，透過我們的哈希函數計算哈希地址時卻得到了相同的哈希地址，我們將這種現象稱為哈希衝突。

雜湊衝突主要與兩個因素有關

（1）填充因子，填入因子是指雜湊表中已儲存入的資料元素個數與哈希位址空間的大小的比值，a=n/m ; a越小，衝突的可能性就越小，相反則衝突可能性較大；但是a越小空間利用率也就越小，a越大，空間利用率越高，為了兼顧哈希衝突和儲存空間利用率，通常將a控制在0.6-0.9之間，而.net中的HashTable則直接將a的最大值定義為0.72 （雖然微軟官方MSDN中聲明HashTable預設填裝因子為1.0，但實際上都是0.72的倍數）
（2）與所使用的哈希函數有關，如果哈希函數得當，就可以使哈希位址盡可能的均勻分佈在雜湊位址空間上，從而減少衝突的產生，但一個良好的雜湊函數的得來很大程度上取決於大量的實踐。

1）開放定址法

Hi=(H(key) di) MOD m i=1,2,…k(k 其中H(key)為雜湊函數；m為哈希表表長；di為增量序列。有3中增量序列：
①線性探測再散列：di=1,2,3,…,m-1
②二次探測再散列：di=1##2,- 1^2,22,-2^{2,…±k^2(k ③偽隨機探測再散列：di=偽隨機數序列}

我們可以看到一個現象：當表中i,i 1,i 2位置上已經填入記錄時，下一個雜湊位址為i,i 1,i 2和i 3的記錄都會填入i 3的位置，這種在處理衝突過程中發生的兩個第一個哈希地址不同的記錄爭奪同一個後繼哈希地址的現象稱為“二次聚集”，即在處理同義詞的衝突過程中又加入了非同義詞的衝突。但另一方面，用線性探測再散列處理衝突可以保證做到：只要雜湊表未填滿，總是能找到一個不發生衝突的位址Hk。而二次探測再散列只有在哈希表長m為形如4j 3（j為整數）的素數時才可能。即開放定址法會造成二次聚集的現象，對查找不利。

2)再雜湊法

Hi = RHi（key），i=1,2,…k RHi皆是不同的雜湊函數，即在同義詞產生位址衝突時計算另一個雜湊函數位址，直到不發生衝突為止。這種方法不易產生聚集，但是增加了計算時間。

缺點：增加了計算時間。

3)鏈結位址法（拉鍊法）

將所有關鍵字為同義詞的記錄儲存在同一線性鍊錶中。

優點:

①拉鍊法處理衝突簡單，且無堆積現象，即非同義詞決不會發生衝突，因此平均查找長度較短；
②由於拉鍊法中各鍊錶上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
③開放定址法為減少衝突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鍊法中可取α≥1，且結點較大時，拉鍊法中增加的指針域可忽略不計，因此節省空間；
④在用拉鍊法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪除鍊錶上對應的結點即可。而對開放位址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之後填人散列表的同義詞結點的查找路徑。這是因為在各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放位址法處理衝突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

缺點：

拉鍊法的缺點是：指標需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的衝突，從而提高平均查找速度。

4)建立一個公共溢出區

假設雜湊函數的值域為[0,m-1]，則設向量HashTable[0…m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0…v]為溢位表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管他們由雜湊函數得到的雜湊位址是什麼，一旦發生衝突，都填入溢位表。

一個簡單雜湊函數不做衝突處理的雜湊表實作

class Hash { constructor() { this.table = new Array(1024); } hash(data) { //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余 var total = 0; for (var i = 0; i < data.length; i++) { total += data.charCodeAt(i); } console.log("Hash Value: " + data + " -> " + total); return total % this.table.length; } insert(key, val) { var pos = this.hash(key); this.table[pos] = val; } get(key) { var pos = this.hash(key); return this.table[pos] } show() { for (var i = 0; i < this.table.length; i++) { if (this.table[i] != undefined) { console.log(i + ":" + this.table[i]); } } } } var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"]; var hash = new Hash(); for (var i = 0; i < someNames.length; ++i) { hash.insert(someNames[i], someNames[i]); } hash.show();

# 採用的是平方取中法建構雜湊函數，開放位址法線性探測法進行解決衝突。

class Hash { constructor() { this.table = new Array(1000); } hash(data) { var total = 0; for (var i = 0; i < data.length; i++) { total += data.charCodeAt(i); } //把字符串转化为字符用来求和之后进行平方运算 var s = total * total + "" //保留中间2位 var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1 console.log("Hash Value: " + data + " -> " + index); return index; } solveClash(index, value) { var table = this.table //进行线性开放地址法解决冲突 for (var i = 0; index + i < 1000; i++) { if (table[index + i] == null) { table[index + i] = value; break; } } } insert(key, val) { var index = this.hash(key); //把取中当做哈希表中索引 if (this.table[index] == null) { this.table[index] = val; } else { this.solveClash(index, val); } } get(key) { var pos = this.hash(key); return this.table[pos] } show() { for (var i = 0; i < this.table.length; i++) { if (this.table[i] != undefined) { console.log(i + ":" + this.table[i]); } } } } var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"]; var hash = new Hash(); for (var i = 0; i < someNames.length; ++i) { hash.insert(someNames[i], someNames[i]); } hash.show();

【推薦學習：javascript進階教學】

以上是javascript hash是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！