Re: beansdb的hash算法

66 views
Skip to first unread message

Davies Liu

unread,
May 3, 2012, 10:34:37 PM5/3/12
to 方栋, bea...@googlegroups.com
2012/5/4 方栋 <fang...@pipul.org>
Hi,前辈

最近在阅读beansdb的源代码。感觉不是很理解。
static const int g_index[] = {0, 1, 17, 289, 4913, 83521, 1419857, 24137569, 410338673};
请问这里面的g_index[]数据,是不是指,如果堆有多少层,就能容纳多少个node,
 
差不多是这个意思,更准确的说法是 g_index 表示每层的起始位置,
每一层跟上一层是可以有空间限制的。
 
比如当堆只有1层的时候,g_index[1]=1,堆只能容纳下1个node
当堆只有两层的时候,g_index[2]=17,相当与 1 + 16
但是为什么当 g_index[3] = 289 但是 不等于 1+16+16^2=273呢?
 
为了简单期间,直接使用了 17 的N此方来做近似,浪费的内存是可以忽略的。

再说,如果g_index里的数字不是我上面说的意思的话,为什么在做enlarge_pool的时候是
int new_size = g_index[tree->height + 1];呢?这个不就是堆的容量吗

谢谢

------------------
祝好
--方(tyut)
 



--
 - Davies
Reply all
Reply to author
Forward
0 new messages