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.