Home Page
Search
\begin{md} # 基础数据结构 ## 导语 这篇文章是在阅读 Redis 基础数据结构的过程中写的,内容条理不会很清晰,记录的主要是阅读代码过程中的思考。 Redis 版本:3.0.1 ## SDS *相关文件:deps/hiredis/sds.h, deps/hiredis/sds.c* SDS 相关代码总是会用到一个函数 `sds sdsMakeRoomFor(sds *s*, size_t *addlen*)` 。这个函数需要注意的地方是它的扩容方式是调用 `zrealloc` 函数,调用了这个函数,返回的扩容后的内存块的首地址可能不一定是我们传入的地址,所以如果调用了 `sdsMakeRoomFor` 函数,需要注意到:**以前指向 sds s 的指针有可能失效**。所以,很多 SDS 相关函数都会提示: > After the call, the modified sds string is no longer valid and all the references must be substituted with the new pointer returned by the call ## DICT *相关文件:deps/hiredis/dict.h, deps/hiredis/dict.c, src/dict.h, src/dict.c* 有个需要注意的地方:**deps/hiredis/dict.h 和 src/dict.h 两个文件里面都有 struct dict,但是内容和含义不相同** 函数 `static unsigned int dictGenHashFunction(const unsigned char **buf*, int *len*);` 。这是一个哈希函数,根据给定的字符串来求一个哈希值。找到的一篇关于这个函数的介绍: > [djb2:一个产生简单的随机分布的哈希函数](https://www.cnblogs.com/vancasola/p/9951686.html) 哈希表的扩展函数分析 ```c /* Expand or create the hashtable */ static int dictExpand(dict *ht, unsigned long size) { // 创建一个新的哈希表用来存放原哈希表的元素 dict n; /* the new hashtable */ // 计算新哈希表的槽位数量 unsigned long realsize = _dictNextPower(size), i; /* the size is invalid if it is smaller than the number of * elements already inside the hashtable */ if (ht->used > size) return DICT_ERR; // 设置新哈希表的 type 和 privdata 于原哈希表一致 _dictInit(&n, ht->type, ht->privdata); n.size = realsize; n.sizemask = realsize-1; n.table = calloc(realsize,sizeof(dictEntry*)); /* Copy all the elements from the old to the new table: * note that if the old hash table is empty ht->size is zero, * so dictExpand just creates an hash table. */ n.used = ht->used; // 循环复制每个原哈希表的槽位 for (i = 0; i < ht->size && ht->used > 0; i++) { dictEntry *he, *nextHe; if (ht->table[i] == NULL) continue; /* For each hash entry on this slot... */ he = ht->table[i]; // 循环复制每个槽位内的冲突链表 while(he) { unsigned int h; nextHe = he->next; /* Get the new element index */ h = dictHashKey(ht, he->key) & n.sizemask; he->next = n.table[h]; n.table[h] = he; ht->used--; /* Pass to the next element */ he = nextHe; } } assert(ht->used == 0); free(ht->table); /* Remap the new hashtable in the old */ *ht = n; return DICT_OK; } ``` ## ZSKIPLIST > [redis(五)跳跃表](https://blog.csdn.net/lz710117239/article/details/78408919#commentBox) 删除 skiplist 的方法: ```c void zslFree(zskiplist *zsl) { // 取第一个非头节点元素 zskiplistNode *node = zsl->header->level[0].forward, *next; // 释放头节点 zfree(zsl->header); // 利用 节点的 forward 指针来遍历跳跃表释放所有节点 while(node) { next = node->level[0].forward; zslFreeNode(node); node = next; } zfree(zsl); } ``` 关于跳表新加节点的时候如何设置新节点的层数的函数 ```c /* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */ int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level
这里的 ZSKIPLIST_P 是 0.25。上述代码中,level 初始化为 1,然后,如果持续满足条件: `(random()&0xFFFF)< (ZSKIPLIST_P * 0xFFFF)` 的话,则 level+= 1。最终调整 level 的值,使其小于 ZSKIPLIST_MAXLEVEL。 > > 理解该算法的核心,就是要理解满足条件: `(random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)` 的概率是多少? > > `random()&0xFFFF` 形成的数,均匀分布在区间 [0, 0xFFFF] 上,那么这个数小于 `(ZSKIPLIST_P * 0xFFFF)` 的概率是多少呢?自然就是 ZSKIPLIST_P,也就是 0.25 了。 > > 因此,最终返回 level 为 1 的概率是 `1-0.25=0.75` ,返回 level 为 2 的概率为 `0.25*0.75` ,返回 level 为 3 的概率为 `0.25*0.25*0.75` ...... 因此,如果返回 level 为 k 的概率为 x,则返回 level 为 k+1 的概率为 `0.25*x` ,换句话说,如果 k 层的结点数是 x,那么 k+1 层就是 `0.25*x` 了。这就是所谓的幂次定律(powerlaw),越大的数出现的概率越小。 > > [引用来源](https://blog.csdn.net/lz710117239/article/details/78408919#commentBox) ```c #include
#include
#include
int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (0.25 * 0xFFFF)) level += 1; return (level<32) ? level : 32; } static long int map[33]; int main() { int tmp = 0; for(int i = 0; i < INT_MAX; ++i) { tmp = zslRandomLevel(); map[tmp] += 1; } for (int i = 0; i < 33; ++i) { printf("%d: %d\n", i, map[i]); } return 0; } ``` 测试结果感觉确实是。 ```bash 0: 0 1: 1610591758 2: 402658458 3: 100679918 4: 25162418 5: 6293395 6: 1572850 7: 394115 8: 97892 9: 24560 10: 6288 11: 1505 12: 369 13: 85 14: 30 15: 6 16: 0 17: 0 18: 0 19: 0 20: 0 21: 0 22: 0 23: 0 24: 0 25: 0 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0 32: 0 ``` ## HyperLogLog [神奇的 HyperLogLog 算法](http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html) \end{md}
Home Page