Hashing

In the context of data structures, hashing is the process of converting a given key into a smaller, fixed-size value, which is then used as an index in a data structure called a hash table. The function that performs this conversion is called a hash function.

Key Concepts:

• Hash Table: A data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
• Hash Function: The algorithm that takes an input (or 'key') and returns a fixed-size string of bytes. The output is typically a 'hash code' or 'hash value'. A good hash function for data structures aims to distribute keys uniformly across the array indices.
• Collision: This occurs when two different keys hash to the same index. Since this is often unavoidable, strategies are needed to handle it.
• Collision Resolution: Techniques to manage collisions. Common methods include:
  • Chaining: Each bucket in the hash table stores a pointer to a linked list of all the key-value pairs that hashed to that index.
  • Open Addressing: When a collision occurs, the algorithm probes for the next empty slot in the table according to a fixed sequence.

Usage: Hashing is fundamental to hash tables (or hash maps), which provide efficient average-case time complexity for lookups, insertions, and deletions, typically O(1). They are widely used in databases for indexing, in compilers for symbol tables, and in caches.

Example: A simple hash function for strings could be to sum the ASCII values of the characters and then take the modulus with the table size. For a table of size 101 and the key "cat": 'c' (99) + 'a' (97) + 't' (116) = 312 312 % 101 = 9 So, the key "cat" would be stored at index 9 in the array.

In cryptography, hashing is the process of using a cryptographic hash function to map data of arbitrary size to a fixed-size bit string. These functions are designed to be one-way and collision-resistant.

Key Properties of a Cryptographic Hash Function:

• Deterministic: The same input message will always produce the same hash output.
• Pre-image Resistance (One-way): Given a hash value h, it should be computationally infeasible to find any input message m such that hash(m) = h.
• Second Pre-image Resistance (Weak Collision Resistance): Given an input m1, it should be computationally infeasible to find a different input m2 such that hash(m1) = hash(m2).
• Collision Resistance (Strong Collision Resistance): It should be computationally infeasible to find any two distinct inputs m1 and m2 such that hash(m1) = hash(m2).
• Avalanche Effect: A small change to the input message (e.g., changing a single bit) should produce a drastically different hash output.

Usage:

• Data Integrity: Hashing is used to generate a checksum for a piece of data (like a file). If the data is altered in any way, its new hash will not match the original, indicating corruption or tampering.
• Password Storage: Instead of storing user passwords in plaintext, systems store their hash values. When a user tries to log in, the system hashes the entered password and compares it to the stored hash. To mitigate rainbow table attacks, a random value called a 'salt' is typically added to the password before hashing.
• Digital Signatures: To create a digital signature, a private key is used to encrypt the hash of a message, not the entire message. This is more efficient and just as secure.
• Blockchain: Hashing is a core component of blockchain technology. Each block contains the hash of the previous block, creating a secure, immutable chain. It is also used in proof-of-work consensus mechanisms.

Examples of Algorithms:

• SHA-2 Family (e.g., SHA-256, SHA-512): Secure Hash Algorithm 2, currently considered secure and widely used.
• SHA-3: The newest standard, chosen through a public competition.
• MD5 (Message Digest 5): An older algorithm that is now considered insecure and broken due to known collision vulnerabilities. It should not be used for security purposes.