Hashing in Data Structures

Study Notes

Hashing is a technique that converts a key (e.g., a string, number, or object) into a unique index or hash code within a fixed-size array called a hash table.
The goal is to achieve near-constant time complexity for insert, search, and delete operations.

Hash Function:
- A hash function takes a key as input and produces a hash code as output.
- A good hash function should:
  - Be deterministic (same input always produces the same output)
  - Distribute keys uniformly across the hash table (minimizes collisions)
  - Be fast to compute
Hash Table:
- A hash table is the data structure where key-value pairs are stored.
- Each slot in the hash table is called a bucket.
Collision Handling:
- When multiple keys produce the same hash code (a collision), we need a way to resolve it.
- Common techniques include:
  - Separate Chaining: Each bucket stores a linked list of key-value pairs.
  - Open Addressing: If a bucket is full, we probe for the next available slot according to a specific strategy (e.g., linear probing, quadratic probing, double hashing).

Efficient Search: Hashing allows for extremely fast lookups of key-value pairs, often in O(1) time on average.
Data Organization: Hash tables are used in dictionaries, sets, and caches to organize data for efficient access.
Cryptography: Hash functions are used to create digital signatures, verify data integrity, and store passwords securely.

Hash Tables: The most common use of hashing is to implement hash tables (also known as hash maps or dictionaries).
Hash Sets: Hash sets are similar to hash tables but only store keys (no values).
- They are useful for quickly checking if an element exists in a collection.
Bloom Filters: Bloom filters are probabilistic data structures that use hashing to test whether an element is a member of a set.

A hash code (or hash value) is simply the output produced by a hash function when you give it a specific input (the key).
Input (Key): This could be anything – a word, a number, an entire file, or even a complex object.
Hash Function: This is the magical recipe that takes your input and transforms it into a hash code.
Output (Hash Code): This is usually a fixed-size number (e.g., a 32-bit or 64-bit integer) that represents your original input in a compressed form.

This is where the determinism of hash functions comes into play.
It means that:
- Every time you feed the exact same input into a hash function, you'll always get the exact same hash code as output.
- If you even change a single character in a string, add 1 to a number, or modify any tiny detail of your input, the resulting hash code will be completely different.

Consistency: It ensures that data stored in a hash table can be reliably retrieved later using the same hash code.
Data Integrity: Hash codes can be used to verify that data hasn't been altered.
Security: Hash functions used for password storage are designed to be one-way – it's incredibly difficult (ideally impossible) to figure out the original password from the hash code.