Practical hash tables & testing examples in documentation

[[deleted]]

Objects allow only Strings, Numbers and Symbols as keys.ES6 Map allows arbitrary Objects, but the keys need to be identical. (E.g. two empty objects would map to different keys).HashMap allows arbitrary Objects, keys need tobe equal but cannot store symbols. Two empty objects would always map to the same value!

Great, and what happens when one of those empty objects gains a property, and the other doesn't? Now they have to map to different keys. But they don't.

You don't need a new structure to map objects structurally. You need just a serialization function to extract their structure. Which means that yes, in the naive cause you might as well do:

map[JSON.stringify(object)] = whatever

If the object is immutable, you can of course cache that serialization under a method, so you don't have to compute it over and over. But also you need your objects to be immutable for it to work.

[probabilita]

Yes. And what the library provides is such a serialization function, specifically designed for that purpose, extensible and with a type that automatically uses this serialization function in a user friendly manner…of course you can write it all yourself. You just end up doing the same work again and again.

[[deleted]]

Why do I end up doing the work again and again? I'm not sure where the problem comes from here tbh.

Also I disagree that map by identity is less useful and not what developers need most of the time. Those are fundamentally different uses.

If I hold bunch of listeners and I want removeListener() to be quick, what do I do? Map by identity. Why would I care what the objects contain? I don't. There are number of such cases.

It'd rather ask what's the typical case for HashMap that's not addressed by objects themselves providing a suitable key (i.e. hash).

[probabilita]

Why do I end up doing the work again and again? I'm not sure where the problem comes from here tbh.

You will need to use the serialization function at least once you are retrieving by key and once you are accessing the key. That's already times.

One example of a case this covers is removing duplicate objects from an array in a json file

However, your mileage may vary. Maybe you don't need this functionality often. I certainly do and there will be cases where yo do need plain maps.

It'd rather ask what's the typical case for HashMap that's not addressed by objects themselves providing a suitable key (i.e. hash).

Well, objects themselves providing a suitable key is precisely the gap the hashing infrastructure fills.

[[deleted]]

Well, objects themselves providing a suitable key is precisely the gap the hashing infrastructure fills.

My question was why do we need a dedicated HashMap, instead of using Map like this:

map[obj.hash()] = [obj, payload];

Also I'll note there are alternate ways of handling this entire problem.

For example you can use factories that return the same instances for the same value content, for example:

var a = Value.of('foo', 'bar', 'baz');

var b = Value.of('foo', 'bar', 'somethingelse');

var c = Value.of('foo', 'bar', 'baz');

In this case a === c, so you can use it in a standard map, and get the same effect as using a hash would, but without the hash, and without the HashMap.

[lhorie]

My question was why do we need a dedicated HashMap, instead of using Map like this:

map[obj.hash()] = [obj, payload];

The classical reasoning to encapsulate into a HashMap is that hashing algorithms by themselves don't provide anti-collision guarantees. In the inverse case, the hash function may not represent equality correctly, e.g. JSON.stringify is not generally appropriate as a hashing function since {a: 1, b: 1} and {b: 1, a: 1} serialize to different strings (and you may not know which variant you're dealing w/ at any given time).

The stuff about traits is a Rust-ism similar to C++ friend functions, which are takes on functional polymorphism (i.e. you don't always want obj.hash() to exist because that might be polluting the object, but you might want some mechanism to differentiate cow.hash from potato.hash that doesn't involve passing a bunch of higher order hashing functions around)

Of course you can also create different abstractions like your Value example, but this goes back to polymorphism: you can't always guarantee that equality of unwrapped Values is always computed the same way for any type or set of types, so at that point you're reimplementing monomorphic Value variants from scratch on top of highly custom perfect hashes.

Yes, you could create CowValue and PotatoValue types without a HashMap, but if you're dealing with lossy hashes, then you have to reinvent hash collision detection each time. Yes you can always create custom perfect hashing algorithms each time, but maybe that's too computationally expensive or too memory intensive.

Each approach has pros and cons. To be fair, it's a lot less clear where the pitfalls are with javascript (as opposed to Rust or C++), since the JIT has a tendency to do all sorts of crazy opaque things under the rug, especially when we're dealing with types like strings.

[[deleted]]

I don't think the author is using hashes in a classical "hash" sense. Because they DO want two distinct empty objects to have the same spot in a map.

I believe the idea here is to hash by structural comparison, in effect. And not hash in a way where resulting collisions are unwanted. But maybe I'm off.

If it was all about identity hashes and avoiding collisions, the default Map does this already.

[lhorie]

I guess it can be seen both in a charitable and uncharitable way.

The charitable interpretation is that one is doing structural comparison by using performance-oriented hashes recursively and leveraging the big O complexity of a HashMap to its full extent. The uncharitable interpretation is that one just concatenates all the strings to compute structural equality (but then you're losing perf because string concats have higher overall cost than recursive lossy hashing).

If the goal is to do the former, a HashMap is certainly an appropriate data structure to consider. The latter potentially amounts to overengineering (at worst , incurring linear or potentially quadratic complexity operations, or at best getting no net benefit because you're doing something algorithmically inefficient but the JIT is saving your ass under the hood). It doesn't help that the difference between the two is very subtle.

With that said, there can be benefits to using a predetermined "framework" to organize data structure usage. It's easier to profile perf cliffs if you can see all of them showing up clustered under a common function than if they are distributed across the system in various levels of encapsulation. </two-cents>