Table of Content

Introduction to Hashing

Understanding Functions and Hashing

• Functions:
  • A function is a bridge connecting inputs to specific outputs.
  • Types of mappings:
    • One-to-One Mapping: Each input has a unique output. E.g., y = x + 2.
    • Many-to-One Mapping: Multiple inputs can map to the same output. E.g., y = x^2 for x = -2, -1, 0, 1, 2.
    • One-to-Many and Many-to-Many Functions: Less desirable for hashing due to lack of clarity and chaotic nature.
• Hashing:
  • Hashing transforms complex data into smaller, fixed-size output.
  • A hash function consistently produces the same output for the same input (deterministic).
  • Fixed-length output regardless of input size.
  • Collisions occur when different inputs produce the same output.
• Key Terms:
  • Hash Function: Converts input into fixed-size output.
  • Hash Input/Message: Data fed into the hash function.
  • Hash Output/Digest: Transformed output of the hash function.
  • Collision: Two different inputs producing the same output.

Cryptographic Hashing

• Irreversibility: Difficult to reverse-engineer the input from the hash.
• Pseudo-random Appearance: Hash appears random but is consistent.
• Collision Resistance: Hard to find two different inputs with the same hash.
• Speed: Efficient generation of hashes is crucial.

Practical Applications

• Passwords: Stored as hashes for security. Salt is added to passwords before hashing to prevent dictionary attacks.
• Git: Uses hashing to track file changes.
• Blockchain Technology: Hashing ensures secure, unchangeable transaction records.
• Digital Signatures: Verify authenticity and integrity of messages/documents.
• Encrypted Communication: Maintains confidentiality and integrity of messages.

Hash Tables

Data Structures for Fast Retrieval