redis的hash怎么實現的

redis的hash怎么實現的

0.前言

redis是KV型的內存數據庫, 數據庫存儲的核心就是Hash表, 我們執行select命令選擇一個存儲的db之后, 所有的操作都是以hash表為基礎的, 下面會分析下redis的hash數據結構和實現.

1.hash數據結構

/*Hash表一個節點包含Key,Value數據對?*/ typedef?struct?dictEntry?{ ????void?*key; ????union?{ ????????void?*val; ????????uint64_t?u64; ????????int64_t?s64; ????????double?d; ????}?v; ????struct?dictEntry?*next;?/*?指向下一個節點,?鏈接表的方式解決Hash沖突?*/ }?dictEntry;  /*?存儲不同數據類型對應不同操作的回調函數?*/ typedef?struct?dictType?{ ????unsigned?int?(*hashFunction)(const?void?*key); ????void?*(*keyDup)(void?*privdata,?const?void?*key); ????void?*(*valDup)(void?*privdata,?const?void?*obj); ????int?(*keyCompare)(void?*privdata,?const?void?*key1,?const?void?*key2); ????void?(*keyDestructor)(void?*privdata,?void?*key); ????void?(*valDestructor)(void?*privdata,?void?*obj); }?dictType;  typedef?struct?dictht?{ ????dictEntry?**table;?/*?dictEntry*數組,Hash表?*/ ????unsigned?long?size;?/*?Hash表總大小?*/ ????unsigned?long?sizemask;?/*?計算在table中索引的掩碼,?值是size-1?*/ ????unsigned?long?used;?/*?Hash表已使用的大小?*/ }?dictht;  typedef?struct?dict?{ ????dictType?*type; ????void?*privdata; ????dictht?ht[2];?/*?兩個hash表,rehash時使用*/ ????long?rehashidx;?/*?rehash的索引,?-1表示沒有進行rehash?*/ ????int?iterators;?/*??*/ }?dict;

2.hash數據結構圖

redis的hash怎么實現的

3.漸進式hash說明

dict中ht[2]中有兩個hash表, 我們第一次存儲數據的數據時, ht[0]會創建一個最小為4的hash表, 一旦ht[0]中的size和used相等, 則dict中會在ht[1]創建一個size*2大小的hash表, 此時并不會直接將ht[0]中的數據copy進ht[0]中, 執行的是漸進式rehash, 即在以后的操作(find, set, get等)中慢慢的copy進去, 以后新添加的元素會添加進ht[0], 因此在ht[1]被占滿的時候定能確保ht[0]中所有的數據全部copy到ht[1]中.

4.創建hash表

創建hash表過程非常簡單,直接調用dictCreate函數, 分配一塊內存,初始化中間變量即可.

dict?*dictCreate(dictType?*type,?void?*privDataPtr) { ?????/*分配內存*/ ????dict?*d?=?zmalloc(sizeof(*d)); ?????/*初始化操作*/ ????_dictInit(d,type,privDataPtr); ????return?d; }

5.添加元素

hash表中添加元素,首先判斷空間是否足夠, 然后計算key對應的hash值, 然后將需要添加的key和value放入表中.

int?dictAdd(dict?*d,?void?*key,?void?*val) { ?????/*添加入hash表中,?返回新添加元素的實體結構體*/ ????dictEntry?*entry?=?dictAddRaw(d,key);  ????if?(!entry)?return?DICT_ERR; ?????/*元素val值放入元素實體結構中*/ ????dictSetVal(d,?entry,?val); ????return?DICT_OK; } /* *添加元素實體函數 */ dictEntry?*dictAddRaw(dict?*d,?void?*key) { ????int?index; ????dictEntry?*entry; ????dictht?*ht;  ????if?(dictIsRehashing(d))?_dictRehashStep(d);  ????/*根據key值計算新元素在hash表中的索引,?返回-1則表示元素已存在,?直接返回NULL*/ ????if?((index?=?_dictKeyIndex(d,?key))?==?-1) ????????return?NULL;  ????/*如果在進行rehash過程,則新元素添加到ht[1]中,?否則添加到ht[0]中?*/ ????ht?=?dictIsRehashing(d)???&d->ht[1]?:?&d->ht[0]; ????entry?=?zmalloc(sizeof(*entry)); ????entry->next?=?ht->table[index]; ????ht->table[index]?=?entry; ????ht->used++;  ????/*設置元素key*/ ????dictSetKey(d,?entry,?key); ????return?entry; } /* *計算索引的函數 */ static?int?_dictKeyIndex(dict?*d,?const?void?*key) { ????unsigned?int?h,?idx,?table; ????dictEntry?*he;  ????/*?判斷hash表是否空間足夠,?不足則需要擴展?*/ ????if?(_dictExpandIfNeeded(d)?==?DICT_ERR) ????????return?-1; ????????? ????/*?計算key對應的hash值?*/ ????h?=?dictHashKey(d,?key); ????for?(table?=?0;?table?ht[table].sizemask; ????????/*遍歷沖突列表,?判斷需要查找的key是否已經在沖突列表中*/ ????????he?=?d->ht[table].table[idx]; ????????while(he)?{ ????????????if?(dictCompareKeys(d,?key,?he->key)) ????????????????return?-1; ????????????he?=?he->next; ????????} ????????if?(!dictIsRehashing(d))?break; ????} ????return?idx; } /* *判斷hash表是否需要擴展空間 */ static?int?_dictExpandIfNeeded(dict?*d) { ????/*redis的rehash采用的漸進式hash,?rehash時分配了原來兩倍的內存空間,?在rehash階段空間必定夠用*/ ????if?(dictIsRehashing(d))?return?DICT_OK;  ????/*?hash表是空的需要初始化空間,?默認是4*/ ????if?(d->ht[0].size?==?0)?return?dictExpand(d,?DICT_HT_INITIAL_SIZE);  ????/*?已使用空間滿足不了設置的條件*/ ????if?(d->ht[0].used?>=?d->ht[0].size?&& ????????(dict_can_resize?|| ?????????d->ht[0].used/d->ht[0].size?>?dict_force_resize_ratio)) ????{ ??????????/*擴展空間,?使用空間的兩倍*/ ????????return?dictExpand(d,?d->ht[0].used*2); ????} ????return?DICT_OK; }  /* *擴展空間或者初始化hash表空間 */ int?dictExpand(dict?*d,?unsigned?long?size) { ????dictht?n; ?????/*?對需要分配大小圓整為2的倍數?*/ ????unsigned?long?realsize?=?_dictNextPower(size);  ????/*?如果空間足夠則表明調用錯誤?*/ ????if?(dictIsRehashing(d)?||?d->ht[0].used?>?size) ????????return?DICT_ERR;  ????n.size?=?realsize; ????n.sizemask?=?realsize-1; ????n.table?=?zcalloc(realsize*sizeof(dictEntry*)); ????n.used?=?0; ???? ?????/*hash表為空初始化hash表*/ ????if?(d->ht[0].table?==?NULL)?{ ????????d->ht[0]?=?n; ????????return?DICT_OK; ????}  ????/*新分配的空間放入ht[1],?后面一步一步進行rehash*/ ????d->ht[1]?=?n; ????d->rehashidx?=?0; ????return?DICT_OK; }

6.查找元素

查找元素過程,首先計算hash值, 然后計算在ht[0]和ht[1]中索引位置, 進行查找.

dictEntry?*dictFind(dict?*d,?const?void?*key) { ????dictEntry?*he; ????unsigned?int?h,?idx,?table;  ????if?(d->ht[0].size?==?0)?return?NULL; ???? ?????/*如果正在進行rehash,?執行一次rehash*/ ????if?(dictIsRehashing(d))?_dictRehashStep(d); ???? ????h?=?dictHashKey(d,?key); ???? ?????/*由于可能正在rehash,?因此要從ht[0]和ht[1]中分別進行查找,?找不到返回NULL*/ ????for?(table?=?0;?table?ht[table].sizemask; ????????he?=?d->ht[table].table[idx]; ??????????/*遍歷沖突列表查找元素*/ ????????while(he)?{ ????????????if?(dictCompareKeys(d,?key,?he->key)) ????????????????return?he; ????????????he?=?he->next; ????????} ????????if?(!dictIsRehashing(d))?return?NULL; ????} ????return?NULL; }

7.刪除元素

刪除元素首先查找元素, 然后將元素從hash表中移除即可, 調用dictDelete刪除元素, 會同時刪除元素所占空間

int?dictDelete(dict?*ht,?const?void?*key)?{ ????return?dictGenericDelete(ht,key,0); }  static?int?dictGenericDelete(dict?*d,?const?void?*key,?int?nofree) { ????unsigned?int?h,?idx; ????dictEntry?*he,?*prevHe; ????int?table;  ????if?(d->ht[0].size?==?0)?return?DICT_ERR; ???? ????if?(dictIsRehashing(d))?_dictRehashStep(d); ????h?=?dictHashKey(d,?key);  ????for?(table?=?0;?table?ht[table].sizemask; ????????he?=?d->ht[table].table[idx]; ????????prevHe?=?NULL; ??????????/*查找元素到元素,進行刪除操作,?并釋放占用的內存*/ ????????while(he)?{ ????????????if?(dictCompareKeys(d,?key,?he->key))?{ ????????????????/*?Unlink?the?element?from?the?list?*/ ????????????????if?(prevHe) ????????????????????prevHe->next?=?he->next; ????????????????else ????????????????????d->ht[table].table[idx]?=?he->next; ????????????????if?(!nofree)?{ ????????????????????dictFreeKey(d,?he); ????????????????????dictFreeVal(d,?he); ????????????????} ????????????????zfree(he); ????????????????d->ht[table].used--; ????????????????return?DICT_OK; ????????????} ????????????prevHe?=?he; ????????????he?=?he->next; ????????} ????????if?(!dictIsRehashing(d))?break; ????} ????return?DICT_ERR;?/*?not?found?*/ }

hash命令

hash命令操作都比較簡單,需要注意的是當我們創建hash表示默認存儲結構,并不是dict,而是ziplist結構,可以參考redis之Ziplist數據結構,hash_max_ziplist_entries和hash_max_ziplist_value值作為閥值,hash_max_ziplist_entries表示一旦ziplist中元素數量超過該值,則需要轉換為dict結構;hash_max_ziplist_value表示一旦ziplist中數據長度大于該值,則需要轉換為dict結構。

更多Redis相關技術文章,請訪問redis之Ziplist數據結構欄目進行學習!

? 版權聲明
THE END
喜歡就支持一下吧
點贊14 分享