hash底层的存储结构包括ziplist(压缩列表)或hashtable(哈希表)
hash在同时满足以下两个条件的时候会使用ziplist(压缩列表):
哈希对象保存的键值对数量小于512个
哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
压缩列表数据结构参考压缩列表章节,下图是hashtable的数据结构
redis的hash数据结构
Redis的Hash储存数据的步骤是:
1.hash = dict->type->hashFunction(k0)// 计算hash值,底层使用MurmurHash3算法
2.index = hash & dict->ht[0].sizemask// hash值与字典的ht[0]的sizemask与操作得到储存索引
上图中K0和K1计算的hash值相同,发生hash碰撞,若发生碰撞Redis采用的是链地址法解决冲突,并使用头插法(头先插入新哈希表,尾后插入)的方式,Jdk1.7也是使用头插法(多线程下有死链问题),而Redis是单线程的所以不存在死链问题
下图是具体的代码关键部分:
