成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

javascript 哈希表

Yi_Zhi_Yu / 1311人閱讀

摘要:分段求和法根據(jù)當(dāng)前哈希表的位數(shù)把所要插入的數(shù)值分成若干段,把若干段進(jìn)行相加,舍去調(diào)最高位結(jié)果就是這個(gè)值的哈希值。而二次探測(cè)再散列只有在哈希表長(zhǎng)為形如為整數(shù)的素?cái)?shù)時(shí)才可能。數(shù)據(jù)為數(shù)據(jù)的哈希值與更大素?cái)?shù)求模后存儲(chǔ)到線性表中沖突的個(gè)數(shù)。

其實(shí)javascript的對(duì)象就是一個(gè)哈希表,為了學(xué)習(xí)真正的數(shù)據(jù)結(jié)構(gòu),我們還是有必要自己重新實(shí)現(xiàn)一下。

基本概念

哈希表(hash table )是一種根據(jù)關(guān)鍵字直接訪問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu),通過(guò)哈希表,數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關(guān)鍵字之間建立起某種對(duì)應(yīng)關(guān)系,建立這種對(duì)應(yīng)關(guān)系的函數(shù)稱為哈希函數(shù)

哈希表的構(gòu)造方法

假設(shè)要存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)是n,設(shè)置一個(gè)長(zhǎng)度為m(m > n)的連續(xù)存儲(chǔ)單元,分別以每個(gè)數(shù)據(jù)元素的關(guān)鍵字Ki(0<=i<=n-1)為自變量,通過(guò)哈希函數(shù)hash(Ki),把Ki映射為內(nèi)存單元的某個(gè)地址hash(Ki),并將數(shù)據(jù)元素存儲(chǔ)在內(nèi)存單元中

從數(shù)學(xué)的角度看,哈希函數(shù)實(shí)際上是關(guān)鍵字到內(nèi)存單元的映射,因此我們希望通過(guò)哈希函數(shù)通過(guò)盡量簡(jiǎn)單的運(yùn)算使得哈希函數(shù)計(jì)算出的花溪地址盡量均勻的背影射到一系列的內(nèi)存單元中,構(gòu)造哈希函數(shù)有三個(gè)要點(diǎn):(1)運(yùn)算過(guò)程要盡量簡(jiǎ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ì)算簡(jiǎn)單,適用范圍廣,是經(jīng)常使用的一種哈希函數(shù),可以表示為:

hash(K=K mod C;該方法的關(guān)鍵是常數(shù)的選取,一般要求是接近或等于哈希表本身的長(zhǎng)度,研究理論表明,該常數(shù)選素?cái)?shù)時(shí)效果最好

數(shù)字分析法:該方法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字來(lái)作為哈希地址的方法,這樣可以盡量避免沖突,但是該方法只適合于所有關(guān)鍵字已知的情況,對(duì)于想要設(shè)計(jì)出更加通用的哈希表并不適用

平方求和法:對(duì)當(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í),存在這樣的問(wèn)題:對(duì)于兩個(gè)不同的關(guān)鍵字,通過(guò)我們的哈希函數(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ù)的得來(lái)很大程度上取決于大量的實(shí)踐,不過(guò)幸好前人已經(jīng)總結(jié)實(shí)踐了很多高效的哈希函數(shù),可以參考大神Lucifer文章:數(shù)據(jù)結(jié)構(gòu):HahTable: http://www.cnblogs.com/lucife...

1)開(kāi)放定址法

Hi=(H(key) + di) MOD m i=1,2,...k(k<=m-1)
其中H(key)為哈希函數(shù);m為哈希表表長(zhǎng);di為增量序列。有3中增量序列:
1)線性探測(cè)再散列:di=1,2,3,...,m-1
2)二次探測(cè)再散列:di=1^2,-1^2,2^2,-2^2,....+-k^2(k<=m/2)
3)偽隨機(jī)探測(cè)再散列: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的位置,這種在處理沖突過(guò)程中發(fā)生的兩個(gè)第一個(gè)哈希地址不同的記錄爭(zhēng)奪同一個(gè)后繼哈希地址的現(xiàn)象稱為“二次聚集”,即在處理同義詞的沖突過(guò)程中又添加了非同義詞的沖突。但另一方面,用線性探測(cè)再散列處理沖突可以保證做到:只要哈希表未填滿,總能找到一個(gè)不發(fā)生沖突的地址Hk。而二次探測(cè)再散列只有在哈希表長(zhǎng)m為形如4j+3(j為整數(shù))的素?cái)?shù)時(shí)才可能。即開(kāi)放定址法會(huì)造成二次聚集的現(xiàn)象,對(duì)查找不利。

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):

①拉鏈法處理沖突簡(jiǎn)單,且無(wú)堆積現(xiàn)象,即非同義詞決不會(huì)發(fā)生沖突,因此平均查找長(zhǎng)度較短;
②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的,故它更適合于造表前無(wú)法確定表長(zhǎng)的情況;
③開(kā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)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對(duì)開(kāi)放地址法構(gòu)造的散列表,刪除結(jié)點(diǎn)不能簡(jiǎn)單地將被刪結(jié) 點(diǎn)的空間置為空,否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開(kāi)放地址法中,空地址單元(即開(kāi)放地址)都是查找失敗的條件。因此在 用開(kāi)放地址法處理沖突的散列表上執(zhí)行刪除操作,只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記,而不能真正刪除結(jié)點(diǎn)

缺點(diǎn):
拉鏈法的缺點(diǎn)是:指針需要額外的空間,故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí),開(kāi)放定址法較為節(jié)省空間,而若將節(jié)省的指針空間用來(lái)擴(kuò)大散列表的規(guī)模,可使裝填因子變小,這又減少了開(kāi)放定址法中的沖突,從而提高平均查找速度

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è)簡(jiǎn)單哈希函數(shù)不做沖突處理的哈希表實(shí)現(xiàn)

// by 司徒正美
class Hash{
    constructor(){
        this.table = new Array(1024);
    }
    hash(data) {
    //就將字符串中的每個(gè)字符的ASCLL碼值相加起來(lái),再對(duì)數(shù)組的長(zhǎng)度取余
        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ù),開(kāi)放地址法線性探測(cè)法進(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)化為字符用來(lái)求和之后進(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)行線性開(kāi)放地址法解決沖突
        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(); 

幾種常見(jiàn)的hash函數(shù) DJBHash
unsigned int DJBHash(char *str)    
{    
    unsigned int hash = 5381;    
     
    while (*str){    
        hash = ((hash << 5) + hash) + (*str++); /* times 33 */    
    }    
    hash &= ~(1 << 31); /* strip the highest bit */    
    return hash;    
}

javascript版

function DJBHash(str)    {    
    var hash = 5381;   
    var len = str.length , i = 0
     
    while (len--){    
        hash = (hash << 5) + hash + str.charCodeAt(i++); /* times 33 */    
    }    
    hash &= ~(1 << 31); /* strip the highest bit */    
    return hash;    
}
JS

Justin Sobel寫(xiě)的一個(gè)位操作的哈希函數(shù)。
原版

public long JSHash(String str)  
   {  
      long hash = 1315423911;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));  
      }  
      return hash;  
   }  

javascript版

function JSHash(str)  {  
      var hash = 1315423911;  
      for(var i = 0; i < str.length; i++)  {  
         hash ^= ((hash << 5) + str.charCodeAt(i) + (hash >> 2));  
      }  
      return hash;  
}  
PJW

該散列算法是基于貝爾實(shí)驗(yàn)室的彼得J溫伯格的的研究。在Compilers一書(shū)中(原則,技術(shù)和工具),建議采用這個(gè)算法的散列函數(shù)的哈希方法。

public long PJWHash(String str)  
   {  
      long BitsInUnsignedInt = (long)(4 * 8);  
      long ThreeQuarters     = (long)((BitsInUnsignedInt  * 3) / 4);  
      long OneEighth         = (long)(BitsInUnsignedInt / 8);  
      long HighBits          = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  
      long hash              = 0;  
      long test              = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash << OneEighth) + str.charAt(i);  
         if((test = hash & HighBits)  != 0)  
         {  
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  
         }  
      }  
      return hash;  
   }  

javascript版

function PJWHash( str)  {  
      var BitsInUnsignedInt = 4 * 8;  
      var ThreeQuarters     =  (BitsInUnsignedInt  * 3) / 4;  
      var OneEighth         = (BitsInUnsignedInt / 8);  
      var HighBits          = (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  
      var hash              = 0;  
      var test              = 0;  
      for(var i = 0; i < str.length; i++)  {  
         hash = (hash << OneEighth) + str.charCodeAt(i);  
         if((test = hash & HighBits)  != 0)  
         {  
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  
         }  
      }  
      return hash;  
} 

如果將上面的哈表的hash函數(shù)改成這個(gè),打印如下:

性能會(huì)大幅下隆,因?yàn)檫@讓我們的table數(shù)組表得非常龐大。

ELF

和PJW很相似,在Unix系統(tǒng)中使用的較多。

public long ELFHash(String str)  
   {  
      long hash = 0;  
      long x    = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash << 4) + str.charAt(i);  
         if((x = hash & 0xF0000000L) != 0)  
         {  
            hash ^= (x >> 24);  
         }  
         hash &= ~x;  
      }  
      return hash;  
   }  
BKDR

這個(gè)算法來(lái)自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。這是一個(gè)很簡(jiǎn)單的哈希算法,使用了一系列奇怪的數(shù)字,形式如31,3131,31...31,看上去和DJB算法很相似。

public long BKDRHash(String str)  
   {  
      long seed = 131; // 31 131 1313 13131 131313 etc..  
      long hash = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash * seed) + str.charAt(i);  
      }  
      return hash;  
   }  
SDBM

這個(gè)算法在開(kāi)源的SDBM中使用,似乎對(duì)很多不同類型的數(shù)據(jù)都能得到不錯(cuò)的分布。

public long SDBMHash(String str)  
   {  
      long hash = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;  
      }  
      return hash;  
   }  
DJB

這個(gè)算法是Daniel J.Bernstein 教授發(fā)明的,是目前公布的最有效的哈希函數(shù)。

public long DJBHash(String str)  
   {  
      long hash = 5381;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = ((hash << 5) + hash) + str.charAt(i);  
      }  
      return hash;  
   }  
DEK

由偉大的Knuth在《編程的藝術(shù) 第三卷》的第六章排序和搜索中給出。

public long DEKHash(String str)  
   {  
      long hash = str.length();  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);  
      }  
      return hash;  
   }  
AP

由Arash Partow貢獻(xiàn)的一個(gè)哈希函數(shù),繼承了上面以旋轉(zhuǎn)以為和加操作

public long APHash(String str)  
{  
      long hash = 0xAAAAAAAA;  
      for(int i = 0; i < str.length(); i++)  
      {  
         if ((i & 1) == 0)  
         {  
            hash ^= ((hash << 7) ^ str.charAt(i) * (hash >> 3));  
         }  
         else  
         {  
            hash ^= (~((hash << 11) + str.charAt(i) ^ (hash >> 5)));  
         }  
      }  
      return hash;  
   }   


其中數(shù)據(jù)1為100000個(gè)字母和數(shù)字組成的隨機(jī)串哈希沖突個(gè)數(shù)。數(shù)據(jù)2為100000個(gè)有意義的英文句子哈希沖突個(gè)數(shù)。數(shù)據(jù)3為數(shù)據(jù)1的哈希值與 1000003(大素?cái)?shù))求模后存儲(chǔ)到線性表中沖突的個(gè)數(shù)。數(shù)據(jù)4為數(shù)據(jù)1的哈希值與10000019(更大素?cái)?shù))求模后存儲(chǔ)到線性表中沖突的個(gè)數(shù)。

經(jīng)過(guò)比較,得出以上平均得分。平均數(shù)為平方平均數(shù)。可以發(fā)現(xiàn),BKDRHash無(wú)論是在實(shí)際效果還是編碼實(shí)現(xiàn)中,效果都是最突出的。APHash也是較為優(yōu)秀的算法。DJBHash,JSHash,RSHash與SDBMHash各有千秋。PJWHash與ELFHash效果最差,但得分相似,其算法本質(zhì)是相似的。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/107225.html

相關(guān)文章

  • Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和散列

    摘要:我經(jīng)常在業(yè)務(wù)代碼中把數(shù)據(jù)處理成這種字典的數(shù)據(jù)結(jié)構(gòu)獲取的方法哈希表在學(xué)習(xí)了類之后,我們會(huì)學(xué)習(xí)散列表,也就是哈希表。 《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和散列表」 集合、字典、散列表存儲(chǔ)的都是「不重復(fù)」的數(shù)據(jù)結(jié)構(gòu) 集合:我們更關(guān)注每一個(gè)元素的值,并把其作為主要元素 字典:我們用[鍵,值]的形式來(lái)存儲(chǔ)數(shù)據(jù) 散列表: 跟字典類似,也會(huì)是用[鍵,值]的形式來(lái)存儲(chǔ)數(shù)據(jù) 但是「字...

    wenyiweb 評(píng)論0 收藏0
  • JavaScript判斷單鏈中是否存在環(huán)

    摘要:如下圖單鏈表中存在環(huán)怎么判斷單鏈表中存在環(huán)呢先創(chuàng)造一下帶環(huán)的單鏈表代碼如下創(chuàng)建帶環(huán)單鏈表結(jié)果可見(jiàn)判斷單鏈表是否帶環(huán)以下有三種方法第一種方法創(chuàng)建哈希表不過(guò)會(huì)占用較大的空間不是最佳方法時(shí)間復(fù)雜度遍歷鏈表將鏈表各節(jié)點(diǎn)添加至哈希表中添加前判斷此節(jié)點(diǎn) 如下圖, 單鏈表中存在環(huán): showImg(https://segmentfault.com/img/bVbpxcI?w=635&h=173); ...

    binta 評(píng)論0 收藏0
  • 「構(gòu)建安全的 PHP 應(yīng)用」讀書(shū)筆記

    摘要:書(shū)名構(gòu)建安全的應(yīng)用作者美譯者張慶龍以下記錄這本安全小書(shū)的大致內(nèi)容,對(duì)書(shū)中的知識(shí)點(diǎn)進(jìn)行備忘??梢员WC內(nèi)容的安全性,使得只有最終傳遞到的具有有效證書(shū)的接收者才能得到這一內(nèi)容。缺省安全及跨站攻擊缺省安全我們應(yīng)該為驗(yàn) 書(shū)名:構(gòu)建安全的 PHP 應(yīng)用 作者:(美) Ben Edmunds 譯者:張慶龍 以下記錄這本 PHP Web 安全小書(shū)的大致內(nèi)容,對(duì)書(shū)中的知識(shí)點(diǎn)進(jìn)行備忘。 不要相信任何用...

    kviccn 評(píng)論0 收藏0
  • LeetCode 之 JavaScript 解答第141題 —— 環(huán)形鏈 I(Linked Lis

    摘要:小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表,沒(méi)遍歷一個(gè)節(jié)點(diǎn)就要在哈希表中判斷是否存在該結(jié)點(diǎn),如果存在,則為環(huán)否則,將該結(jié)點(diǎn)插入到哈希表中繼續(xù)遍歷。 Time:2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿 題目:Linked List Cycle I Given a linked list, determine ...

    wangjuntytl 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<