这篇博客我们就来讲讲redis的字典数据结构。
本节内容主要包括：
1.字典的数据结构
2.字典的扩容机制
Redis字典底层采用的是哈希表的数据结构来实现的。
dictht{
//哈希表数组
dictEntry **table;
//哈希表的大小
long size；
//哈希表大小掩码，用于计算索引值，总是等于 size-1
long sizemask;
//该哈希表中已有节点的数量
long used;
}dictht;
记住这个结构，总共有四个属性。
哈希表节点用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：
dictEntry{
void * key;//键
//值
union{
void *value;
}
dictEntry *next;
}
字典的表示
dict{
//类型特定的函数
dictType *type;
//私有数据
void *privateData;
//哈希表
dictht ht[2];
//rehash索引，当rehash不在进行时，值为-1，
int trehashidx;
}
dictType{
//计算哈希值的函数
int hashFunction(key);
//复制的函数
void valDup(void privateData,void obj)；
//对比键的函数
int keyCompare(void privateData,void key1,void key2)
}
注：详情参考《redis设计与实现》的第四章
一个普通的字典如下所示：
Q:如何计算索引值
hash=dict->type->hashFunction(key)
index=hash&dict->ht[x],sizemask
Q:如何解决键冲突
链表，和java的hashMap类似
Q:什么是渐进式rehash?
redis利用渐进式rehash方式进行扩容或者缩容。
具体步骤如下：
1.为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2.在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash正式开始
3.在rehash进行期间，每次对字典执行添加，删除，查找或者更新操作时，程序出了执行特定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]上，当rehash工作完成后，程序将rehashidx的值加1.
4.随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]上，这时程序将rehashidx的值设为-1，表示rehash操作完成。
注意：（1）在rehash期间执行更新，删除和查找操作会在两个哈希表上进行，ht[0]上没有就去ht[1]上去找
(2)至于添加的操作只会在ht[1]上进行，这样可以确保ht[0]上的键值对数量只减少不增加。
思考题：为什么使用渐进式rehash方法进行扩容？