有书共读：《Redis设计与实现》第三章和第四章读书笔记
第3章：链表
链表节点：
链表节点：
typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}listNode;
链表：
typedef struct list{
listNode *head;
listNode *tail;
unsigned long len;
void *(*dup) (void* ptr);
void (*free) (void *ptr);
int (*match) (void *ptr,void *key);
}list;
Redis的链表实现的特性：
1）双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
2）无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问都以NULL为终点
3）带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)
4）带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)
5）多态：链表节点使用void *指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
第4章：字典
字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。
Redis的字典实现使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。每个字典带有两个哈希表，平时使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。
当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash（重新散列）到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成。
投递百度等公司10个岗位 >
