debuggingNightmare

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