Hacker News Reader

Comment by mike_hearn | Hacker News Reader

The reason is that it'd make HashMap and HashSet a lot less useful. If every type had to opt in, you'd be unable to use many types as keys or set entries for no better reason than the authors didn't bother to implement hash codes or equality. By providing reasonable identity-based versions of these, it increases the utility of the language at a tradeoff in memory usage.

View on HN

You could implement the hashing code in a helper class and construct the HashMap with it.

Without a way to give objects identity you'd get stuck pretty fast as it's not guaranteed you have access to any data to hash. You'd have to break encapsulation. That would then hit problems with evolution, where a new version of a class changes its fields and then everything that uses it as a hashmap key breaks.

My experience with platform design has consistently been that handling version evolution in the presence of distant teams increases complexity by 10x, and it's not just about some mechanical notion of backwards compatibility. It's a particular constraint for Java because it supports separate compilation. This enables extremely fast edit/run cycles because you only have to recompile a minimal set of files, and means that downloading+installing a new library into your project can be done in a few seconds, but means you have to handle the case of a program in which different files were compiled at different times against different versions of each other.

JavaScript handles the "no identity hash" with WeakMap and WeakSet, which are language built-ins. For Virgil, I chose to leave out identity hashes and don't really regret it. It keeps the language simple and the separation clear. HashMap (entirely library code, not a language wormhole) takes the hash function and equality function as arguments to the constructor.

[1] https://github.com/titzer/virgil/blob/master/lib/util/Map.v3

This is partly my style too; I try to avoid using maps for things unless they are really far flung, and the things that end up serving as keys in one place usually end up serving as keys in lots of other places too.

Does that assume that you have only one key type and not an infinite sized hierarchy of child classes to deal with? If you had a map that took a Number as key, how many child classes do you think your helper class would cover and what extension framework would it use to be compatible with user defined classes?

The reality would be that in all but the most extreme cases emulating set semantics by iterating a list would then be considered good enough, "avoid premature optimization" and all that. In real life code, this would have eaten up any advantage of a shorter object header a hundred times.

yeah this is where traits instead of hierarchies become useful - I should be able to implement the Hash interface for an object I do not own and then use that object + trait going forward for HashMap and HashSet.

Java doesnt make this very composable

Should be noted that Rust (one of the most prominent languages with traits) doesn't allow you to implement a trait for an object you do not own. A common workaround is to wrap that object in your own tuple struct and then implement the trait for that struct.

(If you don’t own the trait either, that is. Your own traits can be implemented for foreign types.)

Rust’s approach to the Hash and Eq problem is to make them opt-in but provide a derive attribute that autoimplements them with minimal boilerplate for most types.

Also, Rust’s Hash::hash implementations don’t actually hash anything themselves, they just pass the relevant parts of the object to a Hasher passed as a parameter. This way types aren’t stuck with just a single hash implementation, and normal programmers don’t need to worry about primes and modular arithmetic.

That sounds like a use case for the decorator pattern?

Java uses this pattern in some places, for example you can usually pass a custom Comparator to anything that needs comparisons (like sorts).

Fully separating implementation of an interface from the data can create quite a lot of additional complexities. See my comment elsewhere about encapsulation and version stability.

Reply on news.ycombinator.com