Redis字典数据结构
Redis字典数据结构
WhiteFish 发表于2年前
Redis字典数据结构
  • 发表于 2年前
  • 阅读 138
  • 收藏 3
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 阅读redis代码随手记录下有趣的东西
  • 字典节点。key/value结构。 

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;


  • 字典表

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




  • 迭代器

将safe置1可将迭代器定义为安全的,也就是说添加、查找或者其他操作是与其他的迭代器排他的。

如果是非安全的,则只能进行遍历操作。

/* If safe is set to 1 this is a safe iterator, that means, you can call
 * dictAdd, dictFind, and other functions against the dictionary even while
 * iterating. Otherwise it is a non safe iterator, and only dictNext()
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;


迭代器设计的时候采用指纹的方法(long long dictFingerprint(dict *d) )

申请迭代器的时候,会根据当前字典的地址、大小和使用量计算一个HASH值。每次使用迭代器的时候,比较这个迭代器的指纹

与当前字典的指纹是否一样,如果不同则此迭代器不能使用。

关于字典的REHASH

字典本质上讲就是一个哈希表。Redis的rehash策略是,记录每次进行rehash的位置,在每一次

对字典的操作时判断是否在进行rehash操作。如果是则rehash,为了不会出现某个操作耗时太久

定义了单次操作的最大bucket个数


共有 人打赏支持
粉丝 2
博文 3
码字总数 1035
×
WhiteFish
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: