這篇文章主要講解了“javascript中hash是什么”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“javascript中hash是什么”吧！
在準(zhǔn)格爾等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需規(guī)劃網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都營銷網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè),準(zhǔn)格爾網(wǎng)站建設(shè)費(fèi)用合理。
在javascript中，hash指的是哈希表，是一種根據(jù)關(guān)鍵字直接訪問內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)；通過哈希表，數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關(guān)鍵字之間建立起某種對應(yīng)關(guān)系，建立這種對應(yīng)關(guān)系的函數(shù)稱為哈希函數(shù)。
本教程操作環(huán)境：windows7系統(tǒng)、javascript1.8.5版、Dell G3電腦。
javascript hash的基本概念：
哈希表（hash table ）是一種根據(jù)關(guān)鍵字直接訪問內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)，通過哈希表，數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關(guān)鍵字之間建立起某種對應(yīng)關(guān)系，建立這種對應(yīng)關(guān)系的函數(shù)稱為哈希函數(shù)。
哈希表的構(gòu)造方法：
假設(shè)要存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)是n，設(shè)置一個(gè)長度為m(m > n)的連續(xù)存儲(chǔ)單元，分別以每個(gè)數(shù)據(jù)元素的關(guān)鍵字Ki(0<=i<=n-1)為自變量，通過哈希函數(shù)hash(Ki)，把Ki映射為內(nèi)存單元的某個(gè)地址hash(Ki),并將數(shù)據(jù)元素存儲(chǔ)在內(nèi)存單元中。
從數(shù)學(xué)的角度看，哈希函數(shù)實(shí)際上是關(guān)鍵字到內(nèi)存單元的映射，因此我們希望通過哈希函數(shù)通過盡量簡單的運(yùn)算使得哈希函數(shù)計(jì)算出的花溪地址盡量均勻的背影射到一系列的內(nèi)存單元中，構(gòu)造哈希函數(shù)有三個(gè)要點(diǎn)：（1）運(yùn)算過程要盡量簡單高效，以提高哈希表的插入和檢索效率；（2）哈希函數(shù)應(yīng)該具有較好的散列型，以降低哈希沖突的概率；第三，哈希函數(shù)應(yīng)具有較大的壓縮性，以節(jié)省內(nèi)存。
常用方法：
直接地址法：以關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址，可以表示為hash(K)=aK+C;優(yōu)點(diǎn)是不會(huì)產(chǎn)生沖突，缺點(diǎn)是空間復(fù)雜度可能會(huì)較高，適用于元素較少的情況。
除留余數(shù)法：它是由數(shù)據(jù)元素關(guān)鍵字除以某個(gè)常數(shù)所留的余數(shù)為哈希地址，該方法計(jì)算簡單，適用范圍廣，是經(jīng)常使用的一種哈希函數(shù)，可以表示為：
hash(K=K mod C;該方法的關(guān)鍵是常數(shù)的選取，一般要求是接近或等于哈希表本身的長度，研究理論表明，該常數(shù)選素?cái)?shù)時(shí)效果最好
數(shù)字分析法：該方法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字來作為哈希地址的方法，這樣可以盡量避免沖突，但是該方法只適合于所有關(guān)鍵字已知的情況，對于想要設(shè)計(jì)出更加通用的哈希表并不適用。
平方求和法：對當(dāng)前字串轉(zhuǎn)化為Unicode值，并求出這個(gè)值的平方，去平方值中間的幾位為當(dāng)前數(shù)字的hash值，具體取幾位要取決于當(dāng)前哈希表的大小。
分段求和法：根據(jù)當(dāng)前哈希表的位數(shù)把所要插入的數(shù)值分成若干段，把若干段進(jìn)行相加，舍去調(diào)最高位結(jié)果就是這個(gè)值的哈希值。
哈希沖突的解決方案：
在構(gòu)造哈希表時(shí)，存在這樣的問題：對于兩個(gè)不同的關(guān)鍵字，通過我們的哈希函數(shù)計(jì)算哈希地址時(shí)卻得到了相同的哈希地址，我們將這種現(xiàn)象稱為哈希沖突。
哈希沖突主要與兩個(gè)因素有關(guān)
（1）填裝因子，填裝因子是指哈希表中已存入的數(shù)據(jù)元素個(gè)數(shù)與哈希地址空間的大小的比值，a=n/m ; a越小，沖突的可能性就越小，相反則沖突可能性較大；但是a越小空間利用率也就越小，a越大，空間利用率越高，為了兼顧哈希沖突和存儲(chǔ)空間利用率，通常將a控制在0.6-0.9之間，而.net中的HashTable則直接將a的最大值定義為0.72 （雖然微軟官方MSDN中聲明HashTable默認(rèn)填裝因子為1.0，但實(shí)際上都是0.72的倍數(shù)）
（2）與所用的哈希函數(shù)有關(guān)，如果哈希函數(shù)得當(dāng)，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少?zèng)_突的產(chǎn)生，但一個(gè)良好的哈希函數(shù)的得來很大程度上取決于大量的實(shí)踐。
1）開放定址法
Hi=(H(key) + di) MOD m i=1,2,…k(k<=m-1)
其中H(key)為哈希函數(shù)；m為哈希表表長；di為增量序列。有3中增量序列：
①線性探測再散列：di=1,2,3,…,m-1
②二次探測再散列：di=12,-12,22,-22,…±k^2(k<=m/2)
③偽隨機(jī)探測再散列：di=偽隨機(jī)數(shù)序列
缺點(diǎn)：
我們可以看到一個(gè)現(xiàn)象：當(dāng)表中i,i+1,i+2位置上已經(jīng)填有記錄時(shí)，下一個(gè)哈希地址為i,i+1,i+2和i+3的記錄都將填入i+3的位置，這種在處理沖突過程中發(fā)生的兩個(gè)第一個(gè)哈希地址不同的記錄爭奪同一個(gè)后繼哈希地址的現(xiàn)象稱為“二次聚集”，即在處理同義詞的沖突過程中又添加了非同義詞的沖突。但另一方面，用線性探測再散列處理沖突可以保證做到：只要哈希表未填滿，總能找到一個(gè)不發(fā)生沖突的地址Hk。而二次探測再散列只有在哈希表長m為形如4j+3（j為整數(shù)）的素?cái)?shù)時(shí)才可能。即開放定址法會(huì)造成二次聚集的現(xiàn)象，對查找不利。
2)再哈希法
Hi = RHi（key），i=1,2,…k RHi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到不發(fā)生沖突為止。這種方法不易產(chǎn)生聚集，但是增加了計(jì)算時(shí)間。
缺點(diǎn)：增加了計(jì)算時(shí)間。
3)鏈地址法（拉鏈法）
將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。
優(yōu)點(diǎn):
①拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；
④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對開放地址法構(gòu)造的散列表，刪除結(jié)點(diǎn)不能簡單地將被刪結(jié) 點(diǎn)的空間置為空，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。
缺點(diǎn)：
拉鏈法的缺點(diǎn)是：指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
4)建立一個(gè)公共溢出區(qū)
假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1]，則設(shè)向量HashTable[0…m-1]為基本表，每個(gè)分量存放一個(gè)記錄，另設(shè)立向量OverTable[0…v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。
一個(gè)簡單哈希函數(shù)不做沖突處理的哈希表實(shí)現(xiàn)
重慶分公司
重慶分公司
class Hash {
constructor() {
this.table = new Array(1024);
}
hash(data) {
//就將字符串中的每個(gè)字符的ASCLL碼值相加起來，再對數(shù)組的長度取余
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();
采用的是平方取中法構(gòu)建哈希函數(shù)，開放地址法線性探測法進(jìn)行解決沖突。
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);
}
//把字符串轉(zhuǎn)化為字符用來求和之后進(jìn)行平方運(yùn)算
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
//進(jìn)行線性開放地址法解決沖突
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);
//把取中當(dāng)做哈希表中索引
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中hash是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對javascript中hash是什么這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
