Hashing

Hash Tables

The most common application of hashing is in hash tables (also known as hash maps, dictionaries, or associative arrays). A hash table is a data structure that allows for very fast lookups, insertions, and deletions on average.

How it works:

1. When you want to store a key-value pair, the hash function is applied to the key to compute an index into an array (the "buckets" or "slots").
2. The value is then stored at that index.
3. When you want to look up a key, you re-compute its hash to find the index and retrieve the value.

This allows for an average time complexity of O(1) for search, insert, and delete operations.

Hash Collisions

A "collision" occurs when two different keys produce the same hash, and thus map to the same index in the array. Since the number of possible keys is usually much larger than the number of array indices, collisions are inevitable. A good hash function should distribute keys as evenly as possible to minimize collisions.

Collision Resolution Strategies:

1. Separate Chaining:

Each bucket in the array holds a pointer to a linked list (or another data structure like a balanced binary search tree in Java 8+) of all the key-value pairs that have hashed to that index. This is a very common and robust method.

2. Open Addressing:

All key-value pairs are stored directly in the array itself. When a collision occurs, the algorithm "probes" for the next empty slot. Strategies include Linear Probing, Quadratic Probing, and Double Hashing. Open addressing can be faster due to better cache performance but can suffer from clustering issues.

String Hashing

Another powerful use of hashing is string hashing (or polynomial rolling hash). This technique allows for comparing any two substrings of a string in O(1) time after an O(n) preprocessing step. It works by representing a string as a polynomial and calculating its value under a large prime modulus. This is extremely useful in problems involving string matching.