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值映射到数组中。

此条目发表在 redis 分类目录。将固定链接加入收藏夹。

redis源代码分析3–字典(上)》有 4 条评论

  1. ericuni 说:

    dict 中privatedata 是干什么用的?
    再dictAddRaw 函数最后, 调用了 dictSetKey(d, entry, key);
    这里有对privdata 的使用
    entry->key = (d)->type->keyDup((d)->privdata, _key_);

  2. ericuni 说:

    还是dictAddRaw 这个函数, 在新增key的时候, 有下面的几句:
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    为什么在新增entry的时候, 要把新entry的 next 指向自己?

    • petermao 说:

      形成一个链表。解决hash冲突的一种方式。新entry先指向原来的链表头结点,然后table指向新entry。也意味着新entry放在头部。

发表评论

电子邮件地址不会被公开。 必填项已被标记为 *

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>