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: Daniel James (daniel_james_at_[hidden])
Date: 2010-02-23 07:06:31

On 21 February 2010 20:59, Slawomir Lisznianski <slisznia_at_[hidden]> wrote:
> http://svn.boost.org/svn/boost/sandbox/tokenmap/libs/tokenmap/doc/html/index.html
>
> A tokenmap is a data structure that uniquely maps pseudo-random
> generated keys with elements of the collection.

I think it looks useful. I have some comments.

It looks like the code for finding a free slot could get slow as the
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 a
linked list of free slots. There would be an additional cost when
creating and resizing the container, but I think inserting should be
faster and it would avoid the need for a load factor.

It would also be useful to be able choose the random number generator,
probably using Boost.Random, as your generator doesn't look very
strong. It might also be useful to able to obfuscate the key by some
means, so that the index isn't exposed. A single customization point
might be useful; say, a stateful object with two functions, one which
takes an index and capacity and returns a token, and one which takes a
token and capacity and returns an index (with a suitable guarantee
that the index would be unique for larger capacities). That might
overcomplicate things though, since obfuscation could be done outside
of the container.

Daniel