1
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ P.S, I'm not 100% sure if this fits the community - since it technically is about programming (but more in general). Please tell me if I should move this question to another SE site $\endgroup$
    – nir shahar
    Jan 11, 2022 at 21:49
  • 1
    $\begingroup$ You are missing that Hash-Maps provide fast "find". Lets say you have some collection of keys, and you want to check if $k$ is in this collection, usually you would need $O(n)$ operations (linear search) but with a hash-map you can get up to $O(1)$ amortized. So its about fast look up. $\endgroup$
    – plshelp
    Jan 11, 2022 at 22:03
  • $\begingroup$ Can't we check if the Option<V> field of $k$ is non-empty? This would be $O(1)$ in worst case (and not even amortized or on average) $\endgroup$
    – nir shahar
    Jan 11, 2022 at 22:39
  • $\begingroup$ How do you find the right $k$ though? $\endgroup$
    – Ordoshsen
    Jan 11, 2022 at 22:49
  • $\begingroup$ You are given $k$. Even if your job is to check in a hashmap if $k$ exists, you are still given $k$. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 23:54

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ So basically you are saying this is better from the encapsulation perspective. So assuming that I managed to extend this $K$ in a way that no one else can access - would you say its a more preferable option? I'm thinking more of benefits in time & space rather than encapsulation and "good practices" (because I can almost certainly guarantee encapsulation in some level) $\endgroup$
    – nir shahar
    Jan 12, 2022 at 21:46
  • 1
    $\begingroup$ It is never more preferable. Encapsulation, correctness and comprehensibility are more important than scraping bits 99.999% of the time. Cases where you really care about the tradeoff between the two approaches in terms of number of bytes used are cases where you don't want to use a language with an Option<V> type because you need tighter control over your memory. $\endgroup$ Jan 13, 2022 at 11:37
  • $\begingroup$ Sure, thanks for the help! $\endgroup$
    – nir shahar
    Jan 13, 2022 at 11:39
  • 1
    $\begingroup$ There are no benefits in space, ever. The ability to have an Option<V> field will cost you for all instances of K. A hash map only costs you for instances of K that are mapped to a V. And from a software development (not CS) point of view, this is just godawfully bad. $\endgroup$
    – gnasher729
    Jan 13, 2022 at 16:09
  • 1
    $\begingroup$ One more issue: the equivalent of destructing/garbage collecting the hashmap would have to iterate over all K's in memory to set the Option<V> fields to None. $\endgroup$ Jan 14, 2022 at 8:34
2
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ Well, I was not really thinking of "adding pairs" or "deleting pairs" in terms of a single object that stores them. So, "deleting" in this case would be to set the value of the Option<V> to the None variant, and "adding" is exactly storing something (which is not None) in the field. Also, "extending K" would still yield a single mapping between keys and values, since each key has exactly one value associated with it anyways. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 22:29
  • $\begingroup$ Ok, imagine a program where you would need an unknown number of these pairs. How would you store them? Obvious answer would be in an array, but hashmap is better than an array for any application where you need random access. If you need just a constant number of these objects, of course it's better memory-wise to have an object where you store whatever you need, but that's not a use-case for hashmaps. Hashmap is a container and you need containers when you want to access an unknown (or large) number of objects. $\endgroup$
    – Ordoshsen
    Jan 11, 2022 at 22:39
  • $\begingroup$ The keys are already stored in a different data structure. I'm only interested in associating this value to each key - so given a key (in the extended form), finding the value associated with it boils down to accessing the Option<V> field from it and retrieving the value from it. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 22:41
  • $\begingroup$ Sure, that works, as I've already said, if the underlying container is a hashset, you have something almost equivalent to a hashmap. You should probably mention in the question the fact that you would use a different container for storing the objects. But then I don't really understand the question you're trying to ask and what does it have to do with the complexity of a hashmap (since you didn't specify complexities of your container) and what is the concrete alternative then. For the record most programming languages store the key value pairs almost identically to what you proposed. $\endgroup$
    – Ordoshsen
    Jan 11, 2022 at 22:45
  • $\begingroup$ The "containers" shouldn't make a difference here, since I'm interested in specifically mapping (or associating) a type of keys $K$ with a value of type $V$. It doesn't really matter how I store all the $K$'s I have. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 23:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.