redis源代码分析 – hash table
hashtable的实现有很多，redis的dict.c 是其中之一。
dict 包含了2个dictht hashtable ht[0], ht[1]。
client版本的dict是没有dictht的概念。加入dictht的概念存在2个ht的目的是为了在rehash的时候可以平滑的迁移bucket里的数据，而不像client的dict要把老的hash table里的一次性的全部数据迁移到新的hash table，这在造成一个密集型的操作，在业务高峰期不可取。
ht是hashtable的简称，实际上是一个指针数组，数组的个数由dictht->size决定，是DICT_HT_INITIAL_SIZE的整数倍。每个元素（bucket）指向一个dictEntry的单链表来解决hash的conflict。查询某个key，需要先hash，定位到bucket,再通过链表遍历。
key经过hash函数后，与dictht->sizemask求与均分到ht的每个bucket上。dictht->used表示这个ht里包含的key的个数，也就是dictEntry的个数，每次dictAdd成功+1。链表的加入为头指针的方法加入，这样dictAdd更加的方便。
随着key不断的添加，bucket下的单链表越来越长，查找、删除效率越来越低，需要对ht进行expand，增加bucket个数，让链表的长度减少。bucket数量的增多，原有bucket的key需要迁移到新的bucket上，于是有了rehash的这个过程。
ht[1]就是为了rehash而产生，新的ht size是ht[0]的两倍2， 随着dictAdd，dictFind函数的调用，ht[0]的每个bucket会rehash加入到ht[1]里。dict->rehashidx 是ht[0] 需要rehash就是迁移到ht[1]的bucket的索引，从0开始直到ht->used==0。
rehash除了每次伴随dictAdd，dcitFind而迁移一个bucket的所有dictEntry，还有一种一次hash100个bucket，直到消耗了某个时间点为止的做法。
rehash的步骤：
拿到一个bucket， 遍历这个链表的每个kv，对key进行hash然后于sizemask求与，定位ht[1]的新bucket位置，
加入到链表，迁移后ht[0].used–，ht[1].used++。
直到ht[0].used=0，释放ht[0]的table，再赋值ht[0]= ht[1]，再把则ht[1]reset。
rehash的期间：
由于ht[1]是ht[0]size的2倍，每次dictAdd的时候都会rehash一次，不会出现后ht[1] 满了，而ht[0]还有数据的事情。
查询会先查ht[0]再查询ht[1]，在rehash的过程中，不会出现再次expand。
新的key加到ht[1]。
expand的条件：
table的位置已经满了，糟糕的hash函数造成的skrew导致永远不会expand。
key的个数除以table的大小，超过了dict_force_resize_ratio。
很高兴读到你的文章，我也在分析redis的代码。
我有个疑问是，ht[1]的size一定是ht[0]的2倍吗？ 我觉得也可以是四倍或二分之一等等？？
你回复我的话，请给我的邮箱发信吧。
谢谢
/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
i *= 2;
}
}
你的邮箱是多少？
不好意思哈，之前不會用 LEAVE A REPLY, 原以為會把我提供的郵箱顯示出/
2.4.0-rc8
redis.c:425
// REDIS_HT_MINFILL 默認是10%
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size && used && size > DICT_HT_INITIAL_SIZE &&
(used*100/size < REDIS_HT_MINFILL));
}
/* If the percentage of used slots in the HT reaches REDIS_HT_MINFILL
* we resize the hash table to save memory */
void tryResizeHashTables(void) {
int j;
for (j = 0; j < server.dbnum; j++) {
if (htNeedsResize(server.db[j].dict))
dictResize(server.db[j].dict);
if (htNeedsResize(server.db[j].expires))
dictResize(server.db[j].expires);
}
}
對上面代碼的理解：
當刪除一些key時，hash的size應該減小，這樣可以減少內存消耗; 但對於Hash數據結構可能沒有太大必要，因域的數目變化不大; 但對於top-LeveL的hash結構可能就必需/
受益很多！本人一直从事java服务器端开发，最近想通过阅读redis源码来把c语言拾起来！
你的博客不能访问阿。
你是什么意思？
？
It’s always a plaesure to hear from someone with expertise.
我比较关注redis的底层存储结构，不知楼主是否研究过。
除了比较怪异的skiplist，所有的数结我都研究过。
hoterran 说道：
2011/12/04 18:30
除了比较怪异的skiplist，所有的数结我都研究过。
你好 ，可否交流交流。
musicode # gmail.com
@hoterran
都可以。
请教2个问题：
1. redis-2.4.6/src/dict.c:333
static int dictGenericDelete(dict *d, const void *key, int nofree) { ... if (!nofree) { dictFreeEntryKey(d, he); dictFreeEntryVal(d, he); } zfree(he); ... }为何这里要设置nofree模式？ 这样nofree=1时释放dictEntry结构的时候不就会使得he->key和he->val变成野指针?
2. redis-2.4.6/src/dict.c:531
static int _dictExpandIfNeeded(dict *d) { ... if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2); } ... }在调用dictExpand函数的时候，再判断一下d->ht[0].size > d->ht[0].used的大小有另外的作用吗？不是if语句中已经确定d->ht[0].used >= d->ht[0].size成立了吗?
搭车同疑。2 感觉是疏忽吧，@timebug去github提个pull request问问看
1 里边 nofree=1 的情况没有一处调用 (dictDeleteNoFree 没有在任何地方用到)，09年的第一个commit就有了，所以貌似也是疏漏。
请问在dictRehash中，为什么在对key进行hash后要跟sizemask求与呢？
sizemask是bucket的个数，hash之后要分到bucket里，和求模一样只不过位操作速度快。
1，rehash是在add或者find时，那如果一个key生成之后一直没有用过的话，这时怎么避免rehash一直没能完成？还是我理解有问题。。。
2，rehash时内存占用是呈指数型增长，这时如果内存用完了怎么办？会不会有一个机制直接把swap用上？
ps:还没真正读过redis源码，有空也读读
1. rehash是针对所有的kv记录而不仅仅是使用key.
2. rehash不是呈指数增长,仅仅是两倍.内存完了目前仅仅依赖os的swap
[...] ===data model implementation=== Full!!! — http://www.searchtb.com/2011/05/redis-storage.html key point, but not specific and precise — http://qing.weibo.com/tj/88ca09aa33000cy2.html ziplist — http://blog.nosqlfan.com/html/3919.html ppt — http://www.slideshare.net/iammutex/redis-9948788 hashtable — http://www.hoterran.info/redis_dict [...]
留言,表示感谢.
[...] 1.REDIS源代码分析 – HASH TABLE [...]