当前位置:网站首页>Redis源码学习(30),字典学习,dict.h
Redis源码学习(30),字典学习,dict.h
2022-07-06 21:10:00 【无痕之意】
前言
经过我们不懈的努力,终于将复杂的压缩列表学习完了,虽然学习完了,但还是要经常复习才行,温故而知新可以为师矣,否则岂不是走马观花学习了一遍,之后就忘记的光光。
今天开始学习一个新的数据结构,字典,字典在 Redis 中有很多应用场景,和其他数据结构一样我们先来学习一下他的头文件 dict.h 。
1 字典
在 Redis 中,字典是由哈希表组成,哈希表又是由许多个哈希节点组成,每个哈希节点的位置会根据键值计算一个哈希值来确定在哈希表中的位置。
2 结构体定义
2.1 dictEntry
typedef struct dictEntry {
void *key;//键值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;//值
struct dictEntry *next;//一个哈希桶中下一个节点
} dictEntry;
这个结构体是哈希节点的定义,里面有 3 个主要的属性,key、v、next,分别代表键、值、相同哈希值的下一个哈希节点,在哈希表中哈希节点可能会计算出相同的索引位置,也叫哈希冲突,这个时候就需要将这些相同位置的哈希节点链接起来。
2.2 dictType
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);//计算 hash 值
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;
这个结构体是哈希表的一些方法定义
2.3 dictht
typedef struct dictht {
dictEntry **table;//哈希节点指针数组
unsigned long size;//哈希表的长度
unsigned long sizemask;//哈希表长度的掩码,一般等于 size -1
unsigned long used;//哈希节点的数量
} dictht;
这个结构体是哈希表的定义,里面有 4 个属性 table 、size、sizemask、used,其中 size 表示哈希表的长度,sizemask 是用来计算哈希节点索引值的时候使用到,used 表示哈希表中哈希节点的数量。
2.4 dict
typedef struct dict {
dictType *type; // 类型函数结构体指针
void *privdata;// 私有数据
dictht ht[2]; //哈希表,2 个
long rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehashidx 进度
int iterators; /* number of iterators currently running */ //当前运行的迭代器数量
} dict;
这个接头体是字典的定义,结构体有5个属性。
可以看到 dict 里面定义两个 dictht,两个哈希表的作用是为了更好解决哈希冲突对哈希表进行扩容或者收缩,进行 rehash 动作,就是将第一个哈希表的哈希节点重新计算索引放到新的哈希表中。
rehashidx 这个属性表示当前 rehash 的进度。
3 宏定义
#define dictFreeVal(d, entry) \ if ((d)->type->valDestructor) \ (d)->type->valDestructor((d)->privdata, (entry)->v.val)
#define dictSetVal(d, entry, _val_) do {
\ if ((d)->type->valDup) \ entry->v.val = (d)->type->valDup((d)->privdata, _val_); \ else \ entry->v.val = (_val_); \ } while(0)
#define dictSetSignedIntegerVal(entry, _val_) \ do {
entry->v.s64 = _val_; } while(0)
#define dictSetUnsignedIntegerVal(entry, _val_) \ do {
entry->v.u64 = _val_; } while(0)
#define dictSetDoubleVal(entry, _val_) \ do {
entry->v.d = _val_; } while(0)
#define dictFreeKey(d, entry) \ if ((d)->type->keyDestructor) \ (d)->type->keyDestructor((d)->privdata, (entry)->key)
#define dictSetKey(d, entry, _key_) do {
\ if ((d)->type->keyDup) \ entry->key = (d)->type->keyDup((d)->privdata, _key_); \ else \ entry->key = (_key_); \ } while(0)
#define dictCompareKeys(d, key1, key2) \ (((d)->type->keyCompare) ? \ (d)->type->keyCompare((d)->privdata, key1, key2) : \ (key1) == (key2))
#define dictHashKey(d, key) (d)->type->hashFunction(key)
#define dictGetKey(he) ((he)->key)
#define dictGetVal(he) ((he)->v.val)
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
#define dictGetDoubleVal(he) ((he)->v.d)
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
#define dictIsRehashing(d) ((d)->rehashidx != -1)
4 API
dict *dictCreate(dictType *type, void *privDataPtr);
int dictExpand(dict *d, unsigned long size);
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key);
int dictReplace(dict *d, void *key, void *val);
dictEntry *dictReplaceRaw(dict *d, void *key);
int dictDelete(dict *d, const void *key);
int dictDeleteNoFree(dict *d, const void *key);
void dictRelease(dict *d);
dictEntry * dictFind(dict *d, const void *key);
void *dictFetchValue(dict *d, const void *key);
int dictResize(dict *d);
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
dictEntry *dictGetRandomKey(dict *d);
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
void dictPrintStats(dict *d);
unsigned int dictGenHashFunction(const void *key, int len);
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);
void dictEmpty(dict *d, void(callback)(void*));
void dictEnableResize(void);
void dictDisableResize(void);
int dictRehash(dict *d, int n);
int dictRehashMilliseconds(dict *d, int ms);
void dictSetHashFunctionSeed(unsigned int initval);
unsigned int dictGetHashFunctionSeed(void);
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata);
5 学习总结
- Redis 中字典有两个哈希表。
- Redis 为了更好解决哈希冲突会进行 rehash 动作,重新计算哈希节点的哈希值。
- 哈希节点 dictEntry 中记录了相同索引位置的下一个哈希节点的指针,方便查找和遍历。
- 字典涉及的几个结构体有 dict、dictht、dictEntry 分别代表字典、哈希表、哈希节点。
- dictht 中包含了哈希节点的数组。
边栏推荐
- PIP download only, not install
- [leetcode] 700 and 701 (search and insert of binary search tree)
- HW notes (II)
- 2022年上半年HIT行业TOP50
- leetcode:面试题 17.24. 子矩阵最大累加和(待研究)
- About Estimation Statistics
- 枚举通用接口&枚举使用规范
- 23. (ArcGIS API for JS) ArcGIS API for JS ellipse collection (sketchviewmodel)
- Baidu map JS development, open a blank, bmapgl is not defined, err_ FILE_ NOT_ FOUND
- When QT uses qtooltip mouse to display text, the picture of the button will also be displayed and the prompt text style will be modified
猜你喜欢
你心目中的数据分析 Top 1 选 Pandas 还是选 SQL?
1.19.11.SQL客户端、启动SQL客户端、执行SQL查询、环境配置文件、重启策略、自定义函数(User-defined Functions)、构造函数参数
What is the experience of maintaining Wanxing open source vector database
Preprocessing - interpolation
Code quality management
web服务性能监控方案
Set static IP for raspberry pie
什么是 BA ?BA怎么样?BA和BI是什么关系?
About Confidence Intervals
代码质量管理
随机推荐
termux设置电脑连接手机。(敲打命令贼快),手机termux端口8022
Tencent cloud native database tdsql-c was selected into the cloud native product catalog of the Academy of communications and communications
Clock in during winter vacation
List interview common questions
二叉搜索树的实现
Ubuntu 20 installation des enregistrements redisjson
Kalman filter-1
复杂因子计算优化案例:深度不平衡、买卖压力指标、波动率计算
About Tolerance Intervals
使用 BR 恢复 GCS 上的备份数据
Can the applet run in its own app and realize live broadcast and connection?
10 ways of interface data security assurance
About Confidence Intervals
Kotlin Android environment construction
【安全攻防】序列化與反序列,你了解多少?
1200.Minimum Absolute Difference
浅谈网络安全之文件上传
Enumeration general interface & enumeration usage specification
卡尔曼滤波-1
预处理——插值