Redis中的字典
- Redis中的字典使用哈希表作為底層實(shí)現(xiàn)息罗，一個(gè)哈希表中可以有多個(gè)哈希表結(jié)點(diǎn)才沧，而每個(gè)哈希表結(jié)點(diǎn)保存了字典中的一個(gè)鍵值對(duì)。
- 相當(dāng)于C++中的
unordered_map糜工。 - 相當(dāng)于Java中的
HashMap录淡。
哈希表的負(fù)載因子
負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小
使用位操作(&運(yùn)算)代替求余操作
位運(yùn)算比較高效，當(dāng)size為2的n次方時(shí)刨裆，下面兩個(gè)公式是等價(jià)的：
hash % size-
hash & (size - 1)
在Redis中使用位與運(yùn)算計(jì)算鍵的索引值：
hash = dict->type->hashFunction(k0); // 計(jì)算鍵k0的哈希值
index = hash & dict->ht[0].sizemask; // 計(jì)算鍵k0的索引值彬檀，其中，sizemask等于size-1努潘，size即為哈希表容量
在JDK7中也是使用位與運(yùn)算計(jì)算鍵的索引值：
static int indexFor(int h, int length) {
return h & (length - 1); // 相當(dāng)于h % length
}
參考
- 《redis設(shè)計(jì)與實(shí)現(xiàn)(第二版)》
