redis源码分析之字典源码分析
=====================================================
redis源码学习系列文章:
redis源码分析之内存编码分析intset, ziplist编码分析
redis源码分析之对象系统源码分析string, list链表,hash哈希,set集合,zset有序集合
=====================================================
在我的github上会持续更新Redis代码的中文分析,地址送出https://github.com/chensongpoixs/credis_source,共同学习进步
前言
散列表
理解散列存在意义
解决内存使用尽可能少内存 (空间问题)
简单定义一个散列函数 公式:
hash(k) = k % M == 得到的值 是数组中id 数组中存储 实际 数据存储的地址
分析流程
- 散列基本原则
- redis中的哈希均匀
- redis怎么解决哈希碰撞
正文
一, 散列函数设置原则
- 确定性(determinism): 同一关键码总是被映射至同一地址
- 快速性(efficiency): expected-O(1)
- 满射性(surjection): 尽可能充分地覆盖整个散列空间
- 均匀性(uniformity): 关键码映射到散列表各位置的概率尽量接近可有效避聚集(clustering)现象
在redis中的哈希因子怎么确定了使用sha1算法生成160位的的16字节关于sha1算法可以这里redis源码分析之sha1算法分析
在redis服务器初始化时hash的因子
char hashseed[16];
getRandomHexChars(hashseed, sizeof(hashseed));
// 设置hash因子
dictSetHashFunctionSeed((uint8_t*)hashseed);
二, redis中的哈希均匀
在redis使用google研发siphash算法
我们正常使用两个差别不大字符串经过hash后差别非常大,当时google的siphash算法两个相差不大的hash值也不大的
siphash的算法我也暂时完全理解大家可以自行百度,下面提供参考
采用例子来详解simhash的生成规则。simhash的生成划分为五个步骤:分词->hash->加权->合并->降维
算法描述如下:
输入为一个N维向量V,比如文本的特征向量,每个特征具有一定权重。输出是一个C位的二进制签名S。
1)初始化一个C维向量Q为0,C位的二进制签名S为0。
2)对向量V中的每一个特征,使用传统的Hash算法计算出一个C位的散列值H。对1<=i<=C,
如果H的第i位为1,则Q的第i个元素加上该特征的权重;
否则,Q的第i个元素减去该特征的权重。
3)如果Q的第i个元素大于0,则S的第i位为1;否则为0;
4)返回签名S。
解释:名词
在信息编码中,两个合法代码对应位上编码不同的位数称为码距,又称海明距离。
举例如下:
10101和00110从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。
编辑
两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。
一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。
三, redis怎么解决哈希碰撞
在redis中哈希碰撞发生插入当前节点下一个节点连接成链表,然后子啊主线程进行异步渐渐移动字典1中数据移动字典2中的
int dictRehash(dict *d, int n) {
// empty_visits == 1000;
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d))
{
return 0;
}
while(n-- && d->ht[0].used != 0)
{
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
// rehashindx每次主线程更新检查1000数据中是否没有数据没有直接符合,下次在上次索引后面继续检查是否有数据有就检查是否有哈希冲突
while(d->ht[0].table[d->rehashidx] == NULL)
{
d->rehashidx++;
if (--empty_visits == 0)
{
return 1;
}
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
// 看见吧把hashtable1中数据移动hashtable2中了还是
while(de)
{
uint64_t h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
// 把hashtable2移动hashtable1表 的指针
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0)
{
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
结语
上一篇: 寻找连通域的质心
下一篇: Ubuntu下安装docker方法详解