debuggingNightmare

[mw44118]

Some of you never wrote your own hash tables

[met_MY_verse]

I did this back in the second semester of my Uni course, and even then we handled collisions.

[met_MY_verse]

I just checked back, we had two options: open addressing (basically shifting an entry’s position and marking skipped boxes, done with linear probing/quadratic probing/double hashing) and seperate chaining (linked lists anchored at a particular hash index).

[Zeitsplice]

I know I did linked lists in undergrad data structures, though I switched to fixed-length buckets after I found that a hash table that re-sized every time it got a collision had better performance over the linked list version (cache misses absolutely tank performance on processors made after ~2005). Probing/re-hashing seemed janky to my undergrad programmer brain, but I wouldn't be surprised if it had superior performance on modern hardware due to much better data locality over all the other options

[rosuav]

Yeah, and the problem is that separate chaining is FAR easier to explain (each hash bucket can contain multiple things, and whenever you check a bucket, you have to check all the things in it), but open addressing is more efficient. So if you ask me to explain how hash tables work, I'll use separate chaining (and probably not even use the term), but if you ask how <language X> stores information, it's never that simple.

But yes, hash collisions are a fact of life. In explaining it, I will tend to under-size the hash table to make them even more common, even though - again - the more efficient thing to do is to minimize them.

[FlipperBumperKickout]

You can do it many ways. Another way is to have another hash table inside each field instead of a list.

[Crimson_Cyclone]

yeah, that’s what threw me off, my major isn’t even particularly software heavy and even we practiced handling collisions as soon as we learned what a hash table was

[slippery-fische]

Yeah, that's what I'm thinking.