On July 28, 2014 6:08:26 AM EDT, Niall Douglas
On 28 Jul 2014 at 13:26, Gavin Lambert wrote:
On 28/07/2014 03:20, Niall Douglas wrote:
* To insert or find an item involves determining the bucket from the modulus of the hash by the number of buckets, locking the bucket and scanning the linear list for an empty item or the right item as appropriate. We know empty items from a magic hash value which is defined to some magic constant (advice on the best magic hash value least likely to turn up from std::hash is welcome).
Isn't it by definition (admittedly reality is less ideal) that all hash values have equal probability? What happens if a real item does end up with the magic "empty" hash value? I think it'd be safer to have a separate flag for this case.
Firstly, if the magic hash value ever turns up during insert the program aborts :) It should, hopefully, be exceedingly rare on 64 bit to the point that we don't care [1].
I'd be hard pressed to trust a library that aborts if the possible, but exceedingly rare occurs.
Secondly, a separate flag costs another 8 bytes, and it ruins the cache line symmetry for AFIO where items size out to 32 bytes which is a lovely multiple.
A separate flag only costs one bit. You might yet be able to rethink your current data structure to free one. The worst case, add I see it, is that you simply increment (or decrement) a computed hash value should the magic value ever arise. That is, you increase the odds of a collision so that no value ever uses the magic value. ___ Rob (Sent from my portable computation engine)