3 ms·
It is often useful to have integer-keyed associative arrays; or, if you prefer, sparse positional arrays. In either case, a hash table is often the most optima
by moonchild 5y ago
It is often useful to have integer-keyed associative arrays; or, if you prefer, sparse positional arrays.
In either case, a hash table is often the most optimal implementation strategy. And unless the keys are guaranteed to be evenly distributed, the identity is an asymptotically bad hash function.
- junon 5y agoBut the hash still produces sparse outputs, it has some degree of avalanche effect does it not? In which case, wouldn't the hash function produce worse results w.r.t. cache misses?
- moonchild 5y agoI am not sure what you're getting at. Are you unfamiliar with hash tables as a data structure? If your keys are maximally clustered then you can use an alternate dense representation. Otherwise, using a hash table with the identity hash function will likely result in many collisions.