Redis中的字典

Redis中的字典

  • Redis中的字典使用哈希表作为底层实现,一个哈希表中可以有多个哈希表结点,而每个哈希表结点保存了字典中的一个键值对。
  • 相当于C++中的unordered_map
  • 相当于Java中的HashMap

哈希表的负载因子

负载因子 = 哈希表已保存节点数量 / 哈希表大小

使用位操作(&运算)代替求余操作

位运算比较高效,当size为2的n次方时,下面两个公式是等价的:

  • hash % size
  • hash & (size - 1)
    在Redis中使用位与运算计算键的索引值:
hash = dict->type->hashFunction(k0); // 计算键k0的哈希值
index = hash & dict->ht[0].sizemask; // 计算键k0的索引值,其中,sizemask等于size-1,size即为哈希表容量

在JDK7中也是使用位与运算计算键的索引值:

static int indexFor(int h, int length) {
  return h & (length - 1); // 相当于h % length
}

参考

  • 《redis设计与实现(第二版)》
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容