typedef struct dictEntry {//封装键值对

    void *key;

    union {//联合体表示不同数据类型，节省空间

        void *val;

        uint64_t u64;

        int64_t s64;

    } v;

    struct dictEntry *next;

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

/* This is our hash table structure. Every dictionary has two of this as we

 * implement incremental rehashing, for the old to the new table. */

typedef struct dictht {//hash表

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

typedef struct dict {//数据字典

    dictType *type;

    void *privdata;

    dictht ht[2];//每个数据字典有两个hash表

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */如果值为-1说明没有处于rehash的过程，否则说明指向当前正在rehash的链表的表头在字典中的索引。

    int iterators; /* number of iterators currently running */

} dict;

/* Add an element to the target hash table */

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

{

    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;

    dictSetVal(d, entry, val);

    return DICT_OK;

}

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

{

    int index;

    dictEntry *entry;

    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if

     * the element already exists. */

    if ((index = _dictKeyIndex(d, key)) == -1)

        return NULL;

    /* Allocate the memory and store the new entry */

    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];//如果没有rehash，则还是在ht[0]上操作，否则将新节点加入到ht[1]上。

    entry = zmalloc(sizeof(*entry));

    entry->next = ht->table[index];

    ht->table[index] = entry;

    ht->used++;

    /* Set the hash entry fields. */

    dictSetKey(d, entry, key);

    return entry;

}

int dictRehash(dict *d, int n) {

    if (!dictIsRehashing(d)) return 0;

    while(n--) {

        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */

        if (d->ht[0].used == 0) {//如果表0已经为空，说明rehash完成了，释放表0

            zfree(d->ht[0].table);

            d->ht[0] = d->ht[1];

            _dictReset(&d->ht[1]);

            d->rehashidx = -1;

            return 0;

        }

        /* Note that rehashidx can't overflow as we are sure there are more

         * elements because ht[0].used != 0 */

        assert(d->ht[0].size > (unsigned)d->rehashidx);//防止越界

        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;//从rehashidx+1开始执行

        de = d->ht[0].table[d->rehashidx];//取出当前链表的表头

        /* Move all the keys in this bucket from the old to the new hash HT */

        while(de) {//循环将当前链表的所以节点都从表0移除，加入到表1

            unsigned int h;

            nextde = de->next;

            /* Get the index in the new hash table */

            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            de->next = d->ht[1].table[h];//采用头插法将节点插入新表

            d->ht[1].table[h] = de;

            d->ht[0].used--;

            d->ht[1].used++;

            de = nextde;

        }

        d->ht[0].table[d->rehashidx] = NULL;

        d->rehashidx++;

    }

    return 1;

}

/* Expand or create the hash table */

int dictExpand(dict *d, unsigned long size)

{

    dictht n; /* the new hash table */

    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of

     * elements already inside the hash table */

    if (dictIsRehashing(d) || d->ht[0].used > size)

        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */

    n.size = realsize;

    n.sizemask = realsize-1;

    n.table = zcalloc(realsize*sizeof(dictEntry*));

    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing

     * we just set the first hash table so that it can accept keys. */

    if (d->ht[0].table == NULL) {

        d->ht[0] = n;

        return DICT_OK;

    }

    /* Prepare a second hash table for incremental rehashing */

    d->ht[1] = n;

    d->rehashidx = 0;

    return DICT_OK;

}