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

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

DBMS需要使用各種各樣的數(shù)據(jù)結(jié)構(gòu)來維護系統(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ù)據(jù)結(jié)構(gòu)（Temporary Data Structures）：DBMS在執(zhí)行一些查詢時，會構(gòu)建一些臨時的數(shù)據(jù)結(jié)構(gòu)來加快執(zhí)行速度。
• 表索引（Table Indices）：表的輔助數(shù)據(jù)結(jié)構(gòu)，幫助我們更快地找到表中的某些特定數(shù)據(jù)。

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

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

2. 哈希表

哈希表是一種抽象數(shù)據(jù)類型，它使用哈希函數(shù)將數(shù)據(jù)從鍵空間（key space）映射到值空間（value space）。在哈希表上做增刪改查等操作的平均時間復(fù)雜度是 O ( 1 ) O(1) O(1)（最差的情況是 O ( n ) O(n) O(n)），空間復(fù)雜度是 O ( n ) O(n) O(n)。值得注意的是，即使哈希操作的平均時間復(fù)雜度已經(jīng)達到了 O ( 1 ) O(1) O(1)，在這個常數(shù)級別上的優(yōu)化依然是很有價值的。

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

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

3. 哈希函數(shù)

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

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

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

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

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

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

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

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

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

為了解決這個問題，在刪除時有兩種處理方式：

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

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

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

4.2 羅賓漢哈希（Robin Hood Hashing）

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

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

具體的說看下圖：A，C，D已經(jīng)占用了3個空間，此時，E計算的哈希值為3，但是插入位置已經(jīng)被A占據(jù)，那么就比較其貧富程度，發(fā)現(xiàn)，A和E此時一樣富有，不做處理，E繼續(xù)向下尋找，離自己的理想位置距離加1。查找到C，C和E此時里自己的理想位置距離都是1，不做處理，繼續(xù)向下尋找，距離加1。查找到D，發(fā)現(xiàn)D離自己的理想位置距離更近，即D此時比E“富有”，那么就讓E替換D，然后帶著D繼續(xù)向下尋找。D向下查找發(fā)現(xiàn)一個空位，直接插入。

這樣做的好處是什么呢？大的好處就是各個鍵值對離自己的理想位置的距離變得“均衡”了，或許對查詢的平均時間復(fù)雜度有一定的優(yōu)化，但是一定復(fù)雜化了插入操作的時間復(fù)雜度。

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

4.3 布谷時鐘哈希（Cuckoo Hashing）

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

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

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

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

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

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

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

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

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

5.3 線性哈希（Linear Hashing）

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

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

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

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

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

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

6. 總結(jié)

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

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

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

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

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

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

廣告

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