从源码看redis的'map'结构
默认的map结构使用的是ziplist的编码方式，当超过hash_max_ziplist_value(默认64)时则会将编码方式替换成 OBJ_ENCODING_HT。",is_english:d,is_original:h,user_index:5.0206691216177,original_type:d,original_author:e,content:"
hset用来往map结构存入数据
> hset user:100 name paxi\n(integer) 1\nuser:100是整个map结构的key,name是map中的一项字段值，通过hget就可以获取存入的结果
> hget user:100 name\n"paxi"\nhset命令执行追踪
hset的执行入口在 hsetCommand
Code.SLICE.source("robj *o = lookupKeyWrite(c->db,key);")\n.interpretation("根据提供的dict本身的key，注意这里不是dict中元素的key,而是查找dict的key,比如 user:100 age 12 这里的key是 user:100");\n\nCode.SLICE.source("if (o == NULL) {\\n" +\n " o = createHashObject();\\n" +\n " dbAdd(c->db,key,o);\\n" +\n " } else {\\n" +\n " if (o->type != OBJ_HASH) {\\n" +\n " addReply(c,shared.wrongtypeerr);\\n" +\n " return NULL;\\n" +\n " }\\n" +\n " }")\n.interpretation("如果存在就仅校验是否是hash，满足条件返回；如果不存在就创建一个hash对象，并把这个key的关系存到了自己的db中");\nmap是不能存在key是一样的元素的，因而会先检查是否有同样的key,没有就再创建一个HashObject
Code.SLICE.source("unsigned char *zl = ziplistNew();\\n" +\n " robj *o = createObject(OBJ_HASH, zl);\\n" +\n " o->encoding = OBJ_ENCODING_ZIPLIST;\\n" +\n " return o;")\n .interpretation("默认创建的hash结构，它的编码方式使用的是ziplist");\n默认的map结构使用的是ziplist的编码方式，当超过hash_max_ziplist_value(默认64)时则会将编码方式替换成 OBJ_ENCODING_HT。
key存储
key这里指的是map整个结构的key,而不是map中的一个字段
为了方便区分分别以key和field区分，比如
user:100是整个map结构的key,name是map中的一项字段
从 lookupKeyWrite 和 dbAdd 追踪进去，key其实也是存在了一个dict的结构中
Code.SLICE.source("typedef struct dict {\\n" +\n " dictType *type;\\n" +\n " void *privdata;\\n" +\n " dictht ht[2];\\n" +\n " long rehashidx; /* rehashing not in progress if rehashidx == -1 */\\n" +\n " unsigned long iterators; /* number of iterators currently running */\\n" +\n "} dict;")\n .interpretation("字典结构")\n .interpretation("dictType使得redis可以对任意类型的key和value对应类型来操作")\n .interpretation("privdata存储用户传进来的值，key就是key,value就是value")\n .interpretation("dictht数组存储两个ht,在rehash的时候，ht[0]表示旧的，ht[1]表示新的，当rehash完成，再将ht[1]地址给ht[0]")\n .interpretation("rehashidx用来标识是否正在进行rehash,没有进行的时候是-1")\n .interpretation("iterators表示当前正在进行遍历的iterator的个数,如果要进行rehash，但是当前有迭代器正在进行遍历，不会进行rehash");\n注意到 dictht 和 rehashidx 这两个字段的存在，使得redis方便进行扩容，dictht是redis存储数据的地方，rehashidx用来表示，当前扩容到哪儿了，如果一个map的filed非常的多，那么扩容过程中需要的拷贝量非常大，所以redis选择了使用两个 dictht 来是想逐步的拷贝
field与value的存储
map结构首先存储的方式是使用ziplist,当数据过大，不适合ziplist的时候才选用 OBJ_ENCODING_HT,在存储的时候也需要对应的做不同的处理
//...\nCode.SLICE.source("if (o->encoding == OBJ_ENCODING_ZIPLIST){" +\n "..." +\n " if (hashTypeLength(o) > server.hash_max_ziplist_entries)\\n" +\n " hashTypeConvert(o, OBJ_ENCODING_HT);" +\n "}")\n .interpretation("根据编码方式来做不同的set,如果是 ZIPLIST,插入完成之后，会统计当前存储的个数，如果超过了 hash_max_ziplist_entries （512) 那么转换为 OBJ_ENCODING_HT ");\nCode.SLICE.source("} else if (o->encoding == OBJ_ENCODING_HT) {")\n .interpretation("处理 HashTable的编码方式");\nCode.SLICE.source(" dictEntry *de = dictFind(o->ptr,field);")\n .interpretation("在当前key对应的dict中去查找，有没有这个字段对应的值");\nCode.SLICE.source(" if (de) {\\n" +\n " sdsfree(dictGetVal(de));\\n" +\n " if (flags & HASH_SET_TAKE_VALUE) {\\n" +\n " dictGetVal(de) = value;\\n" +\n " value = NULL;\\n" +\n " } else {\\n" +\n " dictGetVal(de) = sdsdup(value);\\n" +\n " }\\n" +\n " update = 1;\\n" +\n " }")\n.interpretation("如果存在释放原来的dict中值的空间，插入新的值，并标识是更新");\n//...\nCode.SLICE.source("dictAdd(o->ptr,f,v);")\n .interpretation("将key和value加入到dict中");\n//...\n以HT为例，field存储之前，先要看容量是不是够,不够就需要先进行扩容
Code.SLICE.source("if (dictIsRehashing(d)) return DICT_OK;")\n .interpretation("如果已经在rehash了，那么不需要再次扩容");\nCode.SLICE.source("if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);")\n .interpretation("如果dict当前没有分配空间，默认扩容为为4个数组长度");\nCode.SLICE.source(" if (d->ht[0].used >= d->ht[0].size &&\\n" +\n " (dict_can_resize ||\\n" +\n " d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))")\n .interpretation("当已经使用的量不小于分配的量，并且比例已经超过默认占比(默认值为5)进行扩容或者可以进行resize");\nCode.SLICE.source(" return dictExpand(d, d->ht[0].used*2);")\n .interpretation("扩容为使用量的2倍");\n- size:分配的空间，也就是每个table的数组个数它一定是2的幂次方
- used:表示map中已经添加了的元素个数
当遇到满足的条件则进行扩容，扩容后再选择存储
Code.SLICE.source("if (dictIsRehashing(d)) _dictRehashStep(d);")\n .interpretation("如果dict正在执行Rehash先执行一步rehash");\nCode.SLICE.source("if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)\\n" +\n " return NULL;")\n .interpretation("计算出当前key在dict中的下标,如果在那个下标已经有这个key了，返回添加失败");\nCode.SLICE.source("ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];")\n .interpretation("根据是否在rehash来保证新的元素只会放在心的entry列表里面");\nCode.SLICE.source(" entry = zmalloc(sizeof(*entry));")\n .interpretation("分配新的entry的空间");\nCode.SLICE.source(" entry->next = ht->table[index];\\n" +\n " ht->table[index] = entry;\\n" +\n " ht->used++;")\n .interpretation("将新的entry放在第一个dict链表的第一位,并增加使用量");\nCode.SLICE.source(" dictSetKey(d, entry, key);")\n .interpretation("把key存入entry");\nfield按照上述方式存储完毕后，再存入value到dictEntry
结论
hash底部使用dict的结构存储,每个dict会自带当前的数据类型对应hash计算函数等，以及是否正在进行rehash，为了实现Rehash，它自己会有两个hash表的引用，每个hash表都存一个entry的数组，当遇到冲突的时候，就使用链表的方式来解决
附录
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
云数据库 Redis®
腾讯云数据库 Redis®（TencentDB for Redis®）是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备，提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
腾讯云开发者
