本文根據(jù)CMU15-445課程內(nèi)容編寫(xiě)，因?yàn)閿?shù)據(jù)庫(kù)術(shù)語(yǔ)較多，為避免翻譯問(wèn)題帶來(lái)的理解偏差，部分術(shù)語(yǔ)使用英語(yǔ)表達(dá)。
DBMS需要使用各種各樣的數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)系統(tǒng)的內(nèi)部數(shù)據(jù)。比如：
當(dāng)我們?cè)贒BMS中實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)時(shí)，有兩點(diǎn)需要特別注意：
哈希表是一種抽象數(shù)據(jù)類型，它使用哈希函數(shù)將數(shù)據(jù)從鍵空間（key space）映射到值空間（value space）。在哈希表上做增刪改查等操作的平均時(shí)間復(fù)雜度是 O ( 1 ) O(1) O(1)（最差的情況是 O ( n ) O(n) O(n)），空間復(fù)雜度是 O ( n ) O(n) O(n)。值得注意的是，即使哈希操作的平均時(shí)間復(fù)雜度已經(jīng)達(dá)到了 O ( 1 ) O(1) O(1)，在這個(gè)常數(shù)級(jí)別上的優(yōu)化依然是很有價(jià)值的。
哈希表的實(shí)現(xiàn)主要包括兩部分：
一般來(lái)說(shuō)，哈希函數(shù)以鍵key作為輸入，輸出一個(gè)確定的整數(shù)值（在這里，確定的意思是只要哈希函數(shù)和哈希函數(shù)的種子不變，每次輸入同一個(gè)鍵key，輸出的都是同一個(gè)整數(shù)）。
對(duì)于DBMS來(lái)說(shuō)，使用加密的哈希函數(shù)是沒(méi)有必要的，因?yàn)榇蠖鄶?shù)時(shí)候，哈希函數(shù)僅僅在DBMS內(nèi)部使用，并不會(huì)暴露給外部系統(tǒng)，因此，DBMS沒(méi)有必要保護(hù)鍵key的內(nèi)容。我們僅僅需要考慮哈希函數(shù)的運(yùn)行速度和碰撞率。
4. 靜態(tài)的哈希方案（Static Hashing Schemes）靜態(tài)的哈希方案要求事先知道我們大約需要對(duì)多少keys進(jìn)行哈希。在靜態(tài)哈希方案中，哈希表的大小是固定的。如果哈希表的空間用完，那么我們需要重新構(gòu)建一個(gè)更大的哈希表，這是一個(gè)非常耗時(shí)的操作。新的哈希表的大小一般是原來(lái)的兩倍。但是在現(xiàn)實(shí)中，我們事先通常不知道需要存儲(chǔ)的數(shù)據(jù)有多少。
4.1 線性探測(cè)哈希（Linear probe hashing）這是最普遍的哈希方案，一般來(lái)說(shuō)也是最快的。線性探測(cè)哈希方式首先申請(qǐng)一大塊內(nèi)存作為環(huán)形數(shù)組。
插入數(shù)據(jù)時(shí)，如果插入位置已經(jīng)被占用，那么就從插入位置向下查找，直到找到一個(gè)空位并將數(shù)據(jù)插入到這個(gè)空位中。如果一直掃描到數(shù)組尾部都沒(méi)有空位，那么就從數(shù)組頭部開(kāi)始向下掃描（我們申請(qǐng)的是邏輯上的環(huán)形數(shù)組）。如果整個(gè)哈希表都滿了，那么就需要重新申請(qǐng)更大的內(nèi)容，然后將所有數(shù)據(jù)重新插入到新的哈希表中。
查找數(shù)據(jù)時(shí)，計(jì)算key對(duì)應(yīng)的哈希值，查找數(shù)組對(duì)應(yīng)位置的key是否和所需的key相同，如果不同，那么向下掃描直到找到所需的鍵值對(duì)（查找成功）或者遇到一個(gè)空位（查找失?。?/p>
刪除數(shù)據(jù)時(shí)，如果僅僅將對(duì)應(yīng)位置的鍵值對(duì)抹去可能會(huì)導(dǎo)致該鍵值對(duì)下方的鍵值對(duì)在之后的查找中失敗。舉個(gè)例子，首先看圖1，A，C，D經(jīng)過(guò)哈希之后的位置分別是數(shù)組的第3，3，4位，經(jīng)過(guò)線性探測(cè)之后，C插入到第4格，D插入到第5格。現(xiàn)在如果刪除C，就會(huì)出現(xiàn)圖2的情況，這時(shí)，如果我們查找D，哈希值為4，查找對(duì)應(yīng)位置是沒(méi)有數(shù)據(jù)，此時(shí)就會(huì)認(rèn)定D不存在于哈希表中（發(fā)生錯(cuò)誤）。
為了解決這個(gè)問(wèn)題，在刪除時(shí)有兩種處理方式：
當(dāng)鍵key不唯一時(shí)，即有存在多個(gè)鍵值對(duì)，其鍵key相同，但是值不同。這種情況有有兩種處理方式：
線性探測(cè)哈希的變種，羅賓漢是一個(gè)“劫富濟(jì)貧”的強(qiáng)盜，在哈希表，也有這樣一個(gè)“劫富濟(jì)貧”的操作。首先我們定義“貧富”的概念，如果一個(gè)鍵值對(duì)的實(shí)際位置和其理想位置（經(jīng)過(guò)一次哈希函數(shù)計(jì)算得到的位置）相對(duì)比較遠(yuǎn)，那么就是相對(duì)“貧窮”的；反之，就是相對(duì)“富有”的。
那么“劫富濟(jì)貧”的操作具體是什么呢？首先，每個(gè)鍵值對(duì)都需要記錄自己的“貧富”，也就是自己離理想位置的距離。這樣在插入的過(guò)程中，如果發(fā)現(xiàn)某一個(gè)位置已經(jīng)被占用，那么就比較當(dāng)前插入鍵值對(duì)和占用該位置的鍵值對(duì)的貧富程度，如果當(dāng)前插入的鍵值對(duì)比較貧窮，也就是離自己的理想位置更遠(yuǎn)，那么就替換占用該位置的鍵值對(duì)。
具體的說(shuō)看下圖：A，C，D已經(jīng)占用了3個(gè)空間，此時(shí)，E計(jì)算的哈希值為3，但是插入位置已經(jīng)被A占據(jù)，那么就比較其貧富程度，發(fā)現(xiàn)，A和E此時(shí)一樣富有，不做處理，E繼續(xù)向下尋找，離自己的理想位置距離加1。查找到C，C和E此時(shí)里自己的理想位置距離都是1，不做處理，繼續(xù)向下尋找，距離加1。查找到D，發(fā)現(xiàn)D離自己的理想位置距離更近，即D此時(shí)比E“富有”，那么就讓E替換D，然后帶著D繼續(xù)向下尋找。D向下查找發(fā)現(xiàn)一個(gè)空位，直接插入。
這樣做的好處是什么呢？大的好處就是各個(gè)鍵值對(duì)離自己的理想位置的距離變得“均衡”了，或許對(duì)查詢的平均時(shí)間復(fù)雜度有一定的優(yōu)化，但是一定復(fù)雜化了插入操作的時(shí)間復(fù)雜度。
實(shí)際上，經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，這種方法的效率不如線性探測(cè)法，不過(guò)這種方法的思想還是很有價(jià)值的。
4.3 布谷時(shí)鐘哈希（Cuckoo Hashing）布谷鐘擺動(dòng)哈希方式準(zhǔn)備了兩個(gè)哈希表來(lái)存儲(chǔ)數(shù)據(jù)，兩個(gè)哈希表一般采用不同種子的哈希函數(shù)，并且提供 O ( 1 ) O(1) O(1)時(shí)間復(fù)雜度的查找和刪除，但是插入操作會(huì)比較復(fù)雜。和線性探測(cè)不同，布谷時(shí)鐘擺動(dòng)哈希完全不需要掃描，具體來(lái)說(shuō)：
對(duì)于查找和刪除操作，在兩個(gè)哈希表上分別運(yùn)行哈希函數(shù)，然后比較鍵值對(duì)決定哪一個(gè)是所需的鍵值對(duì)。
而對(duì)于插入操作，我們依然在兩個(gè)哈希表運(yùn)行哈希函數(shù)，但是情況稍有些復(fù)雜。
靜態(tài)哈希方案都有一個(gè)大前提就是我們事前是知道哈希表需要容納多少鍵值對(duì)的，否則如果出現(xiàn)預(yù)設(shè)的容量過(guò)大或者過(guò)小問(wèn)題時(shí)，我們對(duì)其擴(kuò)容或者縮容的代價(jià)都比較大（可以采用一致性哈希）。
因此，我們?yōu)榱私鉀Q這個(gè)問(wèn)題，提出了一些動(dòng)態(tài)的哈希方案，即哈希表的運(yùn)行的過(guò)程中可以按需增長(zhǎng)或者減小。下面介紹三種動(dòng)態(tài)哈希方案：
5.1 鏈?zhǔn)焦＃–hained Hashing）這是最簡(jiǎn)單的動(dòng)態(tài)哈希方案，也是java或者jvm中默認(rèn)的哈希方案。鏈?zhǔn)焦Ｖ?，哈希表中?shù)組的成員是buckets的鏈表，因此，當(dāng)發(fā)生沖突時(shí)，將元素添加到對(duì)應(yīng)Bucket的末尾即可，如果Bucket已滿，則創(chuàng)建一個(gè)新的Bucket即可。
線性哈希是可擴(kuò)展哈希的改進(jìn)，可擴(kuò)展哈希有一個(gè)小的性能瓶頸，在bucket分裂且需要擴(kuò)展slot array時(shí)，需要對(duì)整個(gè)slot array加鎖直到bucket分裂完成。為了解決這個(gè)問(wèn)題，提出了線性哈希方式。哈希表維護(hù)一個(gè)指針，指向下一個(gè)準(zhǔn)備分裂的bucket，并且線性哈希采用多個(gè)哈希函數(shù)來(lái)尋找正確的bucket。
當(dāng)插入過(guò)程中，任何一個(gè)bucket溢出，都將分裂指針指向的bucket（無(wú)論這個(gè)bucket是否溢出），舉個(gè)例子，，如下圖。
最初，指針指向第一個(gè)bucket，即當(dāng)任何一個(gè)bucket發(fā)生溢出時(shí)，都分裂第一個(gè)bucket。且現(xiàn)在只有一個(gè)哈希函數(shù)。
現(xiàn)需要插入17，發(fā)現(xiàn)對(duì)應(yīng)的bucket已滿，發(fā)生了溢出，因此需要分裂第一個(gè)bucket.
現(xiàn)在將第一個(gè)bucket分裂，就需要增加一個(gè)bucket，那么哈希哈希表中已經(jīng)有了5個(gè)bucket，原來(lái)的哈希函數(shù)中的n為4，不能滿足使用要求，需要增加新的哈希函數(shù) h a s h 2 hash_2 hash2?。然后使用新的哈希函數(shù)重新分配第一個(gè)bucket中的元素。
現(xiàn)在我們?cè)賮?lái)觀察查詢過(guò)程，現(xiàn)在需要查詢20，首先使用第一個(gè)哈希函數(shù)，發(fā)現(xiàn)哈希值為0，即第一個(gè)bucket。但是這個(gè)哈希值落在了分裂指針的上面，即我們要查詢的值落在一個(gè)已經(jīng)分裂的bucket上，而這個(gè)bucket中的所有鍵值對(duì)已經(jīng)用第二個(gè)哈希函數(shù)重新分配位置，因此，需要用第二個(gè)哈希函數(shù)重新計(jì)算哈希值為4，即第五個(gè)bucket中，然后在這個(gè)bucket中循序查詢即可。
哈希表是一種速度非常快的數(shù)據(jù)結(jié)構(gòu)，支持 O ( 1 ) O(1) O(1)級(jí)別的查找速度，哈希表的設(shè)計(jì)主要包括哈希函數(shù)和哈希方案。其中哈希方案包括靜態(tài)方案和動(dòng)態(tài)方案，靜態(tài)方案即哈希表的大小是固定的，動(dòng)態(tài)方案是哈希表的大小可以按需生長(zhǎng)或者縮小。雖然對(duì)于哈希表有許多改進(jìn)，但是其中速度最快還是最初的線性探測(cè)哈希。
哈希表是普遍使用的數(shù)據(jù)結(jié)構(gòu)，有部分?jǐn)?shù)據(jù)庫(kù)使用哈希表作為索引（例如memcached），但哈希表并不適合用于索引的構(gòu)建，因?yàn)楣：瘮?shù)查找需要完整的key值，且不支持快速查找大于某個(gè)key的數(shù)據(jù)。實(shí)際上，構(gòu)建索引一般使用B+樹(shù)的方式，B+樹(shù)是另一種極為優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。
測(cè)哈希**。
哈希表是普遍使用的數(shù)據(jù)結(jié)構(gòu)，有部分?jǐn)?shù)據(jù)庫(kù)使用哈希表作為索引（例如memcached），但哈希表并不適合用于索引的構(gòu)建，因?yàn)楣：瘮?shù)查找需要完整的key值，且不支持快速查找大于某個(gè)key的數(shù)據(jù)。實(shí)際上，構(gòu)建索引一般使用B+樹(shù)的方式，B+樹(shù)是另一種極為優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
重慶分公司
重慶分公司
