Imagine looking up an avocado’s price at a grocery store. Searching a price list takes time, even when the list is sorted. What if the item’s name told you exactly where its price was stored? A hash function makes that possible: it maps a key, such as a name, to a number that can identify a slot in an array. section 5.0 section 5.1
Store a price, then find it
Suppose the function maps “apple” to index 3. Store the apple price there. Later, feed “apple” into the same function and go straight to index 3. This works only if the function consistently returns the same number for the same key. Its result must also identify a valid array slot. section 5.1
Different keys should spread across the array. But they cannot always get separate slots: a collision occurs when two keys map to the same one. For example, a function based on the first letter sends both “apples” and “avocados” to the same slot. One simple workaround keeps a linked list at that slot, though finding an item then requires searching the list. section 5.7
What makes a function useful for a hash table?
- Consistency: the same key must lead back to the same location. section 5.1
- Good distribution: spreading keys across slots reduces collisions. Returning 1 for every key would put everything in one place. section 5.10
- Performance: with a good hash function and a low load factor, hash-table operations are fast on average; in the worst case, they take O(n) time. section 5.8
You usually use a language’s built-in hash table rather than write its hash function yourself. In Python, a dictionary can store a price as `book["apple"] = 0.67` and retrieve it with `book["apple"]`. Knowing what the hash function does helps explain why that lookup is usually quick—and why collisions matter. section 5.1 section 5.11
