Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)

Subject: Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)
From: Slawomir Lisznianski (sl_at_[hidden])
Date: 2010-03-02 17:42:20

Daniel Trebbien wrote:

> I spent some time trying to understand the secret of this property,
> and came up with a description of the problem and solution which I
> thought was helpful.
>

Although I disagree with your conclusion that the container as-is doesn't
guarantee perfect hashing, your posting was very insightful. Please read on
why I think so.

  1. In order to maintain the "perfect" property, the size of the store
> only needs to be a multiple of the initial size.
>

Correct. The container grows exponentially, that is:

a) SIZE_new = SIZE_prev * 2

where the initial size is a multiple of 2.

Specifically, the constructor establishes the initial size as:

double target_cap = (1 << key_type(ceil(log(capacity_hint)/log(2))));

Subsequently, the container grows exactly following the formula (a):

double target_cap = store_.capacity() << 1;

after it fails to obtain a free slot or the load_factor tells it so.

  2. Special support from the container is needed so that the size of
> the store is always a multiple of the initial size and rehashing is
> performed correctly.
>

I agree. The container does not allow users to influence its size past
construction, ensuring the invariant of perfect hashing stays.

Given the conditions 1 and 2 from your posting are met by the container's
present implementation, I believe there is no problem.

-sl