Redis学习 -- 常用数据结构

二、链表

链表的声明与实现在/src/adlist.h、/src/adlist.c中

十年的高碑店网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。全网营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整高碑店建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联公司从事“高碑店网站设计”,“高碑店网站推广”以来，每个客户项目都认真落实执行。

//双向链表
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

//每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

通过为链表设置不同的类型特定函数，Redis的链表可以用来保存各种不同类型的值

三、字典

字典的声明与实现在src/dict.h、src/dict.c。字典是redis的底层基础，对数据库的增删改查也是构建在对字典的操作之上的

在源码注释中，字典叫哈希表（hash table)，实现了insert/del/replace/find/get-random-element 这些操作，使用链式法处理哈希冲突

重要结构体定义：

• 哈希表节点实体

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* 同一个篮子的下一个Entry */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
} dictEntry;

• 类型方法接口

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

• 哈希表结构实现

struct dict {
    //dictType 包含了一系列的用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同de
    dictType *type;
    //dictEntry结构保存着一个键值对。通常只使用ht_table[0],只有在对ht_table[0]进行rehash时，才使用ht_table[1]
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    //rehashidx 记录rehash的进度，没有进行rehash时为-1,另外，负载因子设定为1.618，在server.h中定义
    long rehashidx;
    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* size的指数 (size = 1<

typedef struct intset {
    uint32_t encoding;      //编码方式
    uint32_t length;        //包含的元素数量
    int8_t contents[];      //保存元素的数组
} intset;

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);    //当前编码
    uint8_t newenc = _intsetValueEncoding(value);   //新元素编码
    int length = intrev32ifbe(is->length);   //intrev32ifbe()是一个宏，只有在目标主机是大端序的时候会转换为小端序
    int prepend = value < 0 ? 1 : 0;             //判断元素位置

    /* 修改intset编码并重新分配内存 */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);     

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));   //秒啊，如果prepend为1，前面就会空出来位置放新元素，否则后面空出来

    /* 因为引发升级的新元素总是比该intset的所有元素长度都大，所以要么会放在最开头，要么放在最末尾 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}