=====================================================
redis源码学习系列文章：
redis源码分析之内存编码分析intset, ziplist编码分析
redis源码分析之对象系统源码分析string, list链表,hash哈希,set集合,zset有序集合
redis源码分析之异步进程保存数据rdb文件和aof文件源码分析
redis源码分析之集群之一的槽的分配算法crc16原理分析
=====================================================
前言
散列表
理解散列存在意义
解决内存使用尽可能少内存 (空间问题)
简单定义一个散列函数 公式:
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中的哈希刚刚开始没有数据时哈希的大小是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，共同学习进步
