What is a Hash Algorithm?
Hash algorithms, told as a story about computing a number to point straight at the right slot in the toolbox.
With so many tools, finding one takes forever.Searching one by one might mean checking the whole box.
Searching from scratch every time is too slow.A rule to point straight at the right slot would help.
A hash algorithm computes a number to point straight at the slot.One calculation tells you the slot — no searching.
Two tools can point to the same slot — a collision.Chain the colliding tools in one slot, or slide one into the next empty slot.
A full toolbox slows tool lookup back down.Fast lookup means keeping more slots than tools.
A hash algorithm computes a number from the data to point straight at a storage slot (bucket), so lookup and storage take roughly one calculation.
A hash algorithm feeds a key into a hash function to produce an array index (bucket number). A hash table built on this achieves near-O(1) average search and insertion, far faster than scanning everything with linear search (O(n)). When different keys hash to the same bucket — a collision — it's resolved by chaining (linking multiple items in one slot) or open addressing (sliding into the next free slot). As the load factor rises (too much data for too few buckets), collisions increase and performance drops. This is the data-structure/algorithm sense of 'hash', distinct from cryptographic hash functions used to verify message integrity.
When grown-ups say it
- Hash Function
- The rule that computes the number. Always gives the same slot for the same input.
- Hash Table
- The toolbox with tools sorted into slots. Average O(1) for lookup and insertion.
- Bucket (Slot)
- The slot the computed number points to. The hash value becomes the slot number.
- Collision
- Different tools pointing to the same slot. Resolved with chaining or open addressing.
- Chaining
- Hanging multiple items one after another in the slot. Links the colliding items in a list.
- Open Addressing
- Sliding into the next empty slot. Gets harder to find an empty slot as the table fills up.
- Load Factor
- The ratio of tools stored to the number of slots. Too high, and collisions rise.
- Linear Search
- Checking items one by one from the start. Much slower than a hash table — O(n).