Re: beansdb的hash算法

[Davies Liu]

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