Hash maps vs extending structs / classes

Question

A hash map that maps keys of type $K$ into values of type $V$, is essentially equivalent to "extending" this type $K$ to also contain an Option<V> field.

Implementing this in practice (apart from the bad habits of adding more fields that are irrelevant most of the time), shouldn't the "extension" of $K$ be faster in practice and more memory-friendly? Since hash maps take extra redundant space, and aren't guaranteed to work in $O(1)$ worst case deterministically (i.e, not on average) - shouldn't this be the case?

Then how come hash-maps are used so much in practice? What am I missing here?

---

For more context, since it seems I wasn't clear enough in the question - I will provide the full scenario I'm dealing with, where both approaches work.

Lets say I have some collection Col of keys with type K. Our running example will be Col:=Graph and K:=Node.

Now, we want run some function on the graph - maybe, BFS. Notice that while running, the BFS algorithm associates with each node the boolean label - "was this node explored already".

Now, my question deals with the specific implementation of how we associate this label to the nodes.

We could use a hash-map, mapping between the nodes and the labels. But we could also explicitly add this label as an extra field to the Node struct (or class).

So my question is - what are the benefits of each approach? What would be the "better" solution in this case?

Answer 1

A hash map that maps keys of type K into values of type V, is essentially equivalent to "extending" this type K to also contain an Option<V> field.

No, it is not; for several reasons:

1. A hashmap gives you a collection of keys, and a fast way to look up a key in the collection. Extending type K with an Option<V> property won't give you a collection of K objects. You still need to define one.
2. Extending K is only possible if you actually own all of the code that uses K and modifying it isn't unreasonably difficult. Most professional developers are rarely in that position. K may be defined or used in code they don't own, and modifying it may be impossible or very hard.
3. The fundamental issue: the proposal of extending K for this purpose will only work if you can somehow guarantee that no existing or future code other than your BFS code will ever abuse their ability to see V values (e.g. by modifying them) and that no more than one instance of your BFS code will ever run at the same time (on collections that share K objects).

So the fundamental issue is with visibility. The extra Option<V> field will be visible to code to which it shouldn't be visible, and that won't just make it irrelevant most of the time; it is much worse: it will actually require all developers who will ever work with extended K objects, yourself included, to keep tiptoeing and handholding around V values to avoid breaking their intended use, namely, keeping state for one little piece of code somewhere in the code base.

That is fundamentally broken design. That piece of state should be visible only to that piece of code, and to nothing else; not even to another concurrent instance of that very same piece of code. There is no way to enforce that. You can put in a comment and hope people will read it, or have access to the comment in the first place. (They may only be given your code in compiled form.)

The hashmap doesn't have this issue. If you make it local to the BFS code, then nothing else, not even another concurrent instance of the same BFS code, will be able to mess with it.

If you were ever taught to avoid global variables: the Option<V> idea is to be avoided for the same reason.

Answer 2

The guarantee that they work in $O(1)$ on average is better than $O(n)$ on average. Even though you don't improve worst-case, you still improve the speed if enough operations are done on the container.

If you just extend $K$ with $V$ you just made a different struct, but it is not a container. I.e. you cannot add $K,V$ pairs there, delete them, find one you're looking for.

You could extend $K$ with $V$ and then use a set and this would be almost equivalent, but not exactly, because in a map each $k\in K$ can map to only one $v\in V$ which wouldn't be the case for a set of pairs. But this depends on the semantics of what you're trying to achieve.

---

Edit for your example - yes, if you don't need the container for looking things up (e.g. because you run BFS and your nodes have references to all neighbors), you don't want to use a hashmap for storing additional data if you can just extend the node. That is not really a use-case for hashmmaps either though. Hashmap is first and foremost a container which you use for storing data and more importantly finding stored data. If you don't need to find the data (because it can be found in another way) there is no reason for you to use it.

If on the other hand your BFS example had nodes iplemented in a way where each node did not have a reference to all its neighbors, but instead had only list of identifiers of neighbor nodes, then hashmap would be a good way to go, with the identifiers being the keys and the nodes themselves (including the visited flag) would be values.

As a last note, if you have found an element in a hashmap, it's usually imlied that you have found a key value pair. Therefore if you have this pair you can get the value in constant time. Some languages even give you an object representing the pair, which is basically equivalent to what you're proposing with extending $k$.

Answer 3

The dictionary approach has advantages, but it depends on the numbers.

If you have 100 possible items but usually use only 10 then you safe lots of space. And there are implementations that allow a prepared set of possible keys to be used, so keys in that set take zero storage.

Passing a dictionary from one function to another is usually passing just one pointer, so passing a dictionary to a ten time nested function is a lot cheaper.

The big advantage is that no code changes are needed if the set of possible values gets larger. Especially since you haven’t been using the newly added possible keys, so at the moment you don’t need them.

It all depends on your actual numbers.