快乐的天空

时间来得快,去得也快

 

redis 哈希表

hashtable的实现有很多,redis的dict.c 是其中之一。

redis_dict

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。

posted on 2012-08-01 17:28 探路者 阅读(307) 评论(0)  编辑 收藏 引用 所属分类: 学习笔记


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

新闻档案

Android

Compiler Course

VIM

编译技术集合

测试

高性能计算

个人博客

框架/组件/库

搜索

最新评论

阅读排行榜

评论排行榜