数据结构-字典

字典可以说是redis一个很常用的结构了，平时我们

执行命令 SET msg “hello world”

就是用的redis的的字典，存储键值对 msg—>"hello world" （键不能重复）

Java的同学一定知道HashMap，在redis，他采用c也写了这样的一套，每个哈希表都是一个链表的结构，结构相对Hashmap，又那么一些类似

typedef struct dictht{
    //链表
    dictEntry **table;
   //大小
    unsigned long size;
    // 用于计算索引，总数等于size-1
    unsigned long sizemask;
    //已经使用节点数量
    unsigned long used;

} dictht

而每个节点的结构

typedef struct dictEntry{
  //键
    void *key;
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
     } v;

    //下一个节点
   struct dictEntry *next ; 
} dictEntry

key记录键，v记录值，值得一提 v为：
void *val;
uint64_t u64;
int64_t s64;

三者取其一

next是为解决哈希冲突产生的，发生冲突的时候就拉链

画个图表示：
图片说明
上图为一个大小为4的空哈希表，next指针连接的k1发生了哈希冲突

注意这里采用头插法（新插入的节点在前）

数据结构-跳表

//每个节点 
typedef struct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //对象成员
    robj *obj;

    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsgined int span；
    }
}zskiplistNode
//整个链 
typedef struct zskiplist{
    //略
}

跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义，

其中 zskiplistNode 结构用于表示跳跃表节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针。

图片说明

展示了一个跳跃表示例，位于图片最左边的是 zskiplist 结构，该结构包含以下属性：

header ：指向跳跃表的表头节点。
tail ：指向跳跃表的表尾节点。
level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

位于 zskiplist 结构右方的是四个 zskiplistNode 结构，该结构包含以下属性：

层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到，所以图中省略了这些部分，只显示了表头节点的各个层。

《Redis设计与实现》读书笔记

数据结构-字典

数据结构-跳表