redis源代码分析3–字典（上）

字典实现中主要用到如下5个结构体：

typedef struct dictEntry {
    void *key;
    void *val;
    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;

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];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

typedef struct dictIterator {
    dict *d;
    int table;
    int index;
    dictEntry *entry, *nextEntry;
} dictIterator;

dict代表整个字典，内部有两个dictht, 以实现增量hash（将ht[0]中的值rehash到ht[1]中），

rehashidx是下一个需要rehash的项在ht[0]中的索引，不需要rehash时置为-1，

iterators记录当前dict中的迭代器数，主要是为了避免在有迭代器时rehash，在有迭代器时rehash可能会造成值的丢失或重复，

type的类型dictType是一组函数指针，表示该怎样哈希、复制、释放key，该怎样复制、释放value；

dictht中的table是一个数组+指针形式的hash表，size表hash数组(桶)的大小，used表示hash表的元素个数，这两个值与rehash、resize过程密切相关。sizemask等于size-1，这是为了方便将hash值映射到数组中。