redis中的hash实现
典型的数据结构[*]hashtable的一个封装
typedef struct dict {
dictType *type; //函数集合
void *privdata;
dictht ht; //真正的hashtable，有两个的原因是在扩容以及rehash的时候使用
int rehashidx; //是否处于rehash状态，-1是不属于
int iterators; /* number of iterators currently running */
} dict;
[*]真正的hashtable
typedef struct dictht {
dictEntry **table; // slot数组指针，slot中存放元素
unsigned long size; //元素容量（实际就是hash中 slot的个数）
unsigned long sizemask;(实际就是元素hash取模的基数（size-1）)
unsigned long used; //已经存储的元素个数
} dictht;
[*]hashtable绑定的函数
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
[*]元素（链表结构，包含key和value以及下个元素的指针）
typedef struct dictEntry {
void *key;
void *val;
struct dictEntry *next;
} dictEntry;
见图
http://files.note.sdo.com/CQ4G7~jJo1R9nM1LA00Ezm
典型场景
[*]创建 （dict.c:dictCreate）
[*]分配内存
[*]设置绑定函数（dict->type）
[*]添加（dict:dictAdd）
[*]如果此时处于rehash状态,那么执行rehash(通常一步，下面会讲)
[*]通过dict:_dictKeyIndex返回slot索引（如果处于rehash状态,也会去遍历ht），如果key存在则返回-1
[*]此时会通过(dict:_dictExpandIfNeeded)来看是否有必要扩容，下面会重点谈
[*]仍然检查是否rehash状态，如果不是则将选择ht作为插入的table,否则选择ht
[*]上面的步骤已经确定插入哪个table以及哪个slot,此时开始给entry分配内存
[*]将新entry插入到链表的表头
[*]查找(dict.c:dictFind)
[*]如果ht为空，则返回null
[*]如果此时处于rehash状态,那么执行rehash(通常一步)
[*]计算key的hash值
[*]根据hash值确定slot(默认去找ht的slot)
[*]遍历slot链表去查找相应的key
[*]在ht中找不到key,如果此时处于rehash状态，那么再去查找ht
[*]扩容的整体过程
[*]扩容(dict:_dictExpandIfNeeded)
[*]如果此时处于rehash状态，返回
[*]如果ht为空，则扩展到初始尺寸（#define DICT_HT_INITIAL_SIZE 4）（slot数目为size-1）
[*]如果【ht的元素个数超过初始尺寸】 && （【允许扩容(默认允许)】 || 【使用比例(容纳的元素个数/初始尺寸）大于阀值(5)】），开始扩容，初始尺寸扩大为原来的2倍
[*]此时仅仅是设置rehash标识（见dict属性rehashidx）,并不迁移数据
[*]rehashidx为-1表示不处于rehash状态，当处于rehash状态(rehashidx>-1)时rehashidx表示ht待处理的slot索引（开始时是0）
[*]另外在事件循环中，每次处理时间函数时调用redis.c:serverCron->redis.c:tryResizeHashTables看是否需要扩容,扩容的标准是used>10*size
[*]在添加（dict:dictAdd）过程中会触发扩容操作
[*]rehash( dict:dictRehash)
[*]有了上面这个rehash标识，就可以进行rehash（迁移数据）
[*]迁移数据是指从ht-->ht
[*]迁移数据也并不是一次就全部完成，默认情况每次迁移一个或者一部分slot
[*]在访问过程中是一次迁移一个slot
[*]在事件循环中，每次处理时间函数是调用redis.c:serverCron->redis.c:incrementallyRehash来继续rehash,最多迁移100个slot，如果超过1ms，就停止迁移
[*]等ht全部迁移到ht,就切换ht到ht
[*]在添加（dict:dictAdd）、查找(dict.c:dictFind)过程中都会触发entry迁移
页:
[1]