Core Concept Mastery • DSA Module
The hash function is the formula that turns a key into an index. A collision is when two different keys get the same index. We cannot avoid collisions if the table is finite, so we need a way to handle them (chaining or probing).
The hash function is the formula that assigns the spot. A collision is when two keys get the same spot.
Spot = Key % TotalSpots
Example: Key 105, 10 spots. 105 % 10 = Spot 5.
Calculates index instantly based on value. O(1).
When two keys get the same spot: that is a collision.
Two different keys (e.g. 105 and 25) both got spot 5. We cannot avoid this when the table is finite. We need a strategy: chaining or probing.
The hash function
The hash function takes a key and returns an index. A simple example is modulo: Spot = Key % TotalSpots. So if the key is 105 and we have 10 spots, 105 % 10 = 5. The key goes to spot 5.
Goal: spread keys evenly
We want keys to go to different slots. If the hash function always returns 0, every key would go to slot 0. Then we would have one long list and search becomes slow (O(n)). A good hash function spreads keys so that on average each slot has few items.
Collisions
Sometimes two keys get the same index. For example 105 and 25: 105 % 10 = 5 and 25 % 10 = 5. Both want spot 5. That is a collision. We cannot avoid collisions when the table has limited size. So we need a rule: either put more than one item at the same slot (chaining) or find another empty slot (probing).
A good hash function spreads keys evenly so we get fast lookups. If it always returns the same index, everything piles in one place and we lose the speed of hashing. Collisions are normal; we just need a clear strategy to handle them.