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 (slisznia_at_[hidden])
Date: 2010-02-23 09:12:36

Daniel James wrote:
> index fills up. I suppose a small load factor would help, but a better
> alternative might be to use the pointers in empty slots to maintain

sounds really good.

fyi, in early tests under various load factors and usage scenarios,
the insertion times don't appear to be affected much at all, as long
as the 0.5 < load_factor < 0.7 condition is met (less than 0.5 doesn't
help much, only wastes space).

> creating and resizing the container, but I think inserting should be
> faster and it would avoid the need for a load factor.

agree

> It would also be useful to be able choose the random number generator,

absolutely. consider the one there for "demo" purposes, plus it
allowed me to come up with a proof of concept that has no external
dependencies.

as a side note, the final generator should adopt to the token-type
template param, as different key sizes ask for different (in
complexity) hashing.

> probably using Boost.Random, as your generator doesn't look very
> strong.

it shows decent distribution. btw, it's based off of research done by
Thomas Wang, http://www.concentric.net/~Ttwang/tech/inthash.htm

I agree that in the end, one should be able to plug an external
generator which is adaptive and more robust.

> It might also be useful to able to obfuscate the key by some
> means, so that the index isn't exposed.

as a side note, if you let the container "grow", the index and random
parts are indistinguishable. unfortunately, there is some cost to
doing that, as opposed to starting with a sufficiently large container
(using capacity hint) at which point the index part becomes fairly
obvious.

> that the index would be unique for larger capacities). That might
> overcomplicate things though, since obfuscation could be done outside
> of the container.

that's how I'd typically solve it too, by using external obfuscation
strategy of sort.

Thanks.