文档章节

redis源码阅读-dict

l
 liamQuan
发布于 2015/11/21 20:43
字数 1775
阅读 68
收藏 0
  1. 概述

    redis内部的字典实现,字典使用了hash表作为dict底层实现。

  2. 数据结构

    一个dict中包含两个hash表(ht[2]),其中ht[1]主要是在对dict进行rehash时使用。hash表使用链地址法解决key冲突,即包含相同key的value用链表存储,入下图所示。

  3. api

    dict *dictCreate(dictType *type, void *privDataPtr);  //创建hash表

    void dictRelease(dict *d);                                        //清空并释放hash表    

    void dictEmpty(dict *d);                                         //清空hash表

    int dictResize(dict *d);                                            //将hash表大小重新调整为可以容纳当前所有元素的最小大小,在redis中,当hash表使用率小于10%时,会执行resize以节省内存

    void dictEnableResize(void);                                   //允许resize

    void dictDisableResize(void);                                 //不允许resize

    int dictExpand(dict *d, unsigned long size);            //为dict扩容


    int dictAdd(dict *d, void *key, void *val);                 //添加元素

    dictEntry *dictAddRaw(dict *d, void *key);              //添加元素但不设置value,主要为方便存储非指针value(比如整数)

    int dictReplace(dict *d, void *key, void *val);            //添加元素,如果key存在,则更新它


    int dictDelete(dict *d, const void *key);                    //删除元素      

    int dictDeleteNoFree(dict *d, const void *key);        //删除元素,但是不需要为key和value调用keyDestructor和valDestructor

      

    dictEntry * dictFind(dict *d, const void *key);         //查找元素,返回dictEntry结构体指针

    void *dictFetchValue(dict *d, const void *key);       //查找元素,返回val指针

    dictEntry *dictGetRandomKey(dict *d);                 //随机返回一个元素


    dictIterator *dictGetIterator(dict *d);                     //创建一个不安全的迭代器

    dictIterator *dictGetSafeIterator(dict *d);              //创建一个安全的迭代器

     dictEntry *dictNext(dictIterator *iter);                  //指向下一个节点,如果迭代完毕,返回NULL

    void dictReleaseIterator(dictIterator *iter);            //释放迭代器


    unsigned int dictGenHashFunction(const void *key, int len);    //MurmurHash2 hash函数

    unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);    //djb hash函数

    int dictRehash(dict *d, int n);                                //对dict执行n次rehash

    int dictRehashMilliseconds(dict *d, int ms);          //在ms毫秒内,对dict进行rehash

    void dictSetHashFunctionSeed(unsigned int initval);    //设置hash种子,若不设置,默认为5381

     unsigned int dictGetHashFunctionSeed(void);        //获取hash种子

  4. 应用

#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <string>

#include "dict.h"

using namespace std;

unsigned int DictStringHashFunc(const void *key) {
    assert(key != NULL);
    return dictGenHashFunction(key, strlen((char *)key));
}

void *DictStringDup(void *privdata, const void *key) {
    assert(key != NULL);
    return strdup((char *)key);
}

int DictStringCompare(void *privdata, const void *key1, const void *key2) {
    return strcmp((char *)key1, (char *)key2) == 0;
}

void StringDestructor(void *privdata, void *key) {
    free(key);
}

dictType g_dict_type = {
    DictStringHashFunc,         /* hash function */
    DictStringDup,              /* key dup */
    DictStringDup,              /* val dup */
    DictStringCompare,          /* key compare */
    StringDestructor,           /* key destructor */
    StringDestructor            /* val destructor */
};

int main(int argc, char *argv[]) {
    dict *dic = dictCreate(&g_dict_type,NULL);

    string key_base = "key";
    string value_base = "value";
    for (char ch = 'a'; ch < 'k'; ++ch) {
        string key = key_base + ch;
        string value = value_base + ch;
        dictAdd(dic, (void *)key.c_str(), (void *)value.c_str());
    }
    cout << "-----------------dict initial stat------------------------------------" << endl;
    dictPrintStats(dic);

    cout << "-----------------dictIterator-----------------------------------------" << endl;
    dictIterator *iter = dictGetIterator(dic);
    while (dictNext(iter) != NULL) {
        cout << (char *)iter->entry->key << "\t" << (char *)iter->entry->v.val << endl;
    }
    dictReleaseIterator(iter);

    cout << "-----------------dictFind---------------------------------------------" << endl;
    string fkey = "keyh";
    dictEntry *entry = dictFind(dic, "keyh");
    if (entry != NULL) {
        cout << "key: " << fkey << "\tvalue:" << (char *)entry->v.val << endl;
    }

    string new_val = "new_valueh";
    dictReplace(dic, (void *)fkey.c_str(), (void *)new_val.c_str());

    cout << "-----------------after dictReplace, dictFetchValue--------------------" << endl;
    void *val = dictFetchValue(dic, "keyh");
    if (val != NULL) {
        cout << "key: " << fkey << "\tvalue:" << (char *)val << endl;
    }

    dictDelete(dic, (void *)fkey.c_str());
    val = dictFetchValue(dic, "keyh");
    if (val != NULL) {
        cout << "key: " << fkey << "\tvalue:" << (char *)val << endl;
    }

    dictDelete(dic, dictGetRandomKey(dic)->key);
    dictDelete(dic, dictGetRandomKey(dic)->key);

    cout << "-----------------before dictResize, dict stat-----------------------" << endl;
    dictPrintStats(dic);

    dictResize(dic);
    cout << "-----------------after dictResize, dict stat------------------------" << endl;
    dictPrintStats(dic);

    dictRehash(dic, 8);
    cout << "-----------------after rehash 8 times, dict stat--------------------" << endl;
    dictPrintStats(dic);

    dictEmpty(dic);
    cout << "-----------------after dictEmpty, dict stat-------------------------" << endl;
    dictPrintStats(dic);

    dictRelease(dic);
    return 0;
}

运行结果:

-----------------dict initial stat------------------------------------
Hash table stats:
 table size: 8
 number of elements: 7
 different slots: 5
 max chain length: 2
 avg chain length (counted): 1.40
 avg chain length (computed): 1.40
 Chain length distribution:
   0: 3 (37.50%)
   1: 3 (37.50%)
   2: 2 (25.00%)
-- Rehashing into ht[1]:
Hash table stats:
 table size: 16
 number of elements: 3
 different slots: 3
 max chain length: 1
 avg chain length (counted): 1.00
 avg chain length (computed): 1.00
 Chain length distribution:
   0: 13 (81.25%)
   1: 3 (18.75%)
-----------------dictIterator-----------------------------------------
keya	valuea
keyb	valueb
keyh	valueh
keye	valuee
keyd	valued
keyc	valuec
keyg	valueg
keyj	valuej
keyf	valuef
keyi	valuei
-----------------dictFind---------------------------------------------
key: keyh	value:valueh
-----------------after dictReplace, dictFetchValue--------------------
key: keyh	value:new_valueh
-----------------before dictResize, dict stat-----------------------
Hash table stats:
 table size: 16
 number of elements: 7
 different slots: 7
 max chain length: 1
 avg chain length (counted): 1.00
 avg chain length (computed): 1.00
 Chain length distribution:
   0: 9 (56.25%)
   1: 7 (43.75%)
-----------------after dictResize, dict stat------------------------
Hash table stats:
 table size: 16
 number of elements: 7
 different slots: 7
 max chain length: 1
 avg chain length (counted): 1.00
 avg chain length (computed): 1.00
 Chain length distribution:
   0: 9 (56.25%)
   1: 7 (43.75%)
-- Rehashing into ht[1]:
No stats available for empty dictionaries
-----------------after rehash 8 times, dict stat--------------------
Hash table stats:
 table size: 8
 number of elements: 7
 different slots: 7
 max chain length: 1
 avg chain length (counted): 1.00
 avg chain length (computed): 1.00
 Chain length distribution:
   0: 1 (12.50%)
   1: 7 (87.50%)
-----------------after dictEmpty, dict stat-------------------------
No stats available for empty dictionaries

运行结果分析:

  1.  dict initial stat

    插入10个元素,经历了两次expand,第一次expand发生在插入第5个元素时,hashtable初始大小为4,所以插入第5个元素时,经历了一次expand,此时的状态为,ht[0] size为4,ht[1] size为8;此后的新元素都插入ht[1],同时每次插入,都会进行一次rehash,将ht[0]中的一个bucket移入ht[1];第二次expand发生在插入第9个元素时,此时的状态为,ht[0] size为8,used为8,ht[1] size为16,used为1,插入第10个元素时,也进行了一次rehash,将ht[0]中的一个bucket移入ht[1],而这个bucket中只有一个元素;所以插入完成后的状态为运行结果所示,ht[0]的table size为8,number of elements为7,ht[1]的table size为16,number of elements为3

  2. dictIterator

    此时dict中所有的kv对,包括ht[0]和ht[1]中的所有元素

  3. dictFind

    对应于keyh的元素为valueh,同时执行了一次rehash,将ht[0]中的一个bucket移入ht[1],而这个bucket中有两个元素,此时的状态为,ht[0] size为8,used为5,ht[1]的size为16,used为5

    后面的dictReplace中也经历了一次dictAdd和一次dictFind,个执行了一次rehash,ht[0] size为8,used为2,ht[1]的size为16,used为8

  4. after dictReplace, dictFetchValue

    dictFetchValue执行了一次rehash,此时的状态为,ht[0] size为8,used为1,ht[1]的size为16,used为9

    dictDelete删除了一个元素,执行了一次rehash,此时的状态为,ht[0] size为8,used为0,ht[1]的size为16,used为9

    后面的dictFetchValue执行了最后一次rehash,ht[0]=ht[1],释放ht[1],此时的状态为,ht[0] size为16,used为9,ht[1]的size为0,used为0,rehash状态结束

    后面的两次dictDelete从ht[0]中删除了2个元素,此时的状态为,ht[0] size为16,used为7,ht[1]的size为0,used为0

  5. before dictResize, dict stat

    resize之前的状态为和之前的状态一样,ht[0] size为16,used为7,ht[1]的size为0,used为0

  6. after dictResize, dict stat

    dictResize,ht[1]初始化为size为_dictNextPower(7)=8,此时的状态为,ht[0] size为16,used为7,ht[1]的size为8,used为0

  7. after rehash 8 times, dict stat

    经历8次rehash后,将ht[0]中的7个元素移入ht[1],将ht[1]赋给ht[0],同时释放ht[1],此时的状态为,ht[0] size为8,used为7,ht[1]的size为0,used为0

  8. after dictEmpty, dict stat

    dictEmtpy之后,清空dict,此时的状态为,ht[0] size为0,used为0,ht[1]的size为0,used为0


参考

http://www.cppblog.com/mysileng/archive/2013/04/05/199132.html    Redis 设计与实现--3--内部数据结构--字典

http://redisbook.com/  Redis 设计与实现



© 著作权归作者所有

l
粉丝 0
博文 4
码字总数 4672
作品 0
昌平
私信 提问
Redis源码阅读笔记-字典结构

字典 字典在Redis中主要用在数据库和哈希键功能上,其他也有。 当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现。(《R...

Jian_Ming
2018/09/09
27
0
Redis 哈希结构内存模型剖析

本文共 1231字,阅读大约需要 5分钟 ! --- 概述 在前文《Redis字符串类型内部编码剖析》之中已经剖析过 Redis最基本的 String类型的内部是怎么编码和存储的,本文再来阐述 Redis中使用 最为...

CodeSheep
2018/08/27
5.6K
2
玩一把redis源码之二—自定义hash、set数据类型

导读 一、本文目的 模仿redis实现自定义字典数据结构 模仿redis实现自定义set、hash数据类型 二、内容简介 redis中set和hash数据类型用到了hash算法,redis中存储数据库所有数据对象使用的基...

老叶茶馆_
01/28
0
0
美团针对Redis Rehash机制的探索和实践

背景 Squirrel(松鼠)是美团技术团队基于Redis Cluster打造的缓存系统。经过不断的迭代研发,目前已形成一整套自动化运维体系:涵盖一键运维集群、细粒度的监控、支持自动扩缩容以及热点Key...

美团技术团队
2018/07/27
103
0
Redis源码分析(dict)

源码版本: 源码位置: dict.h:等数据结构定义。 dict.c:创建、插入、查找等功能实现。 一、dict 简介 (dictionary 字典),通常的存储结构是形式的,通过对key求Hash值来确定Value的位置,...

yangbodong22011
2017/11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【jQuery基础学习】05 jQuery与Ajax以及序列化

本文转载于:专业的前端网站➭【jQuery基础学习】05 jQuery与Ajax以及序列化 好吧,这章不像上章那么水了,总是炒剩饭也不好。 关于AJAX 所谓Ajax,全名Asynchronous JavaScript and XML。(也...

前端老手
31分钟前
10
0
CVE-2019-14287(Linux sudo 漏洞)分析

作者:lu4nx@知道创宇404积极防御实验室 作者博客:《CVE-2019-14287(Linux sudo 漏洞)分析》 原文链接:https://paper.seebug.org/1057/ 近日 sudo 被爆光一个漏洞,非授权的特权用户可以...

极客君
31分钟前
7
0
关于分布式,你需要知道的真相

目录 一、分布式锁 数据库的唯一索引 Redis 的 SETNX 指令 Redis 的 RedLock 算法 Zookeeper 的有序节点 二、分布式事务 2PC 本地消息表 三、CAP 一致性 可用性 分区容忍性 权衡 四、BASE 基...

李红欧巴
31分钟前
8
0
读书笔记:深入理解ES6 (附录B)

附录B:了解ES7(2016)   ES6经历了4年的发展,之后TC-39决定将发布周期转换为每年一版,以确保新语言特性能够更快地发展。   ES6中添加了三个语法特性,下面一一来讲。 第1节 指数运算...

张森ZS
38分钟前
14
0
计算机公开课推荐 2019.8

欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 面试求职交流群 724187166 ApacheCN 学习资源 编程 哈佛 CS50:计算机科学导论 视频 MIT 6.00.1x:计算机科...

ApacheCN_飞龙
38分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部