42张图，带你真正搞懂redis数据类型的底层( 二 ) _redis

那问题来了“
hash算法是不能保证所有的key 经过算法出来的值都一样，那就是会有哈希冲突的存在，就是两个key放到了同一个桶中，这可怎么办呢？
”
我们就用链表来解决这个问题，就是两个在一个桶中的元素，我们就用一个next指针把它们连在一起，经过hash算出来之后找到一个键值对，对比看着如果不是，根据next指针再找下一个比就行。我们都知道链表是一种常用的数据结构，而C语言内部是没有内置这种数据结构的实现，所以我redis会自己构建了链表的实现。
其中每个
链表节点
使用一个listNode结构表示:(下图的右部分）：
//链表节点typedef struct listNode{struct listNode * prev;struct listNode * next;void * value;}下图是有两部分，由list和listNode两个数据结构构成。一部分是“ 统筹部分 ”是左边，一部分是“ 具体实施 “：右边；

文章插图

主体”统筹部分“：head指向具体双向链表的头
tail指向具体双向链表的尾
len双向链表的
长度
；
具体"实施方"：可以看出每个链表节点都有指向前置节点prev 和后置节点next 的指针，组成一个双向链表。每个链表结构，有表头表尾指针和链表长度等信息。另外表头节点和前置和表尾节点的后置都是NULL，所以是无环链表。
在总结下：
特点：

双端：链表节点带有prev和next指针，找到某个节点的前置节点和后置节点的时间复杂度都是O(N)
无环：表头节点的prev指针和表尾节点的next 都指向NULL，对立案表的访问时以 NULL为截止
表头与表尾：因为链表带有head指针和tail指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
长度计数器：链表中存有记录链表长度的属性**len
多态：链表节点使用void* 指针来保存节点值，并且可以通过list结构的dup 、free、match三个属性是节点值设置类型特定函数。

这时我们可以通过直接操作list来操作链表会更加的方便：

typedef struct list {//表头节点listNode* head;//表尾节点listNode* tail;//链表长度unsigned long len;//节点值复制函数void *(*dup) (void *ptr);//节点值释放函数void (*free) (void *ptr);//节点值对比函数int (*match)(void *ptr, void *key);}

“
那么当元素越来越多之后，一个哈希桶所对应的链表就会越来越长，我们知道链表上的遍历时间复杂度是O(n)的，那么会严重影响性能，Redis这种追求快的数据库看来是绝对不能够容忍的，那么要怎么处理，就是rehash操作。
”
rehash和渐进式rehash操作redis会在内部再新建一个长度为原始长度2倍的空哈希表，然后原哈希表上的元素重新rehash 到新的哈希表中去，然后我们再使用新的哈希表即可。
那么，这样还是有个问题要解决呀！
要知道redis中存储的数据可能是成百万上千万的，我们重新rehash 一次未免太耗时了吧，因为redis中操作大部分是单线程的。
“
这个过程可能会阻断其他操作很长时间，这是不能忍受的，那要怎么处理呢？
”
首先redis是采用了渐进式rehash 的操作，就是会有一个变量，指向第一个哈希桶，然后redis每执行一个添加key，删除key的类似命令，就顺便 copy一个哈希桶中的数据到新的哈希表中去，这样细水长流的操作，是不会影响什么性能，就会所有的数据都被重新hash到新的哈希表中。
那么在这个过程中，当然再有写的操作，会直接把数据放到新的哈希表中，保证旧的肯定有 copy完的时候，如果这段时间对数据库的操作比较少，也没有关系，redis 内部也有定时任务，每隔一段时间也会copy一次。
动态字符串SDSSDS的全称"simple dynamic string" 。redis中所有场景中出现的字符串，基本都是由SDS来实现的。
所有非数字的key。例如 set msg "hello world" 中的key msg.
字符串数据类型的值。例如 set msg "hello world"中的msg的值"hello wolrd"
最后是两者结合：
非字符串数据类型中的“字符串值”
。例如 RPUSH fruits "Apple""banana""cherry"中的"apple" "banana" "cherry"都是;
上面的例子，我们可以很直观地看到我们在平常使用redis的时候，创建的字符串到底是一个什么样子的数据类型。除了用来保存字符串以外，SDS还被用作缓冲区（buffer）AOF模块中的 AOF缓冲区。