Hashing Techniques in DSA?

Let’s consider a user authentication system where we need to store and retrieve user credentials (username and password) efficiently. Hashing can be used to:

• Store passwords securely (using cryptographic hashing).

• Quickly look up user information (using a hash table).

1. Hashing Passwords

We’ll use a cryptographic hash function (e.g., SHA-256) to securely store passwords.

using System;
using System.Security.Cryptography;
using System.Text;

class Program
{
    static void Main()
    {
        string password = "mySecurePassword123";
        string hashedPassword = HashPassword(password);

        Console.WriteLine($"Original Password: {password}");
        Console.WriteLine($"Hashed Password: {hashedPassword}");
    }

    static string HashPassword(string password)
    {
        using (SHA256 sha256 = SHA256.Create())
        {
            byte[] hashedBytes = sha256.ComputeHash(Encoding.UTF8.GetBytes(password));
            return BitConverter.ToString(hashedBytes).Replace("-", "").ToLower();
        }
    }
}

Output:

Original Password: mySecurePassword123
Hashed Password: 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

Using a Hash Table for User Lookup

We’ll use a Dictionary (a hash table implementation in C#) to store and retrieve user information.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a hash table to store user information
        Dictionary users = new Dictionary
        {
            { "john_doe", "5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8" },
            { "jane_smith", "6cf615d5bcaac778352a8f1f3360d23f02f34ec182e259897fd6ce485d7870d4" }
        };

        // Simulate a login attempt
        string username = "john_doe";
        string password = "mySecurePassword123";

        if (AuthenticateUser(users, username, password))
        {
            Console.WriteLine("Login successful!");
        }
        else
        {
            Console.WriteLine("Invalid username or password.");
        }
    }

    static bool AuthenticateUser(Dictionary users, string username, string password)
    {
        if (users.TryGetValue(username, out string storedHash))
        {
            string inputHash = HashPassword(password);
            return storedHash == inputHash;
        }
        return false;
    }

    static string HashPassword(string password)
    {
        using (SHA256 sha256 = SHA256.Create())
        {
            byte[] hashedBytes = sha256.ComputeHash(Encoding.UTF8.GetBytes(password));
            return BitConverter.ToString(hashedBytes).Replace("-", "").ToLower();
        }
    }
}

Real-Life Applications of Hashing

1. Databases:

   • Hash indexes are used to speed up data retrieval.

2. Caching:

   • Hash tables are used in caching mechanisms (e.g., Redis) to store and retrieve data quickly.

3. Cryptography:

   • Cryptographic hash functions (e.g., SHA-256) are used to secure sensitive data.

4. Compilers:

   • Hash tables are used to store and look up symbols (e.g., variable names) during compilation.

Part - 1

Hashing is a technique used to map data of arbitrary size to fixed-size values (hash values). It is widely used in data structures like hash tables, hash maps, and hash sets to achieve fast data retrieval, insertion, and deletion. Hashing is essential for optimizing search operations, as it allows for average-case O(1) time complexity for lookups.

1. Hash Function:

   • A function that takes an input (or "key") and returns a fixed-size string of bytes (hash value).

   • The output is typically an integer (hash code) that corresponds to an index in a hash table.

2. Hash Table:

   • A data structure that stores key-value pairs.

   • It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

3. Collision:

   • Occurs when two different keys produce the same hash value.

   • Common collision resolution techniques:

     • Store multiple items in the same bucket using a linked list.

     • Find another slot in the hash table using probing (e.g., linear probing, quadratic probing).

4. Load Factor:

   • The ratio of the number of elements stored in the hash table to the total number of slots.

   • A high load factor increases the likelihood of collisions.

 

Absolutely! I'd be happy to delve into the realm of Hashing Techniques in Data Structures and Algorithms with you. Hashing is a crucial concept in computer science and is widely used in various algorithms and data structures for efficient retrieval and storage of data.

Hashing involves mapping data of arbitrary size to fixed-size values, typically for indexing into a data structure like a hash table. The goal is to quickly locate a data record given its search key. Here are some common hashing techniques used in DSA:

1. Direct Addressing: This is a straightforward hashing technique where an array is used to store data records with their keys as indices. It is efficient when the keys are limited and can be directly used as indices.

2. Division Method: In this technique, the key is divided by a prime number, and the remainder is used as the hash value. The choice of the prime number is crucial to reduce clustering and achieve a more even distribution of keys.

3. Multiplication Method: This technique involves multiplying the key by a constant fraction and extracting the fractional part as the hash value. It helps in achieving a better distribution of keys compared to simpler methods.

4. Universal Hashing: Universal hashing involves selecting a random hash function from a family of hash functions. This ensures that even with a malicious adversary choosing the input, the expected time complexity remains optimal.

5. Collision Resolution: Handling collisions (cases where two keys hash to the same value) is crucial in hashing. Techniques like chaining (using linked lists at each hash table location) and open addressing (probing for an empty slot) are commonly used.

Here's a simple example in Python showcasing the Division Method:

# Hash function using Division Method
def hash_function(key, size):
    return key % size

# Hash table initialization
size = 10
hash_table = [None] * size

# Inserting key-value pairs
keys = [12, 34, 22, 45]
values = ["Alice", "Bob", "Charlie", "David"]

for i in range(len(keys)):
    index = hash_function(keys[i], size)
    hash_table[index] = values[i]

print(hash_table)

These techniques play a vital role in optimizing data retrieval and storage, commonly seen in databases, caches, and various algorithms like hash maps. Let me know if you would like further clarification or examples on any specific aspect of Hashing Techniques in DSA!