06-哈希表-創(chuàng)新互聯(lián)

本文根據(jù)CMU15-445課程內(nèi)容編寫，因?yàn)閿?shù)據(jù)庫術(shù)語較多，為避免翻譯問題帶來的理解偏差，部分術(shù)語使用英語表達(dá)。

目前成都創(chuàng)新互聯(lián)公司已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計(jì)、夏縣網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。1. 數(shù)據(jù)結(jié)構(gòu)

DBMS需要使用各種各樣的數(shù)據(jù)結(jié)構(gòu)來維護(hù)系統(tǒng)的內(nèi)部數(shù)據(jù)。比如：

• 內(nèi)部元信息（Internal Meta-Data）：這些數(shù)據(jù)記錄了數(shù)據(jù)庫的一些關(guān)鍵信息和系統(tǒng)的狀態(tài)。比如，頁表，頁目錄等。
• 核心數(shù)據(jù)存儲（Core Data Storage）：用來保存數(shù)據(jù)庫中的元組
• 臨時(shí)數(shù)據(jù)結(jié)構(gòu)（Temporary Data Structures）：DBMS在執(zhí)行一些查詢時(shí)，會構(gòu)建一些臨時(shí)的數(shù)據(jù)結(jié)構(gòu)來加快執(zhí)行速度。
• 表索引（Table Indices）：表的輔助數(shù)據(jù)結(jié)構(gòu)，幫助我們更快地找到表中的某些特定數(shù)據(jù)。

當(dāng)我們在DBMS中實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)時(shí)，有兩點(diǎn)需要特別注意：

1. 數(shù)據(jù)組織（Data organization）：我們需要設(shè)計(jì)數(shù)據(jù)在內(nèi)存中的布局，以及數(shù)據(jù)結(jié)構(gòu)中需要保存哪些數(shù)據(jù)來提高訪問效率。
2. 并發(fā)（Concurrency）：我們在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)需要考慮到多個(gè)線程同時(shí)訪問數(shù)據(jù)結(jié)構(gòu)的情況。

2. 哈希表

哈希表是一種抽象數(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ù)級別上的優(yōu)化依然是很有價(jià)值的。

哈希表的實(shí)現(xiàn)主要包括兩部分：

• 哈希函數(shù)（Hashing Function）：哈希函數(shù)是一個(gè)從范圍較大的鍵空間（key space）到范圍較小的值空間（value space）的映射。通常來說，對于給定的鍵，哈希函數(shù)計(jì)算出一個(gè)確定的數(shù)值，這個(gè)數(shù)值指向數(shù)組的位置就是存儲對應(yīng)值的地方。在設(shè)計(jì)哈希函數(shù)的時(shí)候，通常需要在執(zhí)行速度和碰撞率之間做折中。過于復(fù)雜的哈希函數(shù)可能碰撞率比較低，但是執(zhí)行速度可能會比較慢；過于簡單的哈希函數(shù)可能執(zhí)行速度比較快，但是碰撞發(fā)生的概率可能比較高。
• 哈希方案（Hashing Scheme）：哈希方式是處理哈希之后的碰撞問題，碰撞問題是不可避免的。通常來說，對于比較大的哈希表，碰撞發(fā)生的概率是比較低的，所以在碰撞發(fā)生時(shí)不需要執(zhí)行太多復(fù)雜的邏輯。因此我們通常也需要在哈希表的邏輯復(fù)雜度和占用空間之間做一個(gè)折中。

3. 哈希函數(shù)

一般來說，哈希函數(shù)以鍵key作為輸入，輸出一個(gè)確定的整數(shù)值（在這里，確定的意思是只要哈希函數(shù)和哈希函數(shù)的種子不變，每次輸入同一個(gè)鍵key，輸出的都是同一個(gè)整數(shù)）。

對于DBMS來說，使用加密的哈希函數(shù)是沒有必要的，因?yàn)榇蠖鄶?shù)時(shí)候，哈希函數(shù)僅僅在DBMS內(nèi)部使用，并不會暴露給外部系統(tǒng)，因此，DBMS沒有必要保護(hù)鍵key的內(nèi)容。我們僅僅需要考慮哈希函數(shù)的運(yùn)行速度和碰撞率。

4. 靜態(tài)的哈希方案（Static Hashing Schemes）

靜態(tài)的哈希方案要求事先知道我們大約需要對多少keys進(jìn)行哈希。在靜態(tài)哈希方案中，哈希表的大小是固定的。如果哈希表的空間用完，那么我們需要重新構(gòu)建一個(gè)更大的哈希表，這是一個(gè)非常耗時(shí)的操作。新的哈希表的大小一般是原來的兩倍。但是在現(xiàn)實(shí)中，我們事先通常不知道需要存儲的數(shù)據(jù)有多少。

4.1 線性探測哈希（Linear probe hashing）

這是最普遍的哈希方案，一般來說也是最快的。線性探測哈希方式首先申請一大塊內(nèi)存作為環(huán)形數(shù)組。

插入數(shù)據(jù)時(shí)，如果插入位置已經(jīng)被占用，那么就從插入位置向下查找，直到找到一個(gè)空位并將數(shù)據(jù)插入到這個(gè)空位中。如果一直掃描到數(shù)組尾部都沒有空位，那么就從數(shù)組頭部開始向下掃描（我們申請的是邏輯上的環(huán)形數(shù)組）。如果整個(gè)哈希表都滿了，那么就需要重新申請更大的內(nèi)容，然后將所有數(shù)據(jù)重新插入到新的哈希表中。

查找數(shù)據(jù)時(shí)，計(jì)算key對應(yīng)的哈希值，查找數(shù)組對應(yīng)位置的key是否和所需的key相同，如果不同，那么向下掃描直到找到所需的鍵值對（查找成功）或者遇到一個(gè)空位（查找失?。?/p>

刪除數(shù)據(jù)時(shí)，如果僅僅將對應(yīng)位置的鍵值對抹去可能會導(dǎo)致該鍵值對下方的鍵值對在之后的查找中失敗。舉個(gè)例子，首先看圖1，A，C，D經(jīng)過哈希之后的位置分別是數(shù)組的第3，3，4位，經(jīng)過線性探測之后，C插入到第4格，D插入到第5格?，F(xiàn)在如果刪除C，就會出現(xiàn)圖2的情況，這時(shí)，如果我們查找D，哈希值為4，查找對應(yīng)位置是沒有數(shù)據(jù)，此時(shí)就會認(rèn)定D不存在于哈希表中（發(fā)生錯(cuò)誤）。

為了解決這個(gè)問題，在刪除時(shí)有兩種處理方式：

• （常用）在刪除位置設(shè)置墓碑標(biāo)識，標(biāo)識這個(gè)位置已經(jīng)被占用，但是并沒有保存數(shù)據(jù)。在查找的時(shí)候如果發(fā)現(xiàn)墓碑符號就正常向下掃描，插入時(shí)發(fā)現(xiàn)墓碑符號就可以插入。
• （不常用）在刪除鍵值對時(shí)，移動(dòng)當(dāng)前位置之下的鍵值對。這個(gè)方法相對復(fù)雜，計(jì)算當(dāng)前位置之下的鍵值對哈希值，并和其實(shí)際位置做比較，以此決定是否移動(dòng)。

當(dāng)鍵key不唯一時(shí)，即有存在多個(gè)鍵值對，其鍵key相同，但是值不同。這種情況有有兩種處理方式：

• 鏈表：鍵值對中的值不再保存實(shí)際的值，而是保存一個(gè)指針。該指針指向一個(gè)鏈表，在鏈表中保存該鍵對應(yīng)的多個(gè)值。
• 冗余keys：直接在哈希表中保存多個(gè)鍵相同的鍵值對，線性探測哈希的規(guī)則在這種情況下依舊可以正常工作且不會出錯(cuò)。

4.2 羅賓漢哈希（Robin Hood Hashing）

線性探測哈希的變種，羅賓漢是一個(gè)“劫富濟(jì)貧”的強(qiáng)盜，在哈希表，也有這樣一個(gè)“劫富濟(jì)貧”的操作。首先我們定義“貧富”的概念，如果一個(gè)鍵值對的實(shí)際位置和其理想位置（經(jīng)過一次哈希函數(shù)計(jì)算得到的位置）相對比較遠(yuǎn)，那么就是相對“貧窮”的；反之，就是相對“富有”的。

那么“劫富濟(jì)貧”的操作具體是什么呢？首先，每個(gè)鍵值對都需要記錄自己的“貧富”，也就是自己離理想位置的距離。這樣在插入的過程中，如果發(fā)現(xiàn)某一個(gè)位置已經(jīng)被占用，那么就比較當(dāng)前插入鍵值對和占用該位置的鍵值對的貧富程度，如果當(dāng)前插入的鍵值對比較貧窮，也就是離自己的理想位置更遠(yuǎn)，那么就替換占用該位置的鍵值對。

具體的說看下圖：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è)鍵值對離自己的理想位置的距離變得“均衡”了，或許對查詢的平均時(shí)間復(fù)雜度有一定的優(yōu)化，但是一定復(fù)雜化了插入操作的時(shí)間復(fù)雜度。

實(shí)際上，經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，這種方法的效率不如線性探測法，不過這種方法的思想還是很有價(jià)值的。

4.3 布谷時(shí)鐘哈希（Cuckoo Hashing）

布谷鐘擺動(dòng)哈希方式準(zhǔn)備了兩個(gè)哈希表來存儲數(shù)據(jù)，兩個(gè)哈希表一般采用不同種子的哈希函數(shù)，并且提供 O ( 1 ) O(1) O(1)時(shí)間復(fù)雜度的查找和刪除，但是插入操作會比較復(fù)雜。和線性探測不同，布谷時(shí)鐘擺動(dòng)哈希完全不需要掃描，具體來說：

對于查找和刪除操作，在兩個(gè)哈希表上分別運(yùn)行哈希函數(shù)，然后比較鍵值對決定哪一個(gè)是所需的鍵值對。

而對于插入操作，我們依然在兩個(gè)哈希表運(yùn)行哈希函數(shù)，但是情況稍有些復(fù)雜。

• 如果兩個(gè)哈希表上都有空位，那么就隨機(jī)選擇一個(gè)哈希表插入
• 如果只有一個(gè)有空位，那么就插入到有空位的哈希表上
• 如果兩個(gè)哈希表都沒有空位，那么就隨機(jī)選擇一個(gè)哈希表替換其對應(yīng)位置的鍵值對，然后遞歸地插入被替換掉的鍵值對，直到所有鍵值對都插入到哈希表中。

5. 動(dòng)態(tài)哈希方案（Dynamic Hashing Schemes）

靜態(tài)哈希方案都有一個(gè)大前提就是我們事前是知道哈希表需要容納多少鍵值對的，否則如果出現(xiàn)預(yù)設(shè)的容量過大或者過小問題時(shí)，我們對其擴(kuò)容或者縮容的代價(jià)都比較大（可以采用一致性哈希）。

因此，我們?yōu)榱私鉀Q這個(gè)問題，提出了一些動(dòng)態(tài)的哈希方案，即哈希表的運(yùn)行的過程中可以按需增長或者減小。下面介紹三種動(dòng)態(tài)哈希方案：

5.1 鏈?zhǔn)焦＃–hained Hashing）

這是最簡單的動(dòng)態(tài)哈希方案，也是java或者jvm中默認(rèn)的哈希方案。鏈?zhǔn)焦Ｖ校１碇袛?shù)組的成員是buckets的鏈表，因此，當(dāng)發(fā)生沖突時(shí)，將元素添加到對應(yīng)Bucket的末尾即可，如果Bucket已滿，則創(chuàng)建一個(gè)新的Bucket即可。

5.3 線性哈希（Linear Hashing）

線性哈希是可擴(kuò)展哈希的改進(jìn)，可擴(kuò)展哈希有一個(gè)小的性能瓶頸，在bucket分裂且需要擴(kuò)展slot array時(shí)，需要對整個(gè)slot array加鎖直到bucket分裂完成。為了解決這個(gè)問題，提出了線性哈希方式。哈希表維護(hù)一個(gè)指針，指向下一個(gè)準(zhǔn)備分裂的bucket，并且線性哈希采用多個(gè)哈希函數(shù)來尋找正確的bucket。

當(dāng)插入過程中，任何一個(gè)bucket溢出，都將分裂指針指向的bucket（無論這個(gè)bucket是否溢出），舉個(gè)例子，，如下圖。

最初，指針指向第一個(gè)bucket，即當(dāng)任何一個(gè)bucket發(fā)生溢出時(shí)，都分裂第一個(gè)bucket。且現(xiàn)在只有一個(gè)哈希函數(shù)。

現(xiàn)需要插入17，發(fā)現(xiàn)對應(yīng)的bucket已滿，發(fā)生了溢出，因此需要分裂第一個(gè)bucket.

現(xiàn)在將第一個(gè)bucket分裂，就需要增加一個(gè)bucket，那么哈希哈希表中已經(jīng)有了5個(gè)bucket，原來的哈希函數(shù)中的n為4，不能滿足使用要求，需要增加新的哈希函數(shù) h a s h 2 hash_2 hash2?。然后使用新的哈希函數(shù)重新分配第一個(gè)bucket中的元素。

現(xiàn)在我們再來觀察查詢過程，現(xiàn)在需要查詢20，首先使用第一個(gè)哈希函數(shù)，發(fā)現(xiàn)哈希值為0，即第一個(gè)bucket。但是這個(gè)哈希值落在了分裂指針的上面，即我們要查詢的值落在一個(gè)已經(jīng)分裂的bucket上，而這個(gè)bucket中的所有鍵值對已經(jīng)用第二個(gè)哈希函數(shù)重新分配位置，因此，需要用第二個(gè)哈希函數(shù)重新計(jì)算哈希值為4，即第五個(gè)bucket中，然后在這個(gè)bucket中循序查詢即可。

6. 總結(jié)

哈希表是一種速度非?？斓臄?shù)據(jù)結(jié)構(gòu)，支持 O ( 1 ) O(1) O(1)級別的查找速度，哈希表的設(shè)計(jì)主要包括哈希函數(shù)和哈希方案。其中哈希方案包括靜態(tài)方案和動(dòng)態(tài)方案，靜態(tài)方案即哈希表的大小是固定的，動(dòng)態(tài)方案是哈希表的大小可以按需生長或者縮小。雖然對于哈希表有許多改進(jìn)，但是其中速度最快還是最初的線性探測哈希。

哈希表是普遍使用的數(shù)據(jù)結(jié)構(gòu)，有部分?jǐn)?shù)據(jù)庫使用哈希表作為索引（例如memcached），但哈希表并不適合用于索引的構(gòu)建，因?yàn)楣：瘮?shù)查找需要完整的key值，且不支持快速查找大于某個(gè)key的數(shù)據(jù)。實(shí)際上，構(gòu)建索引一般使用B+樹的方式，B+樹是另一種極為優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。
測哈希**。

哈希表是普遍使用的數(shù)據(jù)結(jié)構(gòu)，有部分?jǐn)?shù)據(jù)庫使用哈希表作為索引（例如memcached），但哈希表并不適合用于索引的構(gòu)建，因?yàn)楣：瘮?shù)查找需要完整的key值，且不支持快速查找大于某個(gè)key的數(shù)據(jù)。實(shí)際上，構(gòu)建索引一般使用B+樹的方式，B+樹是另一種極為優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：06-哈希表-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://muchs.cn/article48/ddcphp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、做網(wǎng)站、動(dòng)態(tài)網(wǎng)站、網(wǎng)站制作、外貿(mào)建站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)