哈希表的實(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è)元素，包含鍵值對。用于鏈接法散列。是鏈接法散列中的鏈表部分。具體的第一個(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表里面都會有這個(gè)數(shù)據(jù)結(jié)構(gòu)，對每個(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ù)組，還有存儲hash表的大小，大小掩碼，使用個(gè)數(shù)?？梢哉J(rèn)為是一個(gè)數(shù)組的擴(kuò)展。方便管理的數(shù)組。

typedef struct dict {
        dictType *type;//定義了對于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;

• 對于兩個(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í)候是安全的，可以對于hash表進(jìn)行刪除插入操作。否則只能讀取hash表

static void _dictReset(dictht *ht)

• 對于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ù)對于管理兩個(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的大小，動態(tài)分配內(nèi)存。
• 創(chuàng)建hash表：table存儲的是hash元素值的指針，在這個(gè)時(shí)候會給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]來對這兩個(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)存了，就會給另一張表分配內(nèi)存。并不會覆蓋原來有值的hash表。

int dictRehash(dict *d, int n)

• 重新hash，就是把hashtable[0]（ht[0]）里面的所有的鍵重新hash一下，然后把鍵值存儲在hashtable1里面，并且hashtable[0]還指向重新hash后的hash表。

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

• 具體的過程是這樣的：

• 首先在hashtable[0]里面找到所有非空的鍵值對（數(shù)組中查找到鏈表頭節(jié)點(diǎn)（頭指針）），然后對這個(gè)查找到的鏈表進(jìn)行遍歷，鏈表中的每一個(gè)元素都是鍵值對。根據(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的過程是否完成。會進(jìn)行一些列的釋放資源的操作，比如釋放hashtable[0]的內(nèi)存，使得hashtable[1]和hashtable[0]指針互換。重置hashtable[1]

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

• 回過頭來看看，rehash的過程是把一個(gè)hash表中所有元素拿出來之后，按著某種方式對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的大小。移動元素的個(gè)數(shù)。考慮到rehash執(zhí)行的時(shí)間對于其他請求的影響。

static void _dictRehashStep(dict *d)

• 當(dāng)沒有迭代器的時(shí)候會每次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è)位置上?？隙〞幸粋€(gè)index，其次如果這個(gè)index指向的鏈表中
• 如果鏈表為空，那么返回hash碼，否則需要遍歷這個(gè)鏈表查看是否存在與key對應(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ù)會首先調(diào)用_dictKeyIndex查找到應(yīng)該在的index，當(dāng)然也可能會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)

• 添加對key,value對到hashtable中，向字典中添加元素。
• 會調(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í)體，并返回地址。找不到就會返回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è)鍵對于的字典實(shí)體，進(jìn)而獲得字典值。

dictIterator *dictGetIterator(dict *d)

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

dictIterator *dictGetSafeIterator(dict *d)

• 獲得安全的迭代器版本，可以對整個(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í)候需要判斷,是否為安全的迭代器，如果是增加指紋信息（我猜測可能是為了后面進(jìn)行通過迭代器進(jìn)行修改字典進(jìn)行的驗(yàn)證），并且需要增加迭代器的引用個(gè)數(shù)。
• 判斷一個(gè)表是否遍歷完了。如果這個(gè)表遍歷完了（通過index和桶的大?。⑶艺谶M(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è)鍵值對。
• 隨機(jī)找到一個(gè)索引，并且隨機(jī)獲得這個(gè)索引指向的鏈表中的一個(gè)元素。