字典结构

typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2]; //哈希表  使用ht[0],ht[1]用于rehash
    int rehashidx; //当rehash不在进行时,值为-1；记录rehash进度
}dict;

hash值计算公式: hash = dict->type->hashFunction(key);

哈希表结构

typedef struct dictht{
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask; //哈希表大小掩码,用于计算索引值,总是size-1
    unsigned long used;
}dictht;

sizemask和哈希值一起决定索引值
index = hash & dict->ht[x].sizemask;

哈希表节点---即是 上述table属性

typedef struct dictEntry{
    void *key;
    union{
        void *val;
        unit64_t u64;
        int64_t s64;
    }v;
    struct dictEntry *next; //类似链表,解决bucket中 key 相同时,节点顺序索引
}dictEntry;

解决键冲突: 没有表尾指针,新节点添加到表头位置；

Rehash:
ht[1]分配空间
扩展 size>= ht[0].used *2 的2的n次方
收缩 size>= ht[0].used 的2的n次方
比如 used= 9; 扩展为 2的4次方 = 16；

执行扩展操作
1)没有执行bgsave 或 bgrewriteaof且负载因子>=1
2)正在执行bgsave 或 bgrewriteaof且负载因子>=5 (执行命令执行copy-on-write)提高扩展操作所需的负载因子，避免子进程存在期间进行哈希表扩展操作,节约内存

负载因子 = 哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used/ht[0].size
负载因子小于0.1时,程序自动执行收缩操作

渐进式rehash
靠rehashinx来控制执行进程
字典操作在rehash过程中同时在两个哈希表进行.(delete,find,update)
add操作只保存到ht[1]里,保证ht[0]包含键值对数量只增不减,随着rehash操作执行成为空表

redis使用murmurhash2 计算键的哈希值

« 每天读一点redis之SDS字符串 js查看,清除cookie »