欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

redis源码分析之字典源码分析

程序员文章站 2022-05-20 22:13:51
...

=====================================================

redis源码学习系列文章:

redis源码分析之sha1算法分析

redis源码分析之字典源码分析

redis源码分析之内存编码分析intset, ziplist编码分析

redis源码分析之跳跃表

redis源码分析之内存淘汰策略的原理分析

redis源码分析之对象系统源码分析string, list链表,hash哈希,set集合,zset有序集合

=====================================================

在我的github上会持续更新Redis代码的中文分析,地址送出https://github.com/chensongpoixs/credis_source,共同学习进步

前言

散列表

理解散列存在意义

解决内存使用尽可能少内存 (空间问题)

简单定义一个散列函数 公式:

hash(k) = k % M == 得到的值 是数组中id 数组中存储 实际 数据存储的地址

分析流程

  1. 散列基本原则
  2. redis中的哈希均匀
  3. redis怎么解决哈希碰撞

正文

一, 散列函数设置原则

  1. 确定性(determinism): 同一关键码总是被映射至同一地址
  2. 快速性(efficiency): expected-O(1)
  3. 满射性(surjection): 尽可能充分地覆盖整个散列空间
  4. 均匀性(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源码分析之字典源码分析

在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;
}

结语

个人博客地址