redis基础数据结构-dict简介

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef struct dictEntry {
void *key;
void *val;
struct dictEntry *next;
} dictEntry;

/* 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];
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;

特点

  • 2个ht,用于循环渐进式的rehash,避免ht过大的情况下一次性rehash而卡住程序
  • 底层实现为哈希桶
  • fingerprint:指纹值方法用于粗略判断两个时间戳之间ht是否有被修改
  • rehash的条件考虑到了存档RDB时的linux操作系统的写时复制策略

主要接口实现

  • 插入节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    /* Add an element to the target hash table */
    int dictAdd(dict *d, void *key, void *val)
    {
    int index;
    dictEntry *entry;
    dictht *ht;

    /* 执行一次rehash */
    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 DICT_ERR;

    /* Allocates the memory and stores key
    * 正在rehash则存入ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = _dictAlloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetHashKey(d, entry, key);
    dictSetHashVal(d, entry, val);
    return DICT_OK;
    }
  • rehash

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    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) {
    _dictFree(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
    * 因为上面used的判断,这里可以确定不会溢出 */
    while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

    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++;
    }
    return 1;
    }
-------------本文结束 感谢阅读-------------