首頁>技術>

字典是一種用於儲存鍵值對的抽象資料結構,也被稱為查詢表、對映或關聯表。

在字典中,一個鍵(key)可以和一個值(value)進行關聯,這些關聯的鍵和值就稱之為鍵值對。

抽象資料結構,啥意思?就是可以需要實際的資料結構是實現這個功能。抽象,意味著它這是實現功能的標準,凡是能夠完成這些功能的都可以是其實現。

redis的字典

字典作為一種資料結構內建在很多高階程式語言裡面,但是redis是基於C語言進行開發的,所以沒有內建這種資料結構,redis只能構建自己的字典實現。

字典通常可以由兩種底層資料結構組成,分別是線性表(陣列)和hash表。而redis一般是採用hash表的方式進行構建

redis字典為啥不用線性表實現

字典基於用線性表實現,如果我這個字典有200個鍵值對,那麼我就開闢一個長度為200的陣列對這些元素進行放置。

基於線性表實現的字典的優缺點很明顯:

1、實現簡單,適用於任意關鍵碼型別。

2、平均檢索效率低(線性時間),表長度n比較大時,檢索比較耗時。

雜湊如何實現字典

之前寫過一篇文章,關於java中的hashcode解析,有興趣的讀者可以回看下一些經典的hash函式和實現

面試官問我:hashcode 是什麼?和equals是兄弟嗎?

redis字典所使用的雜湊表由dict.h/dictht組成

typedef struct dictht {    dictEntry **table;    //雜湊表陣列        unsigned long size;    //雜湊表大小,即雜湊表陣列大小        unsigned long sizemask; //雜湊表大小掩碼,總是等於size-1,主要用於計算索引        unsigned long used;    //已使用節點數,即已使用鍵值對數}dictht;

可以看到redis聲明瞭一個結構體,裡面由一個雜湊表陣列,雜湊表陣列大小的long值,一個用於計算索引的雜湊表大小掩碼以及已使用的節點數構成。

這個雜湊表陣列,存放的是雜湊節點dicEntry,我們會將key-value鍵值對給它放進去。

typedef struct dictEntry {    void *key;  //存放key值    union {        void *val;    //存放value值        uint64_t u64;    //uint64_t整數        int64_t s64;    //int64_t整數    }v;    struct dictEntry *next;    //指向下個雜湊表節點,形成連結串列}dictEntry;

如圖所示就透過next指標來將兩個索引相同的鍵k1和k0連線在一起。

Redis 中的字典由 dict.h/dict 結構表示:

typedef struct dict {    // 型別特定函式    dictType *type;    // 私有資料    void *privdata;    // 雜湊表    dictht ht[2];    // rehash 索引    // 當 rehash 不在進行時,值為 -1    int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;

可以看到字典裡有一個長度為2的雜湊表陣列,那麼為啥不是三個四個甚至更多呢?感覺雜湊表越多不是效率更快嗎?

其實設定2的原因在於,h[0]用於儲存,h[1]用於當容量不足時進行擴充,更多的雜湊表也用不上,反而可能在擴充時要同步成為效能瓶頸。

字典如何增添一個元素

當要將一個新的鍵值對加入到字典中的時候,首先要計算這個key的雜湊值和索引值,然後再根據這個索引值放入字典中h[0]的索引位置

舉個例子, 對於圖 4-4 所示的字典來說, 如果我們要將一個鍵值對 k0 和 v0 新增到字典裡面, 那麼程式會先使用語句:

hash = dict->type->hashFunction(k0);

計算鍵 k0 的雜湊值。

假設計算得出的雜湊值為 8 , 那麼程式會繼續使用語句:

index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

計算出鍵 k0 的索引值 0 , 這表示包含鍵值對 k0 和 v0 的節點應該被放置到雜湊表陣列的索引 0 位置上, 如圖 所示。

什麼時候會進行擴容

按照java中hashmap的說法,當負載因子loadFactor>0.75的情況下會進行擴容

在redis中,字典裡的雜湊會根據以下兩種情況進行擴容:

伺服器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令, 並且雜湊表的負載因子大於等於 1 ;伺服器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令, 並且雜湊表的負載因子大於等於 5 ;

其中雜湊表的負載因子可以透過公式:

# 負載因子 = 雜湊表已儲存節點數量 / 雜湊表大小load_factor = ht[0].used / ht[0].size
漸進式rehash如何實現

首先要清楚為什麼rehash的時候要漸進式。

這就好比去參加高考,肯定是初中畢業後讀三年高中,一點點學習高中知識後才可以參加高考,這才可以取得不錯的成績。學習是循序漸進的,hash也要,不然中考完直接去參加高考,這誰頂得住啊。

Rehash操作分為兩種:

擴充套件:當負載因子較大時,應該擴大 dictht::size 以降低平均長度,加快查詢速度。收縮:當負載因子較小時,應該減小 dictht::size 以減少對記憶體的浪費。

當整體的資料量比較少,如百八十個key-value對儲存的時候,hash的過程肯定耗時不會很多。但是在生產換鏡下,一個數據庫下key-value值都是有百萬級別的,在進行rehash操作的時候勢必會達到秒級別的運算。所以這個hash的過程不是一次性集中的完成,而是分多次漸進式的完成。

以下是雜湊表漸進式 rehash 的詳細步驟:

為 ht[1] 分配空間, 讓字典同時持有 ht[0] 和 ht[1] 兩個雜湊表。在字典中維持一個索引計數器變數 rehashidx , 並將它的值設定為 0 , 表示 rehash 工作正式開始。在 rehash 進行期間, 每次對字典執行新增、刪除、查詢或者更新操作時, 程式除了執行指定的操作以外, 還會順帶將 ht[0] 雜湊表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] , 當 rehash 工作完成之後, 程式將 rehashidx 屬性的值增1。隨著字典操作的不斷執行, 最終在某個時間點上, ht[0] 的所有鍵值對都會被 rehash 至 ht[1] , 這時程式將 rehashidx 屬性的值設為 -1 , 表示 rehash 操作已完成。rehash的過程中有資料變化怎麼辦

關於字典的操作無非就是四個,增刪改查。

這樣就能保證redis在h[0]上是隻少不多,所有的記錄都會被遷移到h[1]上。

如何解決雜湊碰撞

這個問題還是我面試騰訊的時候面試官問我的原題。

一開始我說了兩個思路,一個是無限增大線性表的容量,一個是採用陣列+連結串列的方式。

面試官:對這兩個都是構成hash的方式,但是如果我的兩個鍵值對的hashcode是一樣的呢?

我:那就可以將這個hash演算法設計的複雜化,比如hash裡頭再巢狀一層hash,這樣碰撞的機率就會變小了。

面試官:這種方法其實也是可以的,那還有沒有其他方法呢?

我:....(支支吾吾中)

然後面試就結束了orz

其實還有另一種方法我不知道就是公共溢位區法

建立一個公共溢位區,假設雜湊函式的值域為[0,m-1],則設向量HashTable[0..m-1]為基本表,另外設立儲存空間向量OverTable[0..v]用以儲存發生衝突的記錄。

18
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • 五分鐘快速掌握Maven的核心概念