Hashing in Data Structures

What is Hashing?

• 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.

How Does Hashing Work?

• 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).

Importance of 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.

Hashing in Data Structures

• 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.

Hash Code

• 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.

The "Same Input, Same Output" Principle

• 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.

Importance of Determinism

• 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.