> "Not suprisingly, [...] global counters [...] are poorly distributed as well."
is true.
I mean, yes, they are not uniformly distributed, but that was never the requirement. As the article itself states, the desired property is that "the values for distinct objects are more or less distinct". With a global counter, you get maximally distinct hash codes. More distinct than any of the other approaches (and not less than any user-implemented function), at least until 2^31 object allocations.
Yes, after 2^31 objects you will get repeated values, but that is trivially the case for any pattern of assigning 31 bit hash codes to distinct objects (and any of the pseudo-random approaches will get birthday-paradoxed much sooner, and much harder). The only case where this could matter is in an adversarial scenario where someone is trying to DoS your hash map with crafted inputs. But according to the article itself, it would take 4+ minutes (120 ns * 2^31) of only allocating objects for each global counter wrapping. If an adversary can reliably achieve that already, what's the point in slowing down a hash map by an epsilon every four minutes?
> the values for distinct objects are more or less distinct
I think these words of author understate the requirement of good distribution of hash codes. As far as I understand, ideally the hash codes for different objects should be as distinct as practically possible, so that they are often put into separate buckets of a hash table.
Consecutively allocated objects will have almost all bits of their addresses equal.
One neat trick could be to use a linear congruential generator to iterate through the 32-bit integers without repetition, as long as you choose the right parameters. Fortunately, these are relatively simple to pick [1] when we're dealing with powers of two.
This would give you fairly easy-to-generate IDs which still have a period of 2^32 but where subsequent allocations have an ID that shares fewer bits on average with its predecessor.
I wouldn't trust any hash table where a hash function yielding consecutive integers would inherently lead to bad behavior. Can you tell me a popular hash-to-bucket reduction that performs badly for this case?
I will concede that there are plenty of schemes where insufficient entropy in lower bits causes problems. Combining those with the global counter hash and e.g. only inserting every 64th allocated object could be a failure case indeed. But this is still simple to defend against in the reduction scheme.
I think its about the naive "rep_array[hashcode(obj) % bucket_size] = object" which is all too common.
If your rep_array is doing linear probing and/or robin-hood hasing, then incremental hashcodes (such as 1, 2, 3, 4, 5...) is a bad thing. Especially if you're doing both inserts and removals: this sort of incremental pattern would lead to many "runs" where linear probing would perform poorly.
Of course, it isn't very hard to do rep_array[(hashcode(obj) * large_constant_odd_number) % bucket_size] instead and get a good distribution. But the question is whether or not people know about those kinds of steps.
Does it also happen in practice where the crafted inputs are given at minimum 4 minutes apart, on the precondition that those minutes are filled with finely-controlled-by-the-attacker spinning?
People are obsessed with that siphash paper, and they're obsessed that Java hashcodes do not do the siphash mitigation, but I don't know if any of it matters. People are obsessed with thinking it matters though.
> "Not suprisingly, [...] global counters [...] are poorly distributed as well."
is true.
I mean, yes, they are not uniformly distributed, but that was never the requirement. As the article itself states, the desired property is that "the values for distinct objects are more or less distinct". With a global counter, you get maximally distinct hash codes. More distinct than any of the other approaches (and not less than any user-implemented function), at least until 2^31 object allocations.
Yes, after 2^31 objects you will get repeated values, but that is trivially the case for any pattern of assigning 31 bit hash codes to distinct objects (and any of the pseudo-random approaches will get birthday-paradoxed much sooner, and much harder). The only case where this could matter is in an adversarial scenario where someone is trying to DoS your hash map with crafted inputs. But according to the article itself, it would take 4+ minutes (120 ns * 2^31) of only allocating objects for each global counter wrapping. If an adversary can reliably achieve that already, what's the point in slowing down a hash map by an epsilon every four minutes?