typedef struct dictEntry {
	    void *key;	//键
	    union {
	        void *val;
	        uint64_t u64;
	        int64_t s64;
	        double d;
	    } 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 {
	    dictEntry **table;
	    unsigned long size;
	    unsigned long sizemask;
	    unsigned long used;
	} dictht;

	
	typedef struct dict {
	    dictType *type;
	    void *privdata;
	    dictht ht[2];
	    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
	    int iterators; /* number of iterators currently running */
	} dict;

	/* Returns the index of a free slot that can be populated with
	 * a hash entry for the given 'key'.
	 * If the key already exists, -1 is returned.
	 *
	 * Note that if we are in the process of rehashing the hash table, the
	 * index is always returned in the context of the second (new) hash table. */
	static int _dictKeyIndex(dict *d, const void *key)
	{
	    unsigned int h, idx, table;
	    dictEntry *he;
	
	    /* Expand the hash table if needed */
	    if (_dictExpandIfNeeded(d) == DICT_ERR)		//判断是否需要扩大哈希表的大小，如果正在 rehash，返回 true
													//如果used/size 大于安全阀值5时，将需要扩大哈希表大小
	        return -1;
	    /* Compute the key hash value */
	    h = dictHashKey(d, key);		//计算哈希值
	    for (table = 0; table <= 1; table++) {
	        idx = h & d->ht[table].sizemask;	//计算索引值，在哈希表中查找是否存在，存在返回-1，不存在，返回索引值
	        /* Search if this slot does not already contain the given 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;
	}

	/* 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)	//如果rehashidx不是-1，说明正在扩，不需重复操作；而且扩大后，used 应该小于 size
	        return DICT_ERR;
	
	    /* Rehashing to the same table size is not useful. */
	    if (realsize == d->ht[0].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;	// 将 ht[1] 设置为扩大后的哈希表，然后将 rehashidx 置为0，表明从 0 开始 rehash
	    d->rehashidx = 0;
	    return DICT_OK;
	}

	/* MurmurHash2, by Austin Appleby
	 * Note - This code makes a few assumptions about how your machine behaves -
	 * 1. We can read a 4-byte value from any address without crashing
	 * 2. sizeof(int) == 4
	 *
	 * And it has a few limitations -
	 *
	 * 1. It will not work incrementally.
	 * 2. It will not produce the same results on little-endian and big-endian
	 *    machines.
	 */
	unsigned int dictGenHashFunction(const void *key, int len) {
	    /* 'm' and 'r' are mixing constants generated offline.
	     They're not really 'magic', they just happen to work well.  */
	    uint32_t seed = dict_hash_function_seed;
	    const uint32_t m = 0x5bd1e995;
	    const int r = 24;
	
	    /* Initialize the hash to a 'random' value */
	    uint32_t h = seed ^ len;
	
	    /* Mix 4 bytes at a time into the hash */
	    const unsigned char *data = (const unsigned char *)key;
	
	    while(len >= 4) {
	        uint32_t k = *(uint32_t*)data;
	
	        k *= m;
	        k ^= k >> r;
	        k *= m;
	
	        h *= m;
	        h ^= k;
	
	        data += 4;
	        len -= 4;
	    }
	
	    /* Handle the last few bytes of the input array  */
	    switch(len) {
	    case 3: h ^= data[2] << 16;
	    case 2: h ^= data[1] << 8;
	    case 1: h ^= data[0]; h *= m;
	    };
	
	    /* Do a few final mixes of the hash to ensure the last few
	     * bytes are well-incorporated. */
	    h ^= h >> 13;
	    h *= m;
	    h ^= h >> 15;
	
	    return (unsigned int)h;
	}

	/* Low level add. This function adds the entry but instead of setting
	 * a value returns the dictEntry structure to the user, that will make
	 * sure to fill the value field as he wishes.
	 *
	 * This function is also directly exposed to the user API to be called
	 * mainly in order to store non-pointers inside the hash value, example:
	 *
	 * entry = dictAddRaw(dict,mykey);
	 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
	 *
	 * Return values:
	 *
	 * If key already exists NULL is returned.
	 * If key was added, the hash entry is returned to be manipulated by the caller.
	 */
	/*如果key已经在哈希表中已经存在，返回NULL；否则返回该哈希节点*/
	dictEntry *dictAddRaw(dict *d, void *key)
	{
	    int index;
	    dictEntry *entry;
	    dictht *ht;
	
		/* 判断是否正在 rehash，正在 rehash 中的哈希表与没有 rehash 的哈希表插入操作不同
		 1. 当 rehash 时，需要将ht[0] 中的所有节点 rehash 到 ht[1]中，这时，为了保证ht[0]中的节点是一直减少的，插入时插入到ht[1]中
		 2. 没有 rehash ，直接将节点插入到 ht[0]中
		*/	
	    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];
	    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;
	}

	/* Expand the hash table if needed */
	static int _dictExpandIfNeeded(dict *d)
	{
	    /* Incremental rehashing already in progress. Return. */
	    if (dictIsRehashing(d)) return DICT_OK;
	
	    /* If the hash table is empty expand it to the initial size. */
	    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
	
	    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
	     * table (global setting) or we should avoid it but the ratio between
	     * elements/buckets is over the "safe" threshold, we resize doubling
	     * the number of buckets. */
	    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;
	}

	/* Performs N steps of incremental rehashing. Returns 1 if there are still
	 * keys to move from the old to the new hash table, otherwise 0 is returned.
	 *
	 * Note that a rehashing step consists in moving a bucket (that may have more
	 * than one key as we use chaining) from the old to the new hash table, however
	 * since part of the hash table may be composed of empty spaces, it is not
	 * guaranteed that this function will rehash even a single bucket, since it
	 * will visit at max N*10 empty buckets in total, otherwise the amount of
	 * work it does would be unbound and the function may block for a long time. */
	// 返回0表示 rehash 结束，返回1 表示还有键值对需要继续 rehash 
	int dictRehash(dict *d, int n) {
	    int empty_visits = n*10; /* Max number of empty buckets to visit. */
	    if (!dictIsRehashing(d)) return 0;
	
	    while(n-- && d->ht[0].used != 0) {
	        dictEntry *de, *nextde;
	
	        /* 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 long)d->rehashidx);
	        while(d->ht[0].table[d->rehashidx] == NULL) {
	            d->rehashidx++;
	            if (--empty_visits == 0) return 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) {
	            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++;		//操作完将 rehashidx 加1
	    }
	
	    /* Check if we already rehashed the whole table... */
	    if (d->ht[0].used == 0) {	//判断是否 rehash 操作完成
	        zfree(d->ht[0].table);
	        d->ht[0] = d->ht[1];
	        _dictReset(&d->ht[1]);
	        d->rehashidx = -1;
	        return 0;
	    }
	
	    /* More to rehash... */
	    return 1;
	}

	int dictDelete(dict *ht, const void *key) {
	    return dictGenericDelete(ht,key,0);
	}
	
	/* Search and remove an element */
	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; /* d->ht[0].table is NULL */
	    if (dictIsRehashing(d)) _dictRehashStep(d);
	    h = dictHashKey(d, key);	//获取哈希值
	
	    for (table = 0; table <= 1; table++) {
	        idx = h & d->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 */
	}

	/* Add an element, discarding the old if the key already exists.
	 * Return 1 if the key was added from scratch, 0 if there was already an
	 * element with such key and dictReplace() just performed a value update
	 * operation. */
	int dictReplace(dict *d, void *key, void *val)
	{
	    dictEntry *entry, auxentry;
	
	    /* Try to add the element. If the key
	     * does not exists dictAdd will suceed. */
	    if (dictAdd(d, key, val) == DICT_OK)
	        return 1;
	    /* It already exists, get the entry */
	    entry = dictFind(d, key);
	    /* Set the new value and free the old one. Note that it is important
	     * to do that in this order, as the value may just be exactly the same
	     * as the previous one. In this context, think to reference counting,
	     * you want to increment (set), and then decrement (free), and not the
	     * reverse. */
	    auxentry = *entry;
	    dictSetVal(d, entry, val);
	    dictFreeVal(d, &auxentry);
	    return 0;
	}