undefined | Better HN

0 pointsq-big3y ago0 comments

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

0 comments

jvanderbot3y 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_3y 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.

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

1 more reply

marcosdumay3y ago

Collision-free hashes exist. They are just not used on practice to build hash maps, but if you use a 128 bits hash with homogeneous distribution, handling collisions is irrelevant.

Besides, just because you are storing the keys, it doesn't mean it is viable to retrieve them. On the collision aware maps you see on CS, iterating through the keys is extremely inefficient.

The OP's description is clearly somebody that has learned the theory, but don't have any practical knowledge.

nuancebydefault3y ago

I never understood why a 'dictionary' (so called conveniently in python) is called a 'map' in c++ and yet, a 'hash' in ruby. On a side note, a map in ruby is an operation that actively maps one thing to another. So confusing. Finally reading what you just wrote makes the pieces of this puzzle to fall in place! Never had a data structures class.

q-bigOP3y ago

According to https://stackoverflow.com/a/2884200 map and dictionary are just terms for the same data structure concept. On the other hand: there exist other backings for this data structure than hashing the key, such as binary trees (for example red-black trees or AVL trees).

j / k navigate · click thread line to collapse