Redis数据结构之hash对象
Redis对象
在了解Redis数据结构的时候我们会学习到简单动态字符串，压缩链表等。
但Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。Redis使用对象表示键和值，每次新建一个键值对时，我们就创建了两个对象。
hash对象
ziplist编码
新建一个key为hash，键值对为name，tom的hash对象。它的编码为ziplist
127.0.0.1:6379> hset hash name "tom"
(integer) 1
127.0.0.1:6379> type hash
hash
127.0.0.1:6379> object encoding hash
"ziplist"
ziplist编码的hash对象ptr就指向一个压缩链表
压缩链表存储hash对象内容的结构如下
hashtable编码
哈希对象保存的所有键值对的键和值的字符串长度都大于64字节或者哈希对象保存的键值对数量大于512个时，hash对象的编码会自动转换为hashtable，当然这两个值都可以在redis.conf文件中进行修改(hash-max-ziplist-value选项和hash-max-ziplist-entries)。这时hash对象的结构是这样的
ptr指向一个字典，字典的每个键都是一个string对象，保存了键值对的键，字段的每个值也是一个string对象，保存了键值对的值。图中也只是抽象化的字典结构，接下来介绍下redis对于字典的底层实现。
redis字段所使用的hash表结构
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
//总是等于size-1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，也即是table数组的大小，而used属性则记录了哈希表目前已有节点（键值对）的数量。sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。
一个空的hash表
dictEntry*[4]是一个数组，数组里的每一元素都指向一个dictEntry结构，dictEntry包含3个属性，key，value，发生散列冲突时指向下一个节点的指针next。结构如下，看得出是使用链地址法解决散列冲突。
redis的字典是通过hash表来实现的
redis字典结构
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
//当rehash不在进行时，值为-1
in trehashidx;
/* rehashing not in progress if rehashidx == -1 */
} dict;
type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：·type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。·而privdata属性则保存了需要传给那些类型特定函数的可选参数。
而redis字典保存两个hash表，当我们新建一个redis字典时，默认使用ht[0] hash表，结构如下
redis字典为什么要维护两个hash表？
redis字典为了控制创建的hash表的空间开销，redis会动态调整hash表的空间大小，当ht[0]的长度满了，这里的ht[0]满了并不是指dictEntry数组里面每一个元素都存储了一个dictEntry，而是dictht的used和size相同，可能有部分dictEntry会发生散列冲突的。
此时再向字典添加元素，此时redis字典就会进行扩容。
首先对ht[1进行扩容，扩容的大小为比当前当前容量大的2的n次方，目标大小必须为2的n次方，这样系统进行内存分配的效率才有保证，比如当前容量ht[0]的容量为4，那么扩容的大小就应该为2的3次方也就是8.再将ht[0]的内容迁移到ht[1]此时redis字典的结构如下
这样就可以减少hash表的内存占用，不够的时候就扩容hash表。这种方法虽然节约了内存，但如果hash表已经很长了的时候，此时再扩容它的内存再分配的规模可能就会很大，造成性能影响。因此，为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]。
以下是哈希表渐进式rehash的详细步骤：
1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的加一。
4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
hash对象的相关命令