Hash Codes, Non-Determinism, and Other Eldritch Horrors

https://verdagon.dev/blog/generics-hash-codes-horrors

by GarethX • 4 years ago

31 5 4 years ago

juancn• 4 years ago

There's also HashMap randomization, that was introduced in JDK 9 to make certain kinds of attacks more difficult to perform.

The moral of the story should be: don't lean on undefined behavior.

If you care about iteration order, that's why there's a LinkedHashMap in the API.

bmm6o• 4 years ago

The article seems incomplete without bringing in the code or test that relied on the hash code. Was the test unnecessarily strict? Was code assuming more than a collection guarantees?

carapace• 4 years ago

In the first place this is an error of RTFM kind. The "problem" behaviour is literally documented in the docs. However, in the second place, this is the wrong solution for the original problem. (The author links to https://andrewlock.net/why-is-string-gethashcode-different-e... )

The original problem is using linked lists to handle hash collisions. Assuming this is what you want (to keep all values rather than discarding old values, like e.g. Python's dict objects do) obviously you should use a data structure that can handle the case of lots of collisions well, or check your user input.

At the very least the function should have a name that reflects its behaviour, eh? "GetUnguessableHashCode()" or something?

This reminds me of the recent fiasco over in Python land where somebody noticed that int() called on large strings can block the interpreter. The obvious solution is to add an optional timeout parameter (the problem is in the time domain after all.) Instead they added a limit to the size of strings you can pass to int()!

tracnar• 4 years ago

I wonder if a type system could track nondeterminism and prevent it. E.g. you couldn't just loop over a set, you'd have to order it, or apply a commutative operation. It would fit well into concurrency too, where nondeterminism is easily introduced.

I'm sure there are languages which do this, I seem to recall seeing it in Mercury

phlip9• 4 years ago

Languages with first class effects, like koka[1], require you to declare up-front what side effects (sample randomness, do I/O, abort, etc...) your function might cause.

Then from another outer function, you can't call the effectful function unless the outer function also declares those same side-effects (or you provide handlers for them).

This way you can easily isolate non-determinism and I/O to the top-level part of your program, while keeping the interior business logic pure.

The "first-class effects" part is what lets you easily compose effects and inject custom handlers. Ideally in a way that's more ergonomic than juggling with Monad type system Jenga.

[1] https://koka-lang.github.io/koka/doc/index.html

Hash Codes, Non-Determinism, and Other Eldritch Horrors

Related Stories