前言
Hash也是Redis中非常常用的一种存储结构了，Redis的hash底层用到了两种存储结构，ziplist压缩列表 和 hash 表,当存储的所有键值对的键和值的字符串长度都小于64字节，且元素个数少于512个，Redis会选择ziplist存储，这样会比较省内存，否则他会选择hashtable hash表去成，这里的hash表它底层结构和Java中的HashMap比较像，都是数组+链表，链表是为了解决hash冲突。
dict底层结构
Hash的存储结构叫dict，译作字典，我们先睹为快
typedef struct dict {
/*类型*/
dictType *type;
/*私有数据*/
void *privdata;
/*2个哈希表，一个存储值，一个位空，哈希表进行rehash的时候才会用到第2个哈希表 */
dictht ht[2];
/*rehash目前进度，rehash的时候用，其他情况下为-1*/
int rehashidx;
/*目前正在运行的安全迭代器的数量*/
int iterators;
}dict;
dict中维护了2个 dictht ， 2个哈希表，一个存储值，一个位空，在哈希表进行rehash重新散列的时候才会用到第2个哈希表，rehash后面再说。看下dictht的结构
typedef struct dictht{
/ * 哈希表数组 */
dictEntry **table;
/ * 哈希表大小 */
unsigned long size;
/ * 掩码，用于计算索引值 : size-1 */
unsigned long sizemask;
/ * 哈希表已有节元素个数 */
unsigned long used;
}dictht
dictht中的 dictEntry **table; 是一个二维哈希表数组，是真正用来存储数据的，使用的是 dictEntry 类型,dictEntry 结构如下：
typedef struct dictEntry{
/* 键 */
void *key;
/* 值*/
union{
/*值*/
void *val;
/*无符号 64位整数*/
uint64_tu64;
/*有符号 64位整数*/
int64_ts64;
}v;
/* 指向下一个哈希表节点，形成链表*/
struct dictEntry *next;
}dictEntry
key是键，val是值，next是下一个hash节点的指针，形成链表。val可以存储64位带符号整数,和无符号整数，占8字节。
有了解过HahsMap底层实现的小朋友应该知道，HahsMap为了解决hash冲突(多个不同的key计算出相同的hash值，意味着他们要存储在hash表中的同一个索引位置，这个是不允许的)采用了链地址法。Redis的hash也是同样，这里的next是指向下一个hash元素，从而形成链表。这里梳理一下结构如图：
rehash重新散列
rehash重新散列指的是对hashtable进行扩容，或者缩容，当元素越来越多势必要扩展空间，当元素变少，多余的空间就是浪费，所以也要缩容。
Hash中 中元素满了就会以原来数组的 2 倍 扩容。但是如果 正在做 bgsave 持久化操作是不会去扩容,因为要减少内存页的过多分离(Copy On Write)。如果 Hash元素的个数达到了数组长度的 5 倍时Redis 会强制扩容。当元素慢慢减少就会缩容，缩容不受bgsave影响。缩容条件是元素个数少于数组长度的 10%
刚才看到在dict中有两个hash表 dictht ht[2]; ，平时存储数据的话就使用 dictht ht[0], dictht ht[1] 定义了结构不分配空间，当执行rehash时就会使用到dictht ht[1] 。redis的rehash不是一次性把ht[0]的元素全部复制到ht[1]，而是采用的是渐进式扩容，步骤如下：
- 为ht[1]分配空间
- 将rehashindex的值设置为0
- 在rehash期间，每次对字典执行增删改查操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1]，当rehash工作完成以后，rehashindex的值+1
- 随着字典操作的不断执行，最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1]，这时将rehashindex的值设置为-1，表示rehash操作结束
- 最后把 ht[0] 释放，把ht[1] 设置为 ht[0]以便下一次扩容
渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。
需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果index大于rehashindex，访问ht[0]，否则访问ht[1]。
ziplist和hashtable的选择
如果你还不知道什么是ziplist,点击这里了解，我们来看一下redis是如何选择ziplist和hashtable的，hset 命令源码如下：
void hsetCommand(redisClient *c) {
int update;
robj *o;
/ * 查找或创建哈希对象 */
if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
/ * [重要]如果需要的话，转换哈希对象的编码 */
hashTypeTryConversion(o,c->argv,2,3);
/ * 编码 field 和 value 对象*/
hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
/ * 把 field 和 value set到 hash ，这个函数里面会判断元素长度达到 512 选择ahsh*/
update = hashTypeSet(o,c->argv[2],c->argv[3]);
/ * 返回状态：显示 field-value 对是新添加还是更新*/
addReply(c, update ? shared.czero : shared.cone);
/ * 发布键修改通知*/
signalModifiedKey(c->db,c->argv[1]);
/ * 发布事件*/
notifyKeyspaceEvent(REDIS_NOTIFY_HASH,"hset",c->argv[1],c->db->id);
/ * 将服务器设为脏*/
server.dirty++;
}
根据hset命令的源码可以看出他做了这些事情
- 根据传入的key查找已有的hash对象，如果没有就创建一个hash对象(hashTypeLookupWriteOrCreate)
- 判断hash对象是使用zipList还是使用hashtable去存储(hashTypeTryConversion)
- 对hash对象进行编码，为了节约内存嘛(hashTypeTryObjectEncoding)
- 把 field 和 value 设置到 hash对象
- 发布修改通知和相关事件
接着我们看一下hashTypeTryConversion是如何选择存储类型的
void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
int i;
/ * 这里在判断编码，如果不是ziplist直接返回*/
if (o->encoding != REDIS_ENCODING_ZIPLIST) return;
for (i = start; i <= end; i++) {
/ * 检查元素的值的字符串长度是否超标 REDIS_HASH_MAX_ZIPLIST_VALUE 默认 64 */
if (sdsEncodedObject(argv[i]) &&
sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
{
/ * 值的长度超过 64，对象使用hash编码 REDIS_ENCODING_HT */
hashTypeConvert(o, REDIS_ENCODING_HT);
break;
}
}
}
从这里我们看到它的选择条件，判断元素的值的长度超过REDIS_HASH_MAX_ZIPLIST_VALUE 默认 64 就使用hash，还有一个判断在hashTypeSet函数中，源码如下：
int hashTypeSet(robj *o, robj *field, robj *value) {
int update = 0;
/* 判断编码为ziplist */
if (o->encoding == REDIS_ENCODING_ZIPLIST) {
unsigned char *zl, *fptr, *vptr;
/ * 解码field和value*/
field = getDecodedObject(field);
value = getDecodedObject(value);
/ * 这里在从ziplist中查找key,如果找到了就会删除旧的键值对，添加新的键值对*/
zl = o->ptr;
fptr = ziplistIndex(zl, ZIPLIST_HEAD);
if (fptr != NULL) {
/ * 找到 field*/
fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
if (fptr != NULL) {
/* Grab pointer to the value (fptr points to the field) */
/ * 找到值*/
vptr = ziplistNext(zl, fptr);
redisAssert(vptr != NULL);
/ * 更新操作*/
update = 1;
/* Delete value */
/ * 删除旧的*/
zl = ziplistDelete(zl, &vptr);
/* Insert new value */
/ * 添加新的*/
zl = ziplistInsert(zl, vptr, value->ptr, sdslen(value->ptr));
}
}
/ * 如果不是更新就是一个添加操作*/
if (!update) {
/* Push new field/value pair onto the tail of the ziplist */
/ * 将添加的键值对天爱到到 ziplist 的末尾*/
zl = ziplistPush(zl, field->ptr, sdslen(field->ptr), ZIPLIST_TAIL);
zl = ziplistPush(zl, value->ptr, sdslen(value->ptr), ZIPLIST_TAIL);
}
o->ptr = zl;
decrRefCount(field);
decrRefCount(value);
/ * 【重要】检查是否需要将 ZIPLIST 编码转换成 Hash编码，REDIS_HASH_MAX_ZIPLIST_ENTRIES 默认 512*/
/ * #define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512
if (hashTypeLength(o) > server.hash_max_ziplist_entries)
hashTypeConvert(o, REDIS_ENCODING_HT);
/ * 如果不是ZIPLIST 编码如果是hash编码*/
} else if (o->encoding == REDIS_ENCODING_HT) {
/ * 添加或修改键值对到字典*/
if (dictReplace(o->ptr, field, value)) {
/* Insert */
incrRefCount(field);
} else {
/* Update */
update = 1;
}
incrRefCount(value);
} else {
redisPanic("Unknown hash encoding");
}
return update;
}
梳理一下hashTypeSet的流程
- 判断对象的编码如果是REDIS_ENCODING_ZIPLIST就走ziplist添加/修改键值对，否则走hash添加/修改键值对
- 解码field和value,然后从ziplist中找到field和value
- 从zipList中删除旧的键值对，添加新的键值对
- 检查元素长度是否大于512，大于的话需要转码成REDIS_ENCODING_HT使用hash存储
文章结束，希望对你有所帮助，喜欢的话请给个好评吧！！！
