https://15445.courses.cs.cmu.edu/fall2018/slides/06-hashtables.pdf

DBMS對系統(tǒng)內(nèi)部的許多不同部分使用各種數(shù)據(jù)結(jié)構(gòu)：
?內(nèi)部元數(shù)據(jù)：跟蹤有關(guān)數(shù)據(jù)庫和系統(tǒng)狀態(tài)的信息。
?核心數(shù)據(jù)存儲：可用作數(shù)據(jù)庫中元組的基本存儲。
?臨時數(shù)據(jù)結(jié)構(gòu)：DBMS可以在處理查詢時動態(tài)構(gòu)建數(shù)據(jù)結(jié)構(gòu)以加速執(zhí)行（例如，用于連接的哈希表）。
?表索引：輔助數(shù)據(jù)結(jié)構(gòu)，以便更容易找到特定元組。
設(shè)計決策：
1.數(shù)據(jù)組織：我們?nèi)绾尾季謨?nèi)存以及在數(shù)據(jù)結(jié)構(gòu)中存儲哪些信息。
2.并發(fā)：如何在不引起問題的情況下啟用多個線程來訪問數(shù)據(jù)結(jié)構(gòu)请毛。

Hash 表 設(shè)計理念

哈希表實(shí)現(xiàn)了將鍵映射到值的關(guān)聯(lián)數(shù)組抽象數(shù)據(jù)類型。
哈希表實(shí)現(xiàn)由兩部分組成：

?散列函數(shù)：如何將大密鑰空間映射到較小的空間里瞭亮。我們需要考慮如何在快速與沖突率之間的權(quán)衡方仿。

?散列方案：如何在散列后處理關(guān)鍵沖突。 需要考慮需要分配大型哈希表以減少沖突與執(zhí)行其他指令以查找/插入密鑰之間的權(quán)衡统翩。

考慮一個簡單的靜態(tài)哈希表實(shí)現(xiàn)：
?為每個元素分配一個帶有一個插槽的巨型陣列仙蚜。 通過元素數(shù)修改鍵以查找數(shù)組中的偏移量。
?有問題的假設(shè)：
你提前了解了元素的數(shù)量
2.每個密鑰都是唯一的
3.完美散列函數(shù)（如果key1厂汗！= key2則hash（key1）鳍征！= hash（key2））

經(jīng)典的hash算法比較

首先又一些hash函數(shù)，我們會想到面徽，如md5,crc,sha艳丛。但是我們不需要這些加密哈希函數(shù)，因?yàn)槲覀儾恍枰獜墓Ｖ蝎@取密鑰趟紊。 我們只關(guān)心速度和碰撞率氮双。
下面是幾種hash函數(shù)的吞吐率。

image.png

靜態(tài)hash結(jié)構(gòu)

1 開放尋址法

哈希沖突解決策略：開放尋址法（Open Addressing）

通常采用的沖突解決策略為開放尋址法（Open Addressing）霎匈，將所有的元素都存放在哈希表內(nèi)的數(shù)組中戴差，不使用額外的數(shù)據(jù)結(jié)構(gòu)。

開放尋址法的最簡單的一種實(shí)現(xiàn)就是線性探查（Linear Probing）铛嘱，步驟如下：

1. 當(dāng)插入新的元素時暖释，使用哈希函數(shù)在哈希表中定位元素位置；
2. 檢查哈希表中該位置是否已經(jīng)存在元素墨吓。如果該位置內(nèi)容為空球匕，則插入并返回，否則轉(zhuǎn)向步驟 3帖烘。
3. 如果該位置為 i亮曹，則檢查 i+1 是否為空，如果已被占用，則檢查 i+2照卦，依此類推式矫，直到找到一個內(nèi)容為空的位置。

線性探查（Linear Probing）方式雖然簡單役耕，但并不是解決沖突的最好的策略采转，因?yàn)樗鼤?dǎo)致同類哈希的聚集（Primary Clustering）。這導(dǎo)致搜索哈希表時瞬痘，沖突依然存在故慈。如果我們要訪問 Edward 的信息，因?yàn)?Edward 的社保號 111-00-1235 哈希為 1235图云，然而我們在 1235 位置找到的是 Bob惯悠，所以再搜索 1236邻邮，找到的卻是 Danny竣况，以此類推直到找到 Edward。

2. 羅賓漢哈希

羅賓漢哈贤惭希可以顯著降低探查長度的方差丹泉。我們來看一下它是怎么做的：

對每個哈希表中的元素，記錄插入時的探查長度
當(dāng)插入一個新元素時鸭蛙，對于探查過程中的元素摹恨，如果它的探查長度小于當(dāng)前插入元素的探查長度，那么交換這兩個元素 (以及探測長度)娶视，然后繼續(xù)探查
也就是說晒哄，事實(shí)上大家的探查長度更加平均了，所以期望最長探查長度也會顯著的下降肪获。這也是羅賓漢 (英國傳說中的俠盜) 哈希名字的來源寝凌，劫富濟(jì)貧。雖然大部分元素的探查長度都更趨近于平均值孝赫，不是一次就能查到较木，但是由于這部分開銷較 CPU 加載 cache line 開銷可以忽略不計，所以整體上仍有顯著的提高青柄。

如果沒有沖突伐债，數(shù)值是0，如果沖突1次數(shù)值為1.

image.png

image.png

當(dāng)沖突的次數(shù)超過當(dāng)前的次數(shù)了致开，就先把這個坑占了峰锁，如圖e 占了 d。
就要把當(dāng)前的d再計1次沖突双戳。

image.png

image.png

3. cuckoo hash

使用具有不同散列函數(shù)的多個散列表祖今。
→在插入時，檢查每個表并選擇任何有空閑插槽的表。
→如果沒有表有空閑插槽千诬，則從其中一個中刪除該元素耍目，然后重新散列它以找到新位置。
查找和刪除始終為O（1）徐绑，因?yàn)槊總€哈希表只檢查一個位置邪驮。

移動鍵時，確保我們不會陷入無限循環(huán)傲茄。
如果我們找到一個循環(huán)毅访，那么我們可以用新的散列函數(shù)重建整個散列表。
→使用兩個哈希函數(shù)盘榨，我們（可能）不需要重建表喻粹，直到它滿50％。
→使用三個哈希函數(shù)草巡，我們（可能）不需要重建表守呜，直到它滿約90％。

image.png

image.png

動態(tài)hash結(jié)構(gòu)

1. Chained Hash

?為哈希表中的每個槽維護(hù)一個桶的鏈表山憨。
?通過將具有相同散列鍵的元素放入同一個存儲桶中來解決沖突查乒。
?如果存儲桶已滿，請?zhí)砑恿硪粋€存儲桶列表郁竟。 哈希表可以無限增長玛迄，因?yàn)槟粩嗵砑有峦啊?br> ?要處理并發(fā)性，您只需要在每個存儲桶上設(shè)置一個latch

image.png

?非唯一鍵的方法

1.單獨(dú)的鏈表：將值存儲在單獨(dú)的存儲區(qū)域中
2.存儲在存儲桶中：將重復(fù)的密鑰存儲在相同的存儲桶中（把value 和key 存在一起）

image.png

2. extensible hash

http://www.cosc.brocku.ca/~efoxwell/2P03/slides/Week12Slides.pdf
實(shí)現(xiàn)見project 1

3. linear hash

線性哈希是一種動態(tài)擴(kuò)展哈希表的方法棚亩。

線性哈希的數(shù)學(xué)原理:

假定key = 5 蓖议、 9 、13

key % 4 = 1

現(xiàn)在我們對8求余

5 % 8 = 5

9 % 8=1

13 % 8 = 5

由上面的規(guī)律可以得出

(任意key) % n = M

(任意key) %2n = M或 (任意key) %2n = M + n

線性哈希的具體實(shí)現(xiàn):

我們假設(shè)初始化的哈希表如下:

image.png

為了方便敘述讥蟆，我們作出以下假定:

1：為了使哈希表能進(jìn)行動態(tài)的分裂勒虾，我們從桶0開始設(shè)定一個分裂點(diǎn)。

2：一個桶的容量為listSize = 5攻询，當(dāng)桶的容量超出后就從分裂點(diǎn)開始進(jìn)行分裂从撼。

3：hash函數(shù)為 h0 = key %4 h1 = key % 8，h1會在分裂時使用钧栖。

4：整個表初始化包含了4個桶低零，桶號為0-3，并已提前插入了部分的數(shù)據(jù)拯杠。

分裂過程如下:

現(xiàn)在插入key = 27

1:進(jìn)行哈希運(yùn)算掏婶，h0 = 27 % 4 = 3

2:將key = 27插入桶3，但發(fā)現(xiàn)桶3已經(jīng)達(dá)到了桶的容量潭陪，所以觸發(fā)哈希分裂

3:由于現(xiàn)在分裂點(diǎn)處于0桶雄妥，所以我們對0桶進(jìn)行分割最蕾。這里需要注意雖然這里是3桶滿了，但我們并不會直接從3桶進(jìn)行分割老厌，而是從分割點(diǎn)進(jìn)行分割瘟则。這里為什么這么做，在下面會進(jìn)一步介紹枝秤。

4:對分割點(diǎn)所指向的桶(桶0)所包含的key采用新的hash函數(shù)(h1)進(jìn)行分割醋拧。

對所有key進(jìn)行新哈希函數(shù)運(yùn)算后，將產(chǎn)生如下的哈希表

image.png

5:雖然進(jìn)行了分裂淀弹，但桶3并不是分裂點(diǎn)丹壕，所以桶3會將多出的key，放于溢出頁.,一直等到桶3進(jìn)行分裂薇溃。

6:進(jìn)行分裂后菌赖，將分裂點(diǎn)向后移動一位。

一次完整的分裂結(jié)束沐序。

key的讀取:

采用h0對key進(jìn)行計算琉用。

如果算出的桶號小于了分裂點(diǎn)，表示桶已經(jīng)進(jìn)行的分裂薄啥，我們采用h1進(jìn)行hash運(yùn)算辕羽，算出key所對應(yīng)的真正的桶號逛尚。再從真正的桶里取出value

如果算出的桶號大于了分裂點(diǎn)垄惧，那么表示此桶還沒進(jìn)行分裂，直接從當(dāng)前桶進(jìn)行讀取value绰寞。

說明:

1:如果下一次key插入0到逊、1、2滤钱、4桶觉壶，是不會觸發(fā)分裂。（沒有超出桶的容量）如果是插入桶3件缸，用戶在實(shí)現(xiàn)時可以自己設(shè)定铜靶，可以一旦插入就觸發(fā)，也可以等溢出頁達(dá)到listSize再觸發(fā)新的分裂他炊。

2:現(xiàn)在0桶被分裂了争剿，新數(shù)據(jù)的插入怎么才能保證沒分裂的桶能正常工作，已經(jīng)分裂的桶能將部分插入到新分裂的桶呢?

只要分裂點(diǎn)小于桶的總數(shù)痊末，我們依然采用h0函數(shù)進(jìn)行哈希計算蚕苇。

如果哈希結(jié)果小于分裂號，那么表示這個key所插入的桶已經(jīng)進(jìn)行了分割凿叠，那么我就采用h1再次進(jìn)行哈希涩笤，而h1的哈希結(jié)果就這個key所該插入的桶號嚼吞。

如果哈希結(jié)果大于分裂號，那么表示這個key所插入的桶還沒有進(jìn)行分裂蹬碧。直接插入舱禽。

這也是為什么雖然是桶3的容量不足，但分裂的桶是分裂點(diǎn)所指向的桶恩沽。如果直接在桶3進(jìn)行分裂呢蔫，那么當(dāng)新的key插入的時候就不能正常的判斷哪些桶已經(jīng)進(jìn)行了分裂。

3:如果使用分割點(diǎn)飒筑，就具備了無限擴(kuò)展的能力片吊。當(dāng)分割點(diǎn)移動到最后一個桶(桶3)。再出現(xiàn)分裂协屡。那么分割點(diǎn)就會回到桶0俏脊，到這個時候，h0作廢肤晓，h1替代h0, h2(key % 12)替代h1爷贫。那么又可以開始動態(tài)分割。那個整個初始化狀態(tài)就發(fā)生了變化补憾。就好像沒有發(fā)生過分裂漫萄。那么上面的規(guī)則就可以循環(huán)使用。

3:線性哈希的論文中是按上面的規(guī)則來進(jìn)行分裂的盈匾。其實(shí)我們可以安裝自己的實(shí)際情況來進(jìn)行改動腾务。

假如我們現(xiàn)在希望去掉分割點(diǎn)，一旦哪個桶滿了削饵，馬上對這個桶進(jìn)行分割岩瘦。

可以考慮了以下方案：

1：為所有桶增加一個標(biāo)志位。初始化的時候?qū)λ型暗臉?biāo)志位清空窿撬。

2：一旦某個桶滿了启昧，直接對這個桶進(jìn)行分割，然后將設(shè)置標(biāo)志位劈伴。當(dāng)新的數(shù)據(jù)插入的時候密末，經(jīng)過哈希計算（h0）發(fā)現(xiàn)這個桶已經(jīng)分裂了，那么就采用新的哈希函數(shù)(h1)來計算分裂之后的桶號跛璧。在讀取數(shù)據(jù)的時候處理類似严里。

   Linehash 實(shí)現(xiàn)代碼如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LineHash {
    
    public int pageSize;  //桶的容量

    public int overPoint = 0; //分裂點(diǎn)

    public int listSize = 4; //哈希表的初始大小

    public int initlistSize = 4; //哈希大小的記錄值
     
    public int workRound = 1;  //分裂輪數(shù)
    
    public List> hash = null; //模擬哈希表

    public LineHash(int pageSIze) {
        this.pageSize = pageSIze;
        hash = new ArrayList>(4);
        for (int i = 0; i < listSize; i++) {
            hash.add(new HashMap()); //向哈希表中初始化桶
        }
    }
    //查詢函數(shù)
    public String getKeyValue(int key){
        int index = hashFun(key, workRound); //根據(jù)分裂輪數(shù)調(diào)用不同的哈希函數(shù)
        if(index < overPoint){              //當(dāng)前桶產(chǎn)生了分裂
            index = hashFun(key, workRound + 1); //采用新的哈希函數(shù)進(jìn)行計算
        }
        return hash.get(index).get(key);
    }
    //添加函數(shù)
    public void addKeyValue(int key, String value) { 
        int index = hashFun(key, workRound);   
        if(index < overPoint){
            index = hashFun(key, workRound + 1);
        }
        Map map = hash.get(index);
        if (map.size() < pageSize) {   //判斷當(dāng)前桶是否滿了
            map.put(key, value);
        } else {
            map.put(key, value);  
            splitHash();              //滿了就進(jìn)行分裂
        }
    }

    public int hashFun(int key, int f1) {
        return key % (4 * f1);
    }

    public void splitHash() {
        Map OldMap = hash.get(overPoint);   //舊桶
        Map NewMap = new HashMap(); //分裂產(chǎn)生的新桶

        Integer[] keyList = OldMap.keySet().toArray(new Integer[0]);
        for (int i = 0; i < keyList.length; i++) {  //準(zhǔn)備移動一半的數(shù)據(jù)到新桶
            int key = keyList[i].intValue();
            int index = hashFun(key, workRound + 1);
            if (index >= listSize) {
                String value = OldMap.get(key);
                OldMap.remove(key);
                NewMap.put(key, value);
            }
        }
        hash.add(NewMap);  //將新桶放入哈希表
        listSize++;  //哈希表長度增加
        overPoint++;  //分裂點(diǎn)移動
        if(overPoint >= initlistSize){  //分裂點(diǎn)移動了一輪就更換新的哈希函數(shù)
            workRound++;
            initlistSize = initlistSize * 2;
            overPoint = 0;
        }
    }
}