數(shù)據(jù)結(jié)構(gòu)——散列

散列也叫作散列表，是一種非線性的數(shù)據(jù)結(jié)構(gòu)失乾，可以用來(lái)快速的查找和插入數(shù)據(jù)常熙。在 JavaScript 中，通常使用數(shù)組來(lái)實(shí)現(xiàn)散列碱茁。
散列的核心是一個(gè)計(jì)算特征值的方法裸卫，該方法將原始數(shù)據(jù)進(jìn)行轉(zhuǎn)換，返回一個(gè)索引早芭，隨后將值保存在數(shù)組對(duì)應(yīng)的索引中彼城。此外诅蝶，該方法還可以用來(lái)進(jìn)行高效的查找退个。
由于不同的特征值計(jì)算出的索引不盡相同，因此散列在保存數(shù)據(jù)時(shí)不是按順序保存的调炬，其是基于列表這樣一個(gè)線性結(jié)構(gòu)上的“非線性”結(jié)構(gòu)语盈，因此被稱為散列。
通常缰泡，我們會(huì)將數(shù)組的長(zhǎng)度設(shè)置為一個(gè)質(zhì)數(shù)刀荒，因?yàn)橘|(zhì)數(shù)的公約數(shù)最少，可以有效的防止碰撞棘钞。

散列的代碼實(shí)現(xiàn)

下面是 IHashTable 的接口定義：

interface IHashTable<T>{
    // 獲取索引值
    getIndex(flag:string):number;
    // 兩種存放方式：放入值缠借，放入一個(gè)值和簡(jiǎn)稱值
    put(flag:string,ele:T):void;
    // 獲取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 獲取散列中的元素
    toString():T[];    
}

上面的 IHashTable 中定義了一個(gè) put 方法，該方法用來(lái)向散列中添加元素宜猜。其第一個(gè)參數(shù)是要添加元素的一個(gè)別名泼返，第二個(gè)參數(shù)是元素本身。如：

hashTable.put("MIKE","mike@mike.com")
hashTable.put("JACK","jack@jack.com")

下面是 HashTable 的代碼實(shí)現(xiàn)：

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:T[] = [];
    // 散列表的長(zhǎng)度
    private dataStoreLen:number = 0;
    // 鹽值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 創(chuàng)建散列對(duì)象時(shí)傳入散列表的長(zhǎng)度和鹽值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置為計(jì)算出的 hash 值對(duì)數(shù)組的長(zhǎng)度取余
        return pos;
    }
    put(flag:string,ele:T):void{
        const pos:number = this.getIndex(flag);
        this.dataStore[pos] = ele;
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        return this.dataStore[pos];
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const res = this.dataStore[pos];        
        this.dataStore[pos] = undefined;
        return res;
    }
    toString():T[]{
        const tmp:T[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

簡(jiǎn)單測(cè)試一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
// 獲取元素
console.log(h.get("PENNY"))
console.log(h.toString())
// 移除元素
h.remove("JERRY")
console.log(h.toString())

運(yùn)行結(jié)果：

penny@penny.com
[ 'penny@penny.com',
  'jerry@jerry.com',
  'jack@jack.com',
  'mike@mike.com' ]
[ 'penny@penny.com', 'jack@jack.com', 'mike@mike.com' ]

碰撞問題

散列的碰撞也叫作散列的沖突姨拥，是指不同的別名計(jì)算出了相同的索引衣吠，上面代碼中實(shí)現(xiàn)的 getIndex() 方法琴锭，使用字符串的 charCodeAt() 方法獲取所有字符的 ASCII 碼读虏，并將這些 ASCII 碼值相加，得到一個(gè)數(shù)值徽缚，然后使用這個(gè)數(shù)值對(duì)散列表的長(zhǎng)度取余，就得到了元素在散列表中的位置革屠。
但只進(jìn)行上述簡(jiǎn)單的計(jì)算凿试，是非常容易產(chǎn)生沖突的，譬如下面的測(cè)試代碼：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
h.put("ACKJ","ackj@ackj.com")
console.log(h.toString())

運(yùn)行結(jié)果：

[ 'penny@penny.com',
  'jerry@jerry.com',
  'ackj@ackj.com',
  'mike@mike.com' ]

從上面的運(yùn)行結(jié)果中可見屠阻，最先插入的 jack@jack.com 被后插入的 ackj@ackj.com 給覆蓋了红省，這是因?yàn)樵谑褂?getIndex() 方法對(duì) JACK 和 ACKJ 計(jì)算索引值時(shí)，得到了相同的結(jié)果国觉，導(dǎo)致后面插入的元素覆蓋了前面的元素吧恃。
要解決這個(gè)問題，首先可以優(yōu)化 getIndex() 方法：

...
getIndex(flag:string):number{
    // 減少散列碰撞麻诀，加點(diǎn)鹽
    let 
        hash:number = -1,
        pos:number = -1;

    if(flag.length){
        hash = 0;
        for(const c of flag){
            hash += (this.hashSalt * hash + c.charCodeAt(0));
        }
        pos = hash % this.dataStoreLen;
    }
    // 存放位置為計(jì)算出的 hash 值對(duì)數(shù)組的長(zhǎng)度取余
    return pos;
}
...

再次執(zhí)行上面的測(cè)試代碼痕寓，運(yùn)行結(jié)果如下：

[ 'penny@penny.com',
  'mike@mike.com',
  'jerry@jerry.com',
  'jack@jack.com',
  'ackj@ackj.com' ]

通過對(duì) getIndex() 做一些修正，解決了 JACK 和 ACKJ 的沖突蝇闭。
下面再推薦一個(gè)更好的散列函數(shù)：djb2 函數(shù)呻率。

...
getIndex(flag:string):number{
    let hash:number = 5381;
    for (const c of flag) {
        hash = hash * 33 + c.charCodeAt(0);
    }
    return hash % 1013;
}
...

使用這個(gè)函數(shù)時(shí)，要求散列表的長(zhǎng)度大于 1013呻引，因此還需要對(duì)類的代碼進(jìn)行一些改進(jìn)礼仗，這里就不再詳述了。

解決碰撞的其他方案

上面對(duì)獲取索引值的 getIndex() 方法做了一些修改逻悠，以達(dá)到解決沖突的目的元践。除此之外，解決散列沖突還有兩個(gè)常用的方案：分離鏈接法（開鏈法）和線性探測(cè)法童谒。將這兩個(gè)方案和上面 getIndex() 方法進(jìn)行結(jié)合单旁，解決碰撞會(huì)更加有效。下面依次介紹這兩個(gè)方案饥伊。

分離鏈接法

分離鏈接法也叫開鏈法象浑，是解決散列碰撞的一種常用方法。在前面實(shí)現(xiàn)的 HashTable 類中琅豆，散列表在每個(gè)索引處存放的是一個(gè)元素愉豺，應(yīng)用開鏈法時(shí)，散列表在買個(gè)索引處存放的不再是一個(gè)具體的元素茫因，而是一個(gè)列表蚪拦，碰撞的元素通通存放在這個(gè)列表中。以前面 JACK 和 ACKJ 的碰撞為例，應(yīng)用分離鏈接法時(shí)外盯，它們?cè)谏⒘斜碇械氖沁@樣存放的：

[
  {key:"JACK",value:"jack@jack.com"},
  {key:"ACKJ",value:"ackj@ackj.com"}
]

在查找或移除元素時(shí)摘盆，會(huì)遍歷這個(gè)列表，根據(jù)某個(gè) KEY 值饱苟，找到相應(yīng)的元素孩擂。
對(duì)于列表，如果想綜合應(yīng)用前面的知識(shí)箱熬，可以采用 List 或者鏈表类垦，甚至集合實(shí)現(xiàn)都可以。方法有很多城须，不用只局限于 JavaScript 數(shù)組這一種數(shù)據(jù)結(jié)構(gòu)蚤认，可以根據(jù)前面介紹的那些數(shù)據(jù)結(jié)構(gòu)進(jìn)行靈活組合。我這里就采用 ES6 原生的 Map 集合糕伐。同時(shí)砰琢，為了方便觀察效果，我將 getIndex() 修改回原始的定義良瞧，在實(shí)際應(yīng)用中陪汽，最好將其換成 djb2 函數(shù)。下面是經(jīng)過改進(jìn)的 IHashTable 接口和 HashTable 類：

interface IHashTable<T>{
    // 獲取索引值
    getIndex(flag:string):number;
    // 兩種存放方式：放入值褥蚯，放入一個(gè)值和簡(jiǎn)稱值
    put(flag:string,ele:T):void;
    // 獲取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 獲取散列中的元素
    toString():Map<string,T>[];    
}

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:Map<string,T>[] = [];
    // 散列表的長(zhǎng)度
    private dataStoreLen:number = 0;
    // 鹽值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 創(chuàng)建散列對(duì)象時(shí)傳入散列表的長(zhǎng)度和鹽值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        // let hash:number = 5381;
        // for (const c of flag) {
        //     hash = hash * 33 + c.charCodeAt(0);
        // }
        // return hash % 1013;
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置為計(jì)算出的 hash 值對(duì)數(shù)組的長(zhǎng)度取余
        return pos;
    }
    put(flag:string,ele:T):void{
        const pos:number = this.getIndex(flag);
        // 初始化操作
        if(this.dataStore[pos] === undefined){
            // 創(chuàng)建一個(gè) Map 對(duì)象
            const tmp = new Map<string,T>();
            tmp.set(flag,ele);
            this.dataStore[pos] = tmp;
        }else{
            this.dataStore[pos].set(flag,ele);
        }
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        return this.dataStore[pos].get(flag);
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const res = this.get(flag);        
        this.dataStore[pos].delete(flag);
        return res;
    }
    toString():Map<string,T>[]{
        const tmp:Map<string,T>[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

測(cè)試一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
h.put("ACKJ","ackj@ackj.com")
console.log(h.toString())

運(yùn)行結(jié)果：

[ Map { 'PENNY' => 'penny@penny.com' },
  Map { 'JERRY' => 'jerry@jerry.com' },
  Map { 'JACK' => 'jack@jack.com', 'ACKJ' => 'ackj@ackj.com' },
  Map { 'MIKE' => 'mike@mike.com' } ]

線性探測(cè)法

線性探測(cè)法是解決散列沖突的另一種常用手段挚冤，在使用 put() 方法向散列中插入元素時(shí)，如果發(fā)現(xiàn)產(chǎn)生了碰撞赞庶，就從獲取的索引處依次向下查找训挡，直到找到空位，將元素插入歧强。
下面是使用改進(jìn)后的 IHashTable 接口和 HashTable 類的實(shí)現(xiàn)：

interface IHashTable<T>{
    // 獲取索引值
    getIndex(flag:string):number;
    // 兩種存放方式：放入值澜薄，放入一個(gè)值和簡(jiǎn)稱值
    put(flag:string,ele:T):void;
    // 獲取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 查找元素
    find(flag:string,startPos:number):number;
    // 獲取散列中的元素
    toString():{key:string,value:T}[];    
}

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:{key:string,value:T}[] = [];
    // 散列表的長(zhǎng)度
    private dataStoreLen:number = 0;
    // 鹽值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 創(chuàng)建散列對(duì)象時(shí)傳入散列表的長(zhǎng)度和鹽值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        // let hash:number = 5381;
        // for (const c of flag) {
        //     hash = hash * 33 + c.charCodeAt(0);
        // }
        // return hash % 1013;
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置為計(jì)算出的 hash 值對(duì)數(shù)組的長(zhǎng)度取余
        return pos;
    }
    find(flag:string,startPos:number):number{
        let len:number = this.dataStoreLen;
        while(len--){
            const tmp = this.dataStore[startPos];
            if(tmp.key === flag){
                return startPos;
            }
            startPos++;
        }
    }    
    put(flag:string,ele:T):void{
        let pos:number = this.getIndex(flag);
        // 初始化操作
        if(this.dataStore[pos] === undefined){
            const tmp = {key:flag,value:ele};
            this.dataStore[pos] = tmp;
        }else{
            const tmp = {key:flag,value:ele};
            while(this.dataStore[pos] !== undefined){
                pos++;
            }            
            this.dataStore[pos] = tmp;
        }
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        const realPos:number = this.find(flag,pos);
        return this.dataStore[realPos].value;
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const realPos:number = this.find(flag,pos);
        const res = this.get(flag);        
        this.dataStore[realPos] = undefined;
        return res;
    }
    toString():{key:string,value:T}[]{
        const tmp:{key:string,value:T}[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

測(cè)試一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("ACKJ","ackj@ackj.com")
h.put("PENNY","penny@penny.com")
h.put("CKAJ","ckaj@ckaj.com")
h.put("AKCJ","ackj@ackj.com")
h.put("JERRY","jerry@jerry.com")
console.log(h.toString())

運(yùn)行結(jié)果：

[ { key: 'PENNY', value: 'penny@penny.com' },
  { key: 'JERRY', value: 'jerry@jerry.com' },
  { key: 'JACK', value: 'jack@jack.com' },
  { key: 'ACKJ', value: 'ackj@ackj.com' },
  { key: 'CKAJ', value: 'ckaj@ckaj.com' },
  { key: 'AKCJ', value: 'ackj@ackj.com' },
  { key: 'MIKE', value: 'mike@mike.com' } ]

至此，我們使用線性探測(cè)法解決了散列的碰撞問題誊锭，使用線性探測(cè)法解決碰撞問題時(shí)表悬，散列表需要足夠的長(zhǎng)度弥锄。

總結(jié)

本文介紹了散列這種數(shù)據(jù)結(jié)構(gòu)丧靡，散列是一種非線性的，可以快速查找和插入數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)籽暇，散列的核心是一個(gè)計(jì)算特征值的方法温治。在計(jì)算特征值時(shí)，容易產(chǎn)生沖突戒悠，要解決沖突可以從以下三個(gè)方面進(jìn)行：

優(yōu)化計(jì)算特征值的方法熬荆，推薦使用 djb2 函數(shù)
使用分離鏈接法，也稱作開鏈法解決沖突
使用線性探測(cè)法解決沖突

將這幾個(gè)方法進(jìn)行結(jié)合使用绸狐，可以達(dá)到更好的效果卤恳。

完累盗。

最后編輯于：2018.02.21 20:24:00

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市突琳，隨后出現(xiàn)的幾起案子若债，更是在濱河造成了極大的恐慌，老刑警劉巖拆融，帶你破解...
沈念sama閱讀 218,204評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蠢琳，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡镜豹，警方通過查閱死者的電腦和手機(jī)傲须，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,091評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)趟脂，“玉大人泰讽，你說(shuō)我怎么就攤上這事∥羝冢” “怎么了菇绵？”我有些...
開封第一講書人閱讀 164,548評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)镇眷。經(jīng)常有香客問我咬最，道長(zhǎng)，這世上最難降的妖魔是什么欠动？我笑而不...
開封第一講書人閱讀 58,657評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任永乌，我火速辦了婚禮，結(jié)果婚禮上具伍，老公的妹妹穿的比我還像新娘翅雏。我一直安慰自己，他們只是感情好人芽，可當(dāng)我...
茶點(diǎn)故事閱讀 67,689評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布望几。她就那樣靜靜地躺著，像睡著了一般萤厅。火紅的嫁衣襯著肌膚如雪橄抹。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,554評(píng)論 1贊 305
城市分裂傳說(shuō)
那天惕味，我揣著相機(jī)與錄音楼誓，去河邊找鬼。笑死名挥，一個(gè)胖子當(dāng)著我的面吹牛疟羹，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播，決...
沈念sama閱讀 40,302評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼榄融，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼参淫！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起愧杯，我...
開封第一講書人閱讀 39,216評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤黄刚，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后民效，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體憔维，經(jīng)...
沈念sama閱讀 45,661評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,851評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年畏邢，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了业扒。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,977評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡舒萎，死狀恐怖程储，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情臂寝，我是刑警寧澤章鲤，帶...
沈念sama閱讀 35,697評(píng)論 5贊 347
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站咆贬，受9級(jí)特大地震影響败徊，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜掏缎，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,306評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一皱蹦、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧眷蜈，春花似錦沪哺、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,898評(píng)論 0贊 22
一樁弒父案辜妓，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至忌怎，卻和暖如春籍滴，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背呆躲。一陣腳步聲響...
開封第一講書人閱讀 33,019評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工异逐，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留捶索，地道東北人插掂。一個(gè)月前我還...
沈念sama閱讀 48,138評(píng)論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親辅甥。傳聞我的和親對(duì)象是個(gè)殘疾皇子酝润，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,927評(píng)論 2贊 355