哈希表的實(shí)現(xiàn)

• 哈希表可以認(rèn)為是redis最為重要的一個(gè)數(shù)據(jù)結(jié)構(gòu)
• 實(shí)現(xiàn)了key,value的查找膛檀，保存所有的key等

1.基本數(shù)據(jù)結(jié)構(gòu)

typedef struct dictEntry {
    void *key;// 鍵
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值(可以有幾種不同類型)
    struct dictEntry *next;// 指向下一個(gè)哈希節(jié)點(diǎn)(形成鏈表)
} dictEntry;

• 這個(gè)數(shù)據(jù)結(jié)構(gòu)可以認(rèn)為是hash表的一個(gè)元素芹缔，包含鍵值對(duì)枢步。用于鏈接法散列。是鏈接法散列中的鏈表部分祝峻。具體的第一個(gè)key,value 可以是聯(lián)合體里面的幾種類型
  最后一個(gè)是指向具有相同hash值的元素枯夜。

typedef struct dictType {
        unsigned int (*hashFunction)(const void *key);//哈希計(jì)算方法，返回整形變量
        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);//key的析構(gòu)函數(shù)
        void (*valDestructor)(void *privdata, void *obj);//val的析構(gòu)函數(shù)
} dictType;

• 這個(gè)數(shù)據(jù)結(jié)構(gòu)定義了一些在hash表上的一系列操作祷愉，結(jié)構(gòu)體里面都是函數(shù)指針窗宦，每個(gè)hash表里面都會(huì)有這個(gè)數(shù)據(jù)結(jié)構(gòu)，對(duì)每個(gè)hash表進(jìn)行操作二鳄。

typedef struct dictht {
        dictEntry **table;//字典實(shí)體赴涵，使用的是數(shù)組形式，方便查找key
        unsigned long size;//字典大小
        unsigned long sizemask;//字典掩碼订讼，為size-1
        unsigned long used;//這個(gè)字典表中（數(shù)組中）髓窜，被使用的個(gè)數(shù)
} dictht;

• 定義了hash表的形式，使用一個(gè)保存hash表元素地址的一個(gè)數(shù)組欺殿，還有存儲(chǔ)hash表的大小寄纵，大小掩碼，使用個(gè)數(shù)脖苏〕淌茫可以認(rèn)為是一個(gè)數(shù)組的擴(kuò)展。方便管理的數(shù)組棍潘。

typedef struct dict {
        dictType *type;//定義了對(duì)于hash表操作的一些列函數(shù)
        void *privdata;//私有的數(shù)據(jù)
        dictht ht[2];//兩個(gè)hash表恃鞋，一個(gè)新的一個(gè)舊的，可以在必要的時(shí)候進(jìn)行hash表的擴(kuò)張蜒谤，和hash表的rehash山宾。
        long rehashidx; /* rehashing not in progress if rehashidx == -1 *///rehash的標(biāo)志-1表示沒在rehash，可以根據(jù)這個(gè)值來取得兩張hash表哪個(gè)可以使用鳍徽。
        int iterators; /* number of iterators currently running *///這個(gè)hash表上迭代器的個(gè)數(shù)
} dict;

• 對(duì)于兩個(gè)hash表的管理數(shù)據(jù)結(jié)構(gòu)资锰，所有的操作都是通過這個(gè)數(shù)據(jù)結(jié)構(gòu)來進(jìn)行的。包含hash元素的添加阶祭，刪除绷杜，查找直秆，擴(kuò)張，rehash鞭盟。

typedef struct dictIterator {
        dict *d;//管理hash表的數(shù)據(jù)機(jī)構(gòu)
        long index;//索引
        int table, safe;//表和安全性標(biāo)志
        dictEntry *entry, *nextEntry;//當(dāng)前元素和下一個(gè)元素
        /* unsafe iterator fingerprint for misuse detection. */
        long long fingerprint;//指紋
} dictIterator;

• hash表上面的迭代器圾结，可以通過迭代器來訪問hash表中的元素。當(dāng)safe=1時(shí)候是安全的齿诉，可以對(duì)于hash表進(jìn)行刪除插入操作筝野。否則只能讀取hash表

static void _dictReset(dictht *ht)

• 對(duì)于hash表進(jìn)行空的初始化，把hash表中的組數(shù)粤剧，大小都設(shè)置為默認(rèn)值歇竟。

dict *dictCreate(dictType *type, void *privDataPtr)

• 創(chuàng)建一個(gè)管理hash表的數(shù)據(jù)結(jié)構(gòu)，首先分配內(nèi)存抵恋，設(shè)置管理hash表數(shù)據(jù)結(jié)構(gòu)的hash類型焕议，私有數(shù)據(jù)佛猛，迭代器舶胀，最為主要的是初始化兩張hash表。
  這樣兩張hash表就創(chuàng)建成功了冬骚，但是現(xiàn)在里面并沒有任何元素世囊，也可以說這兩張表（兩個(gè)數(shù)組）內(nèi)容是hash元素指針别瞭，兩個(gè)數(shù)組里面并沒有開始分配內(nèi)存，只有數(shù)組名茸习。
• 正真進(jìn)行分配內(nèi)存的時(shí)候（給dictht的table分配內(nèi)存）是在dict的擴(kuò)張時(shí)候畜隶。見下面的函數(shù)int dictExpand(dict *d, unsigned long size)

int _dictInit(dict *d, dictType *type,void *privDataPtr)

-根據(jù)參數(shù)對(duì)于管理兩個(gè)hash表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化，設(shè)置

int dictExpand(dict *d, unsigned long size)

• 創(chuàng)建或者擴(kuò)張hash表号胚，其中size為hash表的大小籽慢，也就是dictht中table的大小，動(dòng)態(tài)分配內(nèi)存猫胁。
• 創(chuàng)建hash表：table存儲(chǔ)的是hash元素值的指針箱亿，在這個(gè)時(shí)候會(huì)給table分配內(nèi)存，分配內(nèi)存的大小是大于size的2的指數(shù)倍弃秆。給的size大小需要檢查届惋，不能超過long_max值。同時(shí)這個(gè)值還不能和當(dāng)前hash表的大小一致菠赚，這樣沒什么意義脑豹。
• 分配好table的大小之后，就可以把它賦值給管理hash表的數(shù)據(jù)結(jié)構(gòu)了衡查。管理數(shù)據(jù)結(jié)構(gòu)dict通過ht[2]來對(duì)這兩個(gè)hash表進(jìn)行管理瘩欺。
• 這樣就給兩個(gè)hash表分配的內(nèi)存，其實(shí)這兩個(gè)hash表的指針是指向同一快內(nèi)存的。這只是在創(chuàng)建的時(shí)候兩張hash表是同一塊內(nèi)存俱饿。ht[0]=ht[1] if (ht[0].table=null)
• Expend過程：上面的創(chuàng)建過程給兩張表指針指向同一塊內(nèi)存歌粥，其實(shí)如果兩個(gè)hash表已經(jīng)初始化了之后，就可以達(dá)到擴(kuò)展的過程拍埠。ht[0].table=ht[1].table if (ht[0].table=null)
• 這語句的意思就是在擴(kuò)張的時(shí)候一個(gè)hash表已經(jīng)分配內(nèi)存了失驶，就會(huì)給另一張表分配內(nèi)存。并不會(huì)覆蓋原來有值的hash表枣购。

int dictRehash(dict *d, int n)

• 重新hash嬉探，就是把hashtable[0]（ht[0]）里面的所有的鍵重新hash一下，然后把鍵值存儲(chǔ)在hashtable1里面坷虑，并且hashtable[0]還指向重新hash后的hash表甲馋。

• 整個(gè)表都rehash完成后返回0，部分rehash返回1迄损。

• 具體的過程是這樣的：

• 首先在hashtable[0]里面找到所有非空的鍵值對(duì)（數(shù)組中查找到鏈表頭節(jié)點(diǎn)（頭指針）），然后對(duì)這個(gè)查找到的鏈表進(jìn)行遍歷账磺，鏈表中的每一個(gè)元素都是鍵值對(duì)芹敌。根據(jù)鏈表節(jié)點(diǎn)中的鍵key，找到在hashtable[1]數(shù)組中的索引位置垮抗，然后插入到這個(gè)索引所在的鏈表的表頭氏捞。

• 這樣就可以完成一個(gè)字典實(shí)體的轉(zhuǎn)換，一只把整個(gè)鏈表遍歷完畢冒版。然后在把hashtable[0]數(shù)組中的所有非空元素都遍歷完畢液茎。
  最后實(shí)現(xiàn)了，hashtable[0]里面的所有元素辞嗡，轉(zhuǎn)換為hashtable[1]中的所有元素捆等。- 實(shí)現(xiàn)rehash的過程。注意每次最多遍歷n*10個(gè)元素续室。

• 結(jié)束了上面的兩重遍歷之后栋烤，就可以檢查是否完成整個(gè)rehash的過程是否完成。會(huì)進(jìn)行一些列的釋放資源的操作挺狰，比如釋放hashtable[0]的內(nèi)存明郭，使得hashtable[1]和hashtable[0]指針互換。重置hashtable[1]

• 從這里也可以看出來丰泊，主要的hash表還是hashtable[0],hashtable[1]只是起到了中間作用薯定。還有一點(diǎn)就是可能會(huì)存在部分rehash的過程⊥海可以把部分rehash的內(nèi)容话侄，存放在另一個(gè)臨時(shí)的hash表中。

• 回過頭來看看苛败，rehash的過程是把一個(gè)hash表中所有元素拿出來之后满葛，按著某種方式對(duì)key進(jìn)行重新hash然后存放在其他的表中径簿。

long long timeInMilliseconds(void)

• 獲取當(dāng)前時(shí)間的毫秒數(shù)，使用到了gettimeofday函數(shù)

int dictRehashMilliseconds(dict *d, int ms)

• 在ms毫秒之間進(jìn)行hash,也就是說控制rehash的時(shí)間超過ms毫秒嘀韧。只要rehash時(shí)間沒有超過ms毫秒篇亭，那么增加rehash的參數(shù)n大小，每次增加100锄贷，知道所有rehash時(shí)間超過ms毫秒.
• 這是一種怎樣的控制啊译蒂，強(qiáng)制要求rehash超過一定的時(shí)間，我覺著可能是為了控制rehash的大小谊却。移動(dòng)元素的個(gè)數(shù)柔昼。考慮到rehash執(zhí)行的時(shí)間對(duì)于其他請(qǐng)求的影響炎辨。

static void _dictRehashStep(dict *d)

• 當(dāng)沒有迭代器的時(shí)候會(huì)每次rehash10個(gè)元素(調(diào)用dictRehash(dict, 1) )捕透，逐漸的把hashtable[0]里面的元素遷移到hashtable[1]中。什么時(shí)候能夠知道完全rehash完畢呢碴萧？ 根據(jù)dictRehash函數(shù)的返回值乙嘀。

static int _dictKeyIndex(dict *d, const void *key)

• 查找key所在hashtable（[0],[1]）中的index，key存在返回所在數(shù)組的index破喻，否則返回-1虎谢。
• 先根據(jù)key和整個(gè)hash表的hash計(jì)算方法，計(jì)算出key的hash碼曹质，也就是在hashtable中的索引婴噩，其實(shí)是這個(gè)key應(yīng)該在哪個(gè)位置上∮鸬拢肯定會(huì)有一個(gè)index几莽，其次如果這個(gè)index指向的鏈表中
• 如果鏈表為空，那么返回hash碼玩般，否則需要遍歷這個(gè)鏈表查看是否存在與key對(duì)應(yīng)的元素银觅。最后如果正在rehash,或者rehash 并沒有完成(部分rehash)，那么就需要坏为，把兩個(gè)表都遍歷究驴，否則只查找一個(gè)表（hashtable[0]）

dictEntry *dictAddRaw(dict *d, void *key)

• 添加只有key的字典元素到hashtable中，并返回可以設(shè)置value的字典元素指針匀伏。后來需要調(diào)用setvalue函數(shù)來進(jìn)行value的設(shè)置洒忧。
  這個(gè)函數(shù)會(huì)首先調(diào)用_dictKeyIndex查找到應(yīng)該在的index，當(dāng)然也可能會(huì)key已經(jīng)存在了够颠。然后根據(jù)是否部分rehash,來決定index是在哪一個(gè)表中熙侍。hashtable[0] or hashtable[1]
• 然后創(chuàng)建字典元素實(shí)體，并設(shè)置key值，放在hashtable中蛉抓。

int dictAdd(dict *d, void *key, void *val)

• 添加對(duì)key,value對(duì)到hashtable中庆尘，向字典中添加元素。
• 會(huì)調(diào)用dictAddRaw添加元素的key
• 然后調(diào)用dictSetVal設(shè)置key在hashtable中的實(shí)體的value值巷送。

dictEntry *dictFind(dict *d, const void *key)

• 查找key所在的字典實(shí)體驶忌，返回字典實(shí)體的指針
• 這個(gè)查找的過程和_dictKeyIndex類似，只是這里面要查找到具體的字典實(shí)體所在的內(nèi)存地址
• 首先遍歷兩個(gè)hashtable(數(shù)組)笑跛，找到頭節(jié)點(diǎn)付魔，接著遍歷鏈表，找到和key相同的字典實(shí)體飞蹂，并返回地址几苍。找不到就會(huì)返回NULL

int dictReplace(dict *d, void *key, void *val)

• 調(diào)用dictFind找到字典實(shí)體，調(diào)用dictSetVal設(shè)置字典的新值陈哑，然后釋放原來字典元素的內(nèi)容妻坝。

dictEntry *dictReplaceRaw(dict *d, void *key)

• 查找key,如果存在則添加key，不存在怎返回NULL

static int dictGenericDelete(dict *d, const void *key, int nofree)

• 查找并刪除一個(gè)key元素芥颈，
• 根據(jù)兩張hashtable來進(jìn)行查找惠勒，找到一個(gè)頭節(jié)點(diǎn)之后，進(jìn)行遍歷爬坑，知道找到key的值所在的字典，如果沒有找到返回error涂臣，找到了之后進(jìn)行刪除并釋放內(nèi)存盾计，返回ok

int dictDeleteNoFree(dict *ht, const void *key)

• 調(diào)用dictGenericDelete（ht,key,1）刪除值，但是并不釋放內(nèi)存赁遗。

int dictDelete(dict *ht, const void *key)

• 調(diào)用dictGenericDelete（ht,key,0）刪除值署辉，并釋放內(nèi)存。

int _dictClear(dict *d, dictht *ht, void(callback)(void *))

• 清除指定的ht整個(gè)字典內(nèi)容并岩四，釋放內(nèi)存哭尝。

void dictRelease(dict *d)

• 調(diào)用_dictClear(d,&d->ht[0],NULL)調(diào)用_dictClear(d,&d->ht[1],NULL),分別釋放兩個(gè)hashtable

void *dictFetchValue(dict *d, const void *key)

• 首先調(diào)用dictFind,然后獲得這個(gè)鍵對(duì)于的字典實(shí)體，進(jìn)而獲得字典值剖煌。

dictIterator *dictGetIterator(dict *d)

• 創(chuàng)建dictIterator實(shí)體材鹦，并把內(nèi)容迭代的指針指向dict d。獲得的是不安全的迭代器耕姊，只能通過這個(gè)迭代器讀取字典桶唐，不能寫操作。

dictIterator *dictGetSafeIterator(dict *d)

• 獲得安全的迭代器版本茉兰，可以對(duì)整個(gè)字典進(jìn)行讀寫操作尤泽。

dictEntry *dictNext(dictIterator *iter)

• 獲得下一個(gè)字典元素指針。
• 具體的操作：
• 1.next不為空的時(shí)候直接返回next的內(nèi)容，這個(gè)時(shí)候迭代器里面保存了當(dāng)前hashtable的索引值坯约，所以可以熊咽，等到把這個(gè)鏈表遍歷完了，就可增加索引index的值闹丐，按著往數(shù)組后面開始遍歷另一個(gè)鏈表
• 2.next為空的時(shí)候横殴，這個(gè)時(shí)候需要判斷,是否為安全的迭代器，如果是增加指紋信息（我猜測(cè)可能是為了后面進(jìn)行通過迭代器進(jìn)行修改字典進(jìn)行的驗(yàn)證）妇智，并且需要增加迭代器的引用個(gè)數(shù)滥玷。
• 判斷一個(gè)表是否遍歷完了。如果這個(gè)表遍歷完了（通過index和桶的大形±狻）惑畴，并且正在進(jìn)行rehash那么就需要切換到另一個(gè)hashtable中進(jìn)行依次從數(shù)組的開始0進(jìn)行遍歷。

void dictReleaseIterator(dictIterator *iter)

• 釋放迭代器
• 如果為安全版本的迭代器航徙，需要減少字典迭代器上面的引用如贷，否則需要驗(yàn)證是否為當(dāng)前字典的指紋信息。

dictEntry *dictGetRandomKey(dict *d)

• 隨機(jī)獲得字典中的一個(gè)鍵值對(duì)到踏。
• 隨機(jī)找到一個(gè)索引杠袱，并且隨機(jī)獲得這個(gè)索引指向的鏈表中的一個(gè)元素。