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

hash, dict

Posted by chensong on 2019-10-14 20::19::27

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

redis源码学习系列文章:

redis源码分析之sha1算法分析

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

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

redis源码分析之跳跃表

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

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

redis源码分析之异步进程保存数据rdb文件和aof文件源码分析

redis源码之sentinel高可用架构分析

redis源码分析之集群之一的槽的分配算法crc16原理分析

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

前言

散列表

理解散列存在意义

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

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

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中的哈希刚刚开始没有数据时哈希的大小是0,当要插入一个数据时就哈希的大小变成4, 之后就是2陪的扩容了。 哈希因子是5, 我没有明白为什么是”5”

dict_force_resize_ratio = 5;


/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned
 * and the optional output parameter may be filled.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
	if (_dictExpandIfNeeded(d) == DICT_ERR)
	{
		return -1;
	}
    for (table = 0; table <= 1; table++) 
	{
        idx = hash & d->ht[table].sizemask;   // 这边hash & mask 
        /* Search if this slot does not already contain the given key */
		// 在发生哈希冲突时会触发
		/**/
        he = d->ht[table].table[idx];
        while(he) 
		{
			// key值是否相同, 这个情况子啊一开始查询的时候就已经排除了
            if (key==he->key || dictCompareKeys(d, key, he->key)) 
			{
                if (existing) *existing = he;
                return -1;
            }
			// 这里已经把哈希表中索引的节点向后移动了, 得到链表中最后一个节点的指针
			// 这边使用是开链法 
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}


/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
	if (d->ht[0].size == 0)
	{
		return dictExpand(d, DICT_HT_INITIAL_SIZE); //申请内存空间 
	}

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    //判断是否需要扩容   ?? 有一点想不通 --> 就是used / size > 5 有一点不可能啊 只有在哈希冲突时会发生的这种情况
	if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used / d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used * 2);
    }
    return DICT_OK;
}

四 , 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;
}

结语

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