4 ms·

I had an extraordinarily painful conversation with someone who had done pretty well in our DS class but didn’t have a ton of practical experience. Me: “why don

I had an extraordinarily painful conversation with someone who had done pretty well in our DS class but didn’t have a ton of practical experience. Me: “why don’t you just use a hash table here? That array you’re iterating through each time has like 200,000 entries” Him: “I can’t. I need to be able to get both the key and the value and hash tables don’t store the key” Me: “…sigh, school has failed us again”

readthenotes1 4y ago
I had an extraordinarily painful conversation with experience programmers when I pointed out that the values that the hash key relyed upon must not change, for the life of the hash map.
- KronisLV 4y ago
  > ...when I pointed out that the values that the hash key relyed upon must not change, for the life of the hash map. Now I'm wondering about something like: MutableHashMap<MutableKey<T1>, Value<T2>> You could probably have they key be a container object and allow changing its internal value, which would then communicate to the hash map that it belongs to, that it should do some internal changes: Entry<MutableKey<String>, Value<SomeEntity>> entry = mutableHashMap.getEntryByKey("myKey"); entry.setKey("myNewKey"); That logic could take an internal hash map, remove the element by the old key and add it with the new key. So, to an outside user it would seem like you can change the keys. The only problem would be that depending on the language you're using, you wouldn't change the objects directly, but would use those containers and it would essentially just be some boilerplate around a regular hash map. For example, Java has MutableInt and similar classes, which here would be hooked up to the MutableHashMap that they belong to. Then again, I can't come up with many cases where something like that would be nice to have, since if you want to "change" a key, you can just do the following manually: var ourValue = myHashMap.get("myKey"); myHashMap.remove("myKey"); myHashMap.put("myNewKey", ourValue);
- jbn 4y ago
  the nitpicker in me wants to say that the hash key can change (and it works if you rehash items whose key changed), but lookup by key will fail because the item will landed in the bucket of its original hash... but yes keys can't change if you want your values to be retrievable by key.
  - readthenotes1 4y ago
    Is it nitpicking if we end up with fewer bugs as a result of the conversation? :)
    - jbn 4y ago
      that's the spirit!
q-big 4y ago
> someone who had done pretty well in our DS > Him: “I can’t. I need to be able to get both the key and the value and hash tables don’t store the key” How could he do well in the data structures class? This is the definition of a hash map or hashed dictionary, so this is basic knowledge of data structures that is taught in this class and central to know to even have a chance of passing the exam.
- jvanderbot 4y ago
  No, technically he's right. On paper, a hash map creates an index in an array-like structure from the key, but does not necessarily store the key in a retrievable way. The "Hash" in hashmap comes from the fact that the key is somehow hashed (an often irreversible procedure) to determine the memory location to store the value. In practice it's not the case, but very technically from a purely theoretical standpoint, I think he's right. EDIT: untrue on any finite sized array, due to collisions. See below, and sorry for the brain fart!
  - hawk_ 4y ago
    There's no theoretical way for a hash map to work without storing the key - the reason for that is hash collisions in presence of which you do need to run equality comparison with stored keys otherwise you would overwrite data just because of hash clashes.
    - tonyarkles 4y ago
      >> In practice it's not the case, but very technically from a purely theoretical standpoint, I think he's right. > There's no theoretical way for a hash map to work without storing the key - the reason for that is hash collisions in presence of which you do need to run equality comparison with stored keys otherwise you would overwrite data just because of hash clashes. There's a ton of material in a Data Structures course. I'm sure the point about storing the key was mentioned at some point, but it's not the focus when talking about different hashing strategies etc. For people with a bunch of experience (e.g. I'd been writing Perl for years before this, so being able to iterate across a hash and get (k,v) pairs was obvious) it's a detail that is already there in your brain, but if the DS course is your first exposure to a hash map, it's a detail that can easily get lost in the huge forest of other brand new things to learn.
dehrmann 4y ago
The followup question is "Can you explain a strategy for resolving hash collisions?"
onlycoffee 4y ago
Depends on the use case, sometimes a list is more appropriate. On an old machine, Java 17 can iterate a list of 30 million strings looking for a match in around a half second. Just checked it in jshell. If the use case was that the map's keys could potentially change over the lifetime of the map or if the value's were not idempotent and if iterating 30 million items occurs fairly infrequently, then an ArrayList (in Java) might be the best choice.

readthenotes1 4y ago

I had an extraordinarily painful conversation with experience programmers when I pointed out that the values that the hash key relyed upon must not change, for the life of the hash map.

KronisLV 4y ago
> ...when I pointed out that the values that the hash key relyed upon must not change, for the life of the hash map. Now I'm wondering about something like: MutableHashMap<MutableKey<T1>, Value<T2>> You could probably have they key be a container object and allow changing its internal value, which would then communicate to the hash map that it belongs to, that it should do some internal changes: Entry<MutableKey<String>, Value<SomeEntity>> entry = mutableHashMap.getEntryByKey("myKey"); entry.setKey("myNewKey"); That logic could take an internal hash map, remove the element by the old key and add it with the new key. So, to an outside user it would seem like you can change the keys. The only problem would be that depending on the language you're using, you wouldn't change the objects directly, but would use those containers and it would essentially just be some boilerplate around a regular hash map. For example, Java has MutableInt and similar classes, which here would be hooked up to the MutableHashMap that they belong to. Then again, I can't come up with many cases where something like that would be nice to have, since if you want to "change" a key, you can just do the following manually: var ourValue = myHashMap.get("myKey"); myHashMap.remove("myKey"); myHashMap.put("myNewKey", ourValue);
jbn 4y ago
the nitpicker in me wants to say that the hash key can change (and it works if you rehash items whose key changed), but lookup by key will fail because the item will landed in the bucket of its original hash... but yes keys can't change if you want your values to be retrievable by key.
- readthenotes1 4y ago
  Is it nitpicking if we end up with fewer bugs as a result of the conversation? :)
  - jbn 4y ago
    that's the spirit!

q-big 4y ago

> someone who had done pretty well in our DS > Him: “I can’t. I need to be able to get both the key and the value and hash tables don’t store the key” How could he do well in the data structures class? This is the definition of a hash map or hashed dictionary, so this is basic knowledge of data structures that is taught in this class and central to know to even have a chance of passing the exam.

jvanderbot 4y ago
No, technically he's right. On paper, a hash map creates an index in an array-like structure from the key, but does not necessarily store the key in a retrievable way. The "Hash" in hashmap comes from the fact that the key is somehow hashed (an often irreversible procedure) to determine the memory location to store the value. In practice it's not the case, but very technically from a purely theoretical standpoint, I think he's right. EDIT: untrue on any finite sized array, due to collisions. See below, and sorry for the brain fart!
- hawk_ 4y ago
  There's no theoretical way for a hash map to work without storing the key - the reason for that is hash collisions in presence of which you do need to run equality comparison with stored keys otherwise you would overwrite data just because of hash clashes.
  - tonyarkles 4y ago
    >> In practice it's not the case, but very technically from a purely theoretical standpoint, I think he's right. > There's no theoretical way for a hash map to work without storing the key - the reason for that is hash collisions in presence of which you do need to run equality comparison with stored keys otherwise you would overwrite data just because of hash clashes. There's a ton of material in a Data Structures course. I'm sure the point about storing the key was mentioned at some point, but it's not the focus when talking about different hashing strategies etc. For people with a bunch of experience (e.g. I'd been writing Perl for years before this, so being able to iterate across a hash and get (k,v) pairs was obvious) it's a detail that is already there in your brain, but if the DS course is your first exposure to a hash map, it's a detail that can easily get lost in the huge forest of other brand new things to learn.

dehrmann 4y ago

The followup question is "Can you explain a strategy for resolving hash collisions?"

onlycoffee 4y ago

Depends on the use case, sometimes a list is more appropriate. On an old machine, Java 17 can iterate a list of 30 million strings looking for a match in around a half second. Just checked it in jshell. If the use case was that the map's keys could potentially change over the lifetime of the map or if the value's were not idempotent and if iterating 30 million items occurs fairly infrequently, then an ArrayList (in Java) might be the best choice.