Hash Functions & Collisions

Stacks and queues both still require scanning to find an arbitrary value - neither answers "does this exact key exist?" any faster than O(n). Hashing exists to answer that specific question in average-case O(1) time, and it is arguably the single most-used data structure in real software: Python's own dict, every in-memory cache, and most database indexes that are not range-based all rest on this same idea.

A hash function takes an arbitrary key - a string, a number, a tuple - and deterministically maps it to a number called a hash code. The same key always produces the same hash code. To actually place that key in a fixed-size array, take the hash code modulo the number of buckets available, which gives a bucket index - this is what lets a hashmap jump almost directly to roughly the right slot instead of scanning the whole structure.

Python's hash() function already works for built-in immutable types like strings, numbers, and tuples of hashable values. A custom class needs its own __hash__ method (paired with a matching __eq__) to be usable as a dict key - a direct callback to the dunder methods covered in the OOP portion of Phase 1.

The pigeonhole principle guarantees that if more distinct keys are hashed than there are buckets available, at least two of those keys must eventually land in the same bucket - no hash function, however well designed, can avoid this for an unbounded key space mapped onto a fixed number of buckets. A good hash function distributes keys as evenly as possible to minimize how often this happens, but it can never eliminate collisions outright.

• -Separate chaining: each bucket holds a small list of every key-value pair that hashed there. On a collision, simply append to that bucket's list; searching means scanning within that one, hopefully short, bucket.
• -Open addressing: on a collision, probe forward for the next open slot in the array itself (linear probing, quadratic probing, double hashing), with no per-bucket list at all - but deletions become trickier, and a full table can suffer from clustering.

Separate chaining is the simpler model to reason about, and the one built in the next chapter (and asked for in Level 4): each bucket degrades gracefully into a slightly longer list rather than requiring careful tombstone handling on delete, which open addressing needs.