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设计与实现(第二版)》
网友评论