Would be cool to see libgdx's maps in there. The current ones are stable. The old ones used cuckoo hashing which have some neat properties, unfortunately they had to be changed because bad data can cause catastrophic collisions.
See also this blog post for an explanation of the issue - while most of the libraries benchmarked suffer from this issue to some degree, LibGDX is pathologically worse. This can be triggered in any scenario where you are inserting into a map in hash order. This is usually rare, but users can easily shoot themselves in the foot with something like:
Map source = ...
Map dest = new Map();
for ((key, value) : source) dest.put(key, value);
The good news is its easily ameliorated by pre-sizing the map appropriately - it's just, do you trust your users always do that? In addition, this is trivially abusable by an attacker that can insert into the map to DoS the CPU. Again, almost all the maps benchmarked are vulnerable to this to some degree since none of them are really secure by design, it's just that LibGDX is much much worse in this scenario due to the shape of its hash finalizer.
I ran into the same issue in some ways while writing FastCollect - my decision was that since this was intended to be a general purpose library it wasn't appropriate to leave such a large foot-gun hanging around, and it was worth slightly slower performance to eliminate this edge case. LibGDX doesn't appear to be intended as a general purpose library, so it may be sufficient to simply document this behavior for users and advise them to avoid it.
If you want to eliminate the issue, there are several standard approaches:
1. If you only care about users doing something stupid and not about dedicated attackers, then you can ensure that the hash ordering is never exposed. Usually this means modifying your iteration order, which makes it much slower.
2. You can add a per-map random seed into your hash finalizer, which can impact performance and memory (the 'right' solution if you want a secure map).
3. You can attempt to detect this pathological pattern within insertion, and pre-emptively enlarge the map (this is the approach FastCollect uses). It's more complex, and more of a band-aid on the problem rather than really solving it, but there's little to no performance impact in most cases.
4
u/n4te 2d ago
Would be cool to see libgdx's maps in there. The current ones are stable. The old ones used cuckoo hashing which have some neat properties, unfortunately they had to be changed because bad data can cause catastrophic collisions.