什么散列

散列是提供對(duì)任何有名項(xiàng)提供存取操作和刪除操作的列表萤衰。這種結(jié)構(gòu)的目的是提供常數(shù)時(shí)間的基本操作阎肝。

舉個(gè)例子：如果所有元素都是16-bits且不帶正負(fù)號(hào)的整數(shù)，范圍是0-65535凑阶。那么簡(jiǎn)單運(yùn)用一個(gè) array 就可以滿足上面的期望稻据。首先配置一個(gè)arrayA.，擁有65536個(gè)元素衬鱼，初值全部為0业筏，每個(gè)元素值代表相應(yīng)元素出現(xiàn)的次數(shù)。如果插入元素i馁启，就執(zhí)行A[i]++驾孔，如果刪除元素i，就執(zhí)行A[i]--惯疙，如果搜素元素就檢查A[i]是否為0翠勉。以上的每一個(gè)操作都是常數(shù)時(shí)間。這種解法的額外負(fù)擔(dān)是array的空間和初始化時(shí)間霉颠。

繪圖1.jpg

但是這種解法存在2個(gè)現(xiàn)實(shí)的問題：

• 如果元素很多对碌，那么要準(zhǔn)備的數(shù)組大小就很大，空間占用太大蒿偎。
• 如果元素是其他的類型（非整型）朽们，那么就不能作為數(shù)組索引。

第一個(gè)問題：
我們是可以采用一個(gè)映射函數(shù)诉位，將大數(shù)轉(zhuǎn)換為小數(shù)骑脱，比如給定整數(shù)x，那么
x % array.size()苍糠，那么就會(huì)得到一個(gè)范圍在 [ 0叁丧，array.size() - 1 ] 之間的數(shù)，也可以作為數(shù)組索引岳瞭，但這會(huì)引入新的問題：如何解決碰撞沖突的問題拥娄。

第二個(gè)問題：
我們可以將一個(gè)非整數(shù)類型的轉(zhuǎn)換為整型，比如字符串"string"瞳筏，轉(zhuǎn)換為ASCII編碼稚瘾。

線性探測(cè)

當(dāng)用散列函數(shù)計(jì)算出元素的插入位置，而該位置已經(jīng)不能使用時(shí)姚炕，最簡(jiǎn)單的辦法就是循序往下一一尋找摊欠，直到找到一個(gè)可用的位置為止。
元素的刪除則可以采用"惰性刪除"钻心，也就是標(biāo)記刪除記號(hào)凄硼，實(shí)際刪除則待散列表重新整理時(shí)再進(jìn)行。

線性探測(cè).jpg

但線性探測(cè)會(huì)有一個(gè)不好的現(xiàn)象是：如圖最后狀態(tài)中捷沸，除非元素進(jìn)過散列函數(shù)計(jì)算之后直接得出位置在#4 ~ #7摊沉，否則#4 ~ #7永遠(yuǎn)不可能會(huì)被優(yōu)先考慮，因?yàn)?8 9 0 1 2已被占痒给，遇到?jīng)_突會(huì)線性巡訪整個(gè)表格) #3一直會(huì)被優(yōu)先考慮说墨。
這樣會(huì)暴露出一個(gè)問題：主集團(tuán)(primary clustering)陷阱骏全。散列表中是一大團(tuán)被用過的方格，插入操作極有可能在主集團(tuán)所形成的泥濘中奮力爬行尼斧，不斷解決碰撞問題姜贡，最后再找到空位置。然而插入之后又助長(zhǎng)了主集團(tuán)的長(zhǎng)度棺棵。

public class LinearProbingHashST<Key, Value> {
    private int n;            // 當(dāng)前key-value元素對(duì)數(shù)
    private int m;            // 線性表（key-value）的總長(zhǎng)度
    private Key[] keys;     // the keys
    private Value[] vals;   // the values

    public void put(Key key, Value val) {
        .....省略參數(shù)的有效性判斷
        // 如果已經(jīng)用掉50%楼咳，則擴(kuò)容，減小主集團(tuán)的影響
        if (n >= m / 2)
          resize(2 * m);      // resize里面會(huì)重新計(jì)算散列值烛恤，插入元素
    
        // 線性探測(cè)過程
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
            // 如果已經(jīng)存在key母怜，則更新value
            if (keys[i].equals(key)) {
                vals[i] = val;
                    return;
            }
        }
        keys[i] = key;
        vals[i] = val;
        n++;
    }
    
    public void delete(Key key) {
        ...... 省略參數(shù)有效性判斷
        // find position i of key
        int i = hash(key);
        while (!key.equals(keys[i]))
            i = (i + 1) % m;
        
      // delete key and associated value
        keys[i] = null;
        vals[i] = null;

        // rehash all keys in same cluster
        i = (i + 1) % m;
        while (keys[i] != null) {
            // delete keys[i] an vals[i] and reinsert
            Key keyToRehash = keys[i];
            Value valToRehash = vals[i];
            keys[i] = null;
            vals[i] = null;
            n--;
            put(keyToRehash, valToRehash);
            i = (i + 1) % m;
        }
        n--;
        // halves size of array if it's 12.5% full or less
        if (n > 0 && n <= m / 8)
            resize(m / 2);
    }
}

二次探測(cè)

二次探測(cè)主要用于解決主集團(tuán)的問題。
其命名由來是因?yàn)榻鉀Q碰撞的方程式：F(i) = i^2是一個(gè)二次方程式缚柏。更明確的說苹熏，如果散列函數(shù)計(jì)算出新元素位置H，而該位置實(shí)際上已經(jīng)被使用币喧，那么我們就依次嘗試H+1^{2轨域，H+2}2，H+3^2......而不是像線性探測(cè)一樣依序嘗試：H+1杀餐，H+2干发，H+3.......

二次探測(cè).jpg

二次探測(cè)可以消除主集團(tuán)，但卻可能造成次集團(tuán)：兩個(gè)元素經(jīng)散列函數(shù)計(jì)算出來的位置若相同史翘，那么插入時(shí)所探測(cè)的位置也相同铐然，形成某種浪費(fèi)。

但總體來說恶座，還是二次探測(cè)相比于線性探測(cè)，仍然值得選擇沥阳。

開鏈法

開鏈法是在每一個(gè)表格元素中維護(hù)一個(gè)list跨琳，散列函數(shù)分配某一個(gè)list，然后再那個(gè)list身上執(zhí)行元素的插入桐罕，搜尋脉让，刪除等操作。雖然針對(duì)list是一種線性搜索功炮，但list夠短溅潜。速度還是很快。

開鏈法jpg

散列函數(shù)

參考資料
[1] 《STL源碼剖析》侯捷
[2] 《算法》4th [美] Robert Sedgewick薪伏，Kevin Wayne