DICT数据结构 Dict其实就是一个hash表，但在Redis中，已经存在一种叫Hash的数据结构，所以，就把Hash表改名成Dict吧。。。 Dict是Redis进行键值处理的灵魂，不管多大的数据量，始终维持O(1)的时间复杂度（排除bucket下链表很长的情况） 全局保存的所有key，
DICT数据结构
dict其实就是一个hash表，但在redis中，已经存在一种叫“hash”的数据结构，所以，就把hash表改名成dict吧。。。
dict是redis进行键值处理的灵魂，不管多大的数据量，始终维持o(1)的时间复杂度（排除bucket下链表很长的情况）
全局保存的所有key，都存在于一个dict中
而且别的数据结构，比如set、hash也可能会用到dict
Dict实现于 dict.h dict.c 两个文件中
其类型定义如下图：
1. dict：表示一个独立的dict结构，提供给外部使用
1 typedef struct dict {*privdata;rehashidx; iterators; } dict;
2. dictht：表示一个独立的dict容器，内部使用，外部程序不建议直接操作该结构
1 typedef struct dictht {unsigned unsigned unsigned } dictht;
3. dictEntry：数据结点，香港服务器租用，其实就是一个kv键值对，还包含一个next指针
1 typedef struct dictEntry {2void *key;3void *val;4struct dictEntry *next;5 } dictEntry;
4. dictType：定义了一组回调函数，进行数据结点的操作
typedef struct dictType {unsigned *(*keyDup)(*(*valDup)((*keyCompare)(*key2); (*keyDestructor)((*valDestructor)(void *privdata, void *obj); //销毁val} dictType;
DICT操作
Redis中的dict是一个标准的 “bucket + 开链” 的哈希表
并未进行更复杂的处理
包括防止哈希冲突导致开链过长的问题，也没有考虑
如果精心构造一串key来打redis，很容易打死的
所以，企业级应用的同学们，如果你的Redis服务对用户比较Open，别下个源码就用了，还是动手改改HashFunction再用吧！
Redis用两个dictht结构，作用是为了能够渐进地导数据，防止Rehash时阻塞时间太长
这种做法在memcache中就已经用了，不过memcache中是开辟一个线程专门做rehash而已
相比之下，不开线程的处理方式不用锁，BUG更少一些
命名空间
Redis中的Dict分为两类：
1. 系统级Dict，具有全局的命名空间，其定义如下：
typedef struct redisDb {dict *dict;dict *expires;dict *blocking_keys;dict *io_keys;dict *watched_keys; id;} redisDb;
2. 应用级Dict，由metadata数据结构自己维护，主要是一些 set、hash结构中的dict
如下图：
代码小浣熊
代码小浣熊是基于商汤大语言模型的软件智能研发助手，覆盖软件需求分析、架构设计、代码编写、软件测试等环节
51 查看详情
Rehash
当满足以下条件时，会启动Rehash
1 // 当有效空间使用率 htNeedsResize(dict *dict) { size, used; 5 6size = dictSlots(dict); 7used = dictSize(dict); 8return (size && used && size > DICT_HT_INITIAL_SIZE && 9(used*100/size REDIS_HT_MINFILL));10 }
1 // 当有效空间使用率 > 100%时，_dictExpandIfNeeded(dict *d) 4 { 5 … …(d->ht[0].used >= d->ht[0].size && 8(dict_can_resize || 9d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))10 {11return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?12d->ht[0].size : d->ht[0].used)*2);13 }14return DICT_OK;15 }
Rehash启动后，就要开始进行Rehash操作了
但是，Rehash的代价是很大的，特别是当容量超过千万级以后，往往会耗费数十秒来进行操作（视机器性能）
所以，Redis采用了渐进式的Rehash，把操作分片，一步步来，总不能阻塞用户响应吧
根据Dict的类型不同，会采用不同的Rehash策略：
1. 全局性的DICT结构（就是全局命名空间中的key），会周期性的进行rehash，每次进行 1ms
而且，不受稍后提到的 SafeIterator的干扰，可以一直执行（但是，虚拟主机，不受干扰是一回事，在iterator循环空间中，还是得用Safe模式的，所以，源码中也会看到大量针对全局dict的SafeIterator，这一点需要理解一下）
毕竟，全局的，是重要的嘛，挤也要挤出1ms来，用吧！而且还甭想打扰它，别不服气了
2. 应用级DICT结构（就是用户自定义的一些DICT），Redis会采取一种 Lazy Rehash 的策略
所谓 Lazy Rehash，就是用得越多，处理得越快；用得越少，处理得越慢
什么叫“用”呢？
很好理解，“增删查”操作都叫用，源码里对应：dictAdd、dictGenericDelete、dictFind、dictGetRandomKey操作，都会促发_dictRehashStep函数进行Rehashing
但别高兴太早，每次只触发一条而已，所以，慢慢来吧~~
Iterator
由于Dict内部结构的复杂性，虚拟主机，提供一个遍历所有数据的iterator，是非常必要的
Dict提供两种Iterator:
1. dictGetIterator：普通iter，在遍历时不可对dict做更多操作，否则会引起数据遗漏或重复
2. dictGetSafeIterator：安全iter，什么操作都能做，安全的，你懂的。
可以参考上图理解这一点，不再赘述
DictType
dictType 定义了dict的操作行为。Redis预定义了一组dictType，规范各种类型dict的操作
相关代码如下：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/471684.html
微信扫一扫 
支付宝扫一扫 
