Insertion algorithm in a nutshell:
1. Calculate hash value
2. Take 4 least-significant bits of the hash value. These tell you which
partition the value belongs to.
3. Lock that partition
4. Take the X (X > 4) least significant bits of the hash value. These
tell you which hash bucket the value belongs to.
5. Add value to that hash bucket. A bucket is implemented as a linked
list. Also called a "hash chain" in the README.
6. Unlock partition
Cui Shijun wrote:
> Ah... It seems that a item is calculated its hash value, get the bucket
> number from it and insert into that bucket "chain". The insertion has
> nothing to do with partition number(but Alvaro says "which hash is
> used depends on the partition number". I haven't really understood
> this: how can we get a hash value without deciding which hash to
> use? ). However, when we travel along a chain to get a item, we can
> infer its partition number from its hash value.
>
> My problem is, I'm not so sure about the process stated above,
> because in that way, items in ONE chain may belong to different
> partitions,and it is obviously conflicted with "so that different
> partitions use different hash chains" as README mentioned.
>
> 2007/4/28, Tom Lane <tgl@sss.pgh.pa.us>:
>
>> It's not that hard: the bucket number is some number of low-order bits
>> of the hash value, and the partition number is some smaller (or at most
>> equal) number of low-order bits of the hash value.
>>
>> regards, tom lane
>>
>
-- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
