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.
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk