Redis源码阅读三:哈希表

栏目: 数据库 · 发布时间: 7年前

内容简介:直接上代码:

直接上代码:

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

typedef struct dictType {
    uint64_t (*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 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
  • 采用面向接口编程,把函数定义放到 struct dictType 里,这里是对字典中所有 元素进行操作的函数

  • struct dictEntry 是字典中K-V真正存放的地方, void *key 是K,而 union ... v 是V

  • 每个字典有两张哈希表,在 dictht ht[2] 这里定义。 rehashidx 是一个标记位,代表是否处于 重新哈希。其中rehash采用的是渐进式rehash,可以看到代码中有好几个地方有这样的代码:

if (dictIsRehashing(d)) _dictRehashStep(d);

/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python网络编程攻略

Python网络编程攻略

萨卡尔 (Dr.M.O.Faruque Sarker) / 安道 / 人民邮电出版社 / 2014-12-1 / 45.00元

开发TCP/IP网络客户端和服务器应用 管理本地设备的IPv4/IPv6网络接口 使用HTTP和HTTPS协议编写用途多、效率高的Web客户端 编写可使用常见电子邮件协议的电子邮件客户端 通过Telnet和SSH连接执行远程系统管理任务 使用Web服务与流行的网站交互 监控并分析重要的常见网络安全漏洞一起来看看 《Python网络编程攻略》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具