当前位置:网站首页>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
- 21. (article ArcGIS API for JS) ArcGIS API for JS rectangular acquisition (sketchviewmodel)
- 【knife-4j 快速搭建swagger】
- Summer 2022 daily question 1 (1)
- 未来发展路线确认!数字经济、数字化转型、数据...这次会议很重要
- 华为小米互“抄作业”
- Create commonly used shortcut icons at the top of the ad interface (menu bar)
- termux设置电脑连接手机。(敲打命令贼快),手机termux端口8022
- 2022夏每日一题(一)
- 【安全攻防】序列化與反序列,你了解多少?
猜你喜欢
Hisilicon 3559 universal platform construction: RTSP real-time playback support
ggplot 分面的细节调整汇总
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
About Tolerance Intervals
[safe office and productivity application] Shanghai daoning provides you with onlyoffice download, trial and tutorial
Kotlin Android environment construction
Can the applet run in its own app and realize live broadcast and connection?
23. (ArcGIS API for JS) ArcGIS API for JS ellipse collection (sketchviewmodel)
How to customize the shortcut key for latex to stop running
What is the experience of maintaining Wanxing open source vector database
随机推荐
HW-小记(二)
It's too convenient. You can complete the code release and approval by nailing it!
使用 BR 恢复 GCS 上的备份数据
Search of linear table
哈夫曼树基本概念
About Tolerance Intervals
Implementation steps of docker deploying mysql8
1200.Minimum Absolute Difference
Ggplot facet detail adjustment summary
19. (ArcGIS API for JS) ArcGIS API for JS line acquisition (sketchviewmodel)
About Estimation Statistics
Mobile measurement and depth link platform - Branch
【安全攻防】序列化與反序列,你了解多少?
2022夏每日一题(一)
二进制、八进制、十六进制
自适应非欧表征广告检索系统AMCAD
Force buckle ----- path sum III
QT 项目 表格新建列名称设置 需求练习(找数组消失的数字、最大值)
一些常用软件相关
First understand the principle of network