4 ms·
Random Hash Functions (2012)
- coderholic 14y agoPosted on April 1st, 2012
- CJefferson 14y agoWhile that's true, it is also interesting how badly hash tables perform if you can fill them with NaNs. A quick prod tells me that g++'s unordered hash tables have the same bug.. interesting.
- cpressey 14y agoApril's fools aside, "m[NaN] = 1 always creates a new hash table element (since the key is unequal to any existing entry), reading m[NaN] never finds any data (same reason), and iterating over the hash table yields each of the inserted NaN entries." This suggests to me an ADT that special-cases insert on the key: if it's not NaN, put it in a hash table, but if it is, tack it onto (say) a plain linked list. Lookup NaN fails, traversing the structure traverses both the hash table and linked list. Might be a bit more code than a straight-up hash table, but definitely less weird than calling rand in the hash function. (To me.)