一 Redis数据结构-Redis的数据存储及String类型的实现 _生活百科

1 引言Redis作为基于内存的非关系型的K-V数据库。因读写响应快速、原子操作、提供了多种数据类型String、List、Hash、Set、Sorted Set、在项目中有着广泛的使用，今天我们来探讨下下Redis的数据结构是如何实现的。
2 数据存储2.1 RedisDBRedis将数据存储在redisDb中，默认0~15共16个db 。每个库都是独立的空间，不必担心key冲突问题，可通过select命令切换db 。集群模式使用db0
typedef struct redisDb {dict *dict; /* The keyspace for this DB */dict *expires; /* Timeout of keys with a timeout set */...} redisDb;

dict：数据库键空间，保存着数据库中的所有键值对
expires：键的过期时间，字典的键为键，字典的值为过期事件UNIX时间戳

2.2 Redis哈希表实现2.2.1 哈希字典dict
K-V存储我们最先想到的就是map ，在Redis中通过dict实现，数据结构如下：

typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */unsigned long iterators; /* number of iterators currently running */} dict;

type：类型特定函数是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数， Redis会为用途不同的字典设置不同的类型特定函数。
privdata：私有数据保存了需要传给那些类型特定函数的可选参数
ht[2]：哈希表一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0] 哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
rehashidx：rehash 索引，当rehash不在进行时，值为 -1

hash数据存在两个特点：

任意相同的输入一定能得到相同的数据
不同的输入，有可能得到相同的输出

针对hash数据的特点，存在hash碰撞的问题，dict通过dictType中的函数能够解决这个问题
【一 Redis数据结构-Redis的数据存储及String类型的实现】

typedef struct dictType {uint64_t (*hashFunction)(const void *key);int (*keyCompare)(void *privdata, const void *key1, const void *key2);...} dictType;

hashFunction：用于计算key的hash值的方法
keyCompare：key的值比较方法

2.2.2 哈希表 dictht
dict.h/dictht表示一个哈希表，具体结构如下：
typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;} dictht;

table：数组指针，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
size：记录了哈希表的大?。簿褪莟able数组的大小，大小总是2^n
sizemask：总是等于size - 1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。
used：记录了哈希表目前已有节点（键值对）的数量。

键值对dict.h/dictEntry

typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;} dictEntry;

key：保存着键值对中的键(SDS类型对象)
val：保存着键值对中的值，可以是一个uint64_t整数，或者是一个int64_t整数，又或者是一个指针指向一个被redisObject包装的值
next：指向下个哈希表节点，形成链表指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题

使用hash表就一定会存在hash碰撞的问题，hash碰撞后在当前数组节点形成一个链表，在数据量超过hash表长度的情况下，就会存在大量节点称为链表，极端情况下时间复杂度会从O(1)变为O(n)；如果hash表的数据再不断减少，会造成空间浪费的情况。Redis会针对这两种情况根据负载因子做扩展与收缩操作：