How Hash Maps Work Under the Hood

https://www.youtube.com/watch?v=e9Ny-9Gwsvk You have a million contacts in your phone. You type a name and it appears instantly. Not after scanning a thousand entries. Instantly. How? The Core Trick: Calculate, Don't Search A hash map takes your key — say, "Alice" — and feeds it into a hash function. The function produces a number, which gets reduced (usually modulo the array size) into an index. You don't search for where Alice lives. You calculate it. One operation, direct access. That's O(1) lookup. But hash functions map infinite possible keys into a finite number of slots. Eventually, two keys land in the same bucket. As the table fills, collisions become unavoidable. Handling Collisions Chaining — each bucket holds a linked list. Collisions just append to the chain. Simple, but every pointer chase is a cache miss since list nodes are scattered across memory. Open addressing — instead of a list, you look for the next empty slot in the array itself. Linear probing checks the next s