Hashing Algorithms and Collision Management

A hash function is a mathematical function that takes an input (or ‘message’) and returns a fixed-size string of bytes.

Need for Hash data structure:

• The amount of data we deal with is constantly increasing, both on the internet and in everyday programming tasks.
• Arrays are a common data structure for storing information. They excel at adding data quickly (in constant time, O(1)). However, searching for specific data within an array can be slow (at least O(log n) time).
• This is where hash tables come in. They are a specialized data structure designed for lightning-fast lookups.
• Unlike arrays, hash tables prioritize retrieval speed over insertion speed.
• Hash tables achieve this through a technique called hashing, where data is mapped to a unique location based on a key (like a name).
• This allows for near-instantaneous lookups, making them ideal for scenarios where finding specific data is essential, like checking usernames or retrieving shopping cart items.

Components of Hashing:

Hashing utilizes three core components to achieve efficient data storage and retrieval:

1. Key: This acts as a unique identifier for the data element. It can be a string, integer, or any data type that can be consistently hashed. The key serves as the input for the hash function.
2. Hash Function: This is a special algorithm that transforms the key into a fixed-size integer value, known as the hash index. Ideally, the hash function should distribute keys uniformly across the available slots in the hash table to minimize collisions.
3. Hash Table: This is a data structure designed for fast access using keys. It’s essentially an array with each slot potentially holding a key-value pair. The hash index generated by the hash function determines the specific slot where the corresponding data element is stored or retrieved within the hash table.

Key Features of a Hash Function:

• Collision resistance: It should be highly unlikely to get the same output for two different inputs.
• Preimage resistance: It should be computationally infeasible to find the input that matches a given hash function.
• Deterministic: The same input should always produce the same hash result.
• Avalanche effect: A small change in the input should result in a completely different hash value.
• Hidden: It should be difficult to guess the input from the output.
• Puzzle-friendly: It should be difficult to choose an input that produces a specific output.
• Quick Computation: The hash value should be computationally efficient to compute for any input size.

Types of Hashing Algorithms

MD5 (Message Digest Algorithm 5):

• Developed by Ronald Rivest in 1991.
• Produces a 128-bit (16-byte) hash value.
• Security: Vulnerable to collision attacks; considered cryptographically broken and unsuitable for further use in security applications.

SHA-1 (Secure Hash Algorithm 1):

• Developed by the NSA and published by NIST in 1993.
• Produces a 160-bit (20-byte) hash value.
• Security: Vulnerable to collision attacks; deprecated for most cryptographic uses.

SHA-256 (Secure Hash Algorithm 256):

• Part of the SHA-2 family, developed by the NSA and published by NIST in 2001.
• Produces a 256-bit (32-byte) hash value.
• Security: Currently considered secure and widely used in various security applications.

Cryptographic vs Non-Cryptographic Hash Functions

• The distinction between cryptographic and non-cryptographic hash functions lies primarily in their design goals and properties.
• Cryptographic hash functions prioritize security guarantees such as resistance to pre-image attacks and collision attacks, making them suitable for cryptographic protocols and applications where data integrity and authenticity are paramount.
  Eg : Digital Signatures, Data Integrity and Password Hashing.
• Non-cryptographic hash functions, on the other hand, focus on speed and efficiency, catering to applications where security requirements are less stringent and performance is critical.
  Eg : Hash Tables, Checksums, Data Structures

Hash Collisions

• In hashing, collisions occur when two distinct keys map to the same hash value within the hash table.
• We have a hash table with a capacity of 4 entries (slots 0–3). This means it can hold a maximum of 4 key-value pairs.
• We use a basic hash function that takes the key modulo (remainder after division) by the table capacity (4). This is denoted as key % 4.

Keys and Hashes:

• Key: “user123” (hash value: “user123” % 4 = 3)
• Key: “admin” (hash value: “admin” % 4 = 3)

Both “user123” and “admin” map to the same hash index (3) due to the limited addressing space (4 slots) and the compression by the hash function (mod 4). This creates a collision.

Hash collision

Handling the collision

1. Separate Chaining:

• Imagine each slot in the hash table can hold a linked list.
• When a collision occurs (like with “user123” and “admin” in your example), both keys are added to the same linked list attached to the slot with the colliding hash value (slot 3 in this case).
• This creates a separate chain of elements that share the same hash index.

Seperate Chaining

Benefits:

• Simple to implement.
• Works well for a moderate number of collisions.

Drawbacks:

• In the worst case, if many keys collide and end up in the same linked list, searching for a specific key can become slow as you need to traverse the entire list.

2. Linear Probing:

• This approach attempts to insert the key in the next available slot after the initial collision point.
• In your example, with “user123” and “admin” colliding at slot 3, linear probing would check slot 4(since it’s the next available slot).
• If slot 4 is empty, “admin” would be placed there.(depending on the table’s fill pattern).

Benefits:

• No need for additional data structures like linked lists.
• Can be faster than separate chaining for a small number of collisions.

Drawbacks:

• In the worst case, if the table is nearly full, linear probing might keep searching for empty slots, causing a performance issue known as clustering.

Strategies for Hash Collision Prevention

While collisions are unavoidable, there are techniques to minimize their occurrence and maintain the effectiveness of your hash table.

1. Using Strong Hash Functions:

• The first line of defense is choosing a well-established and cryptographically secure hash function. These functions are designed to distribute keys uniformly across the hash table space, reducing the likelihood of collisions.
• Common examples include SHA-256 and SHA-3.

2. Increasing Hash Table Size:

• A larger hash table offers more space for keys to be distributed, reducing the probability of collisions occurring.
• However, this comes with the trade-off of increased memory usage.

3. Salting:

• When hashing passwords or other sensitive data, adding a random string (salt) before hashing significantly reduces the chance of collisions.
• Even if two passwords collide after salting, the attacker would need to find a collision for the specific salt used, making it much more difficult to crack passwords.

4. Choosing Appropriate Hash Function Parameters:

• Some hash functions allow for configurable parameters that influence the output size and collision resistance. Choosing the right parameters ensures a balance between security and performance. For example, a larger hash value generally offers better collision resistance but requires more storage space.

5. Load Factor:

• The load factor represents the percentage of slots in the hash table that are filled. Maintaining a moderate load factor (around 50%) helps to keep collisions at control.
• If the load factor becomes too high, consider increasing the hash table size.