redis的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;

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

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; }

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; }

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?*/ }