本文根據(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ù)。比如:
當(dāng)我們在DBMS中實現(xiàn)數(shù)據(jù)結(jié)構(gòu)時,有兩點需要特別注意:
哈希表是一種抽象數(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ù)以鍵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ā)生錯誤)。
為了解決這個問題,在刪除時有兩種處理方式:
當(dāng)鍵key不唯一時,即有存在多個鍵值對,其鍵key相同,但是值不同。這種情況有有兩種處理方式:
線性探測哈希的變種,羅賓漢是一個“劫富濟貧”的強盜,在哈希表,也有這樣一個“劫富濟貧”的操作。首先我們定義“貧富”的概念,如果一個鍵值對的實際位置和其理想位置(經(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ù)雜。
靜態(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)焦V?,哈希表中?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://m.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)
猜你還喜歡下面的內(nèi)容