Hash Function Properties 🎯

Welcome to our deep dive into the fascinating world of Hash Functions! In this lesson, we'll explore various properties that make hash functions an essential tool in data structures and algorithms. Let's get started!

What are Hash Functions? 📝

Hash functions are mathematical functions used to map data of arbitrary size to a fixed-size string, typically an integer. They play a crucial role in many real-world applications, such as data compression, database indexing, and password hashing.

Properties of Hash Functions 💡

1. Deterministic

A good hash function should always produce the same output given the same input, ensuring consistency and predictability.

2. Easy to Compute

Hash functions should be easy to calculate, allowing for fast execution in real-world applications.

3. Fast

Ideally, hash functions should be designed to be fast, enabling quick data processing and reducing computational overhead.

4. Unique Output

For distinct inputs, a good hash function should always produce different outputs, maximizing the chances of unique values in hash tables.

5. Low Collision Rate

Although unique outputs are desirable, it's impossible to have zero collisions for all inputs. A good hash function should minimize collisions, ensuring efficient data handling.

6. Pseudorandom

A perfect hash function will produce outputs that appear random, making it challenging to predict the outcome for a given input.

Common Types of Hash Functions 📝

Simple Hashing: Uses basic arithmetic operations to generate hash values.
Division Hashing: Uses the division method to map keys to array indices.
Mid-Square Method: Squares a key and extracts certain bits as the hash value.
Hash Chaining: Combines hashing with linked lists to manage collisions effectively.

Code Examples 💡

Simple Hashing in Python

python

def simple_hash(key, table_size=10):
    total = 0
    for char in key:
        total += ord(char)
    return total % table_size

# Example usage
table = [None] * 10
key1 = "apple"
key2 = "banana"

# Hash keys and store values
table[simple_hash(key1)] = "Apple"
table[simple_hash(key2)] = "Banana"

# Retrieve values
print(table[simple_hash(key1)])  # Output: Apple
print(table[simple_hash(key2)])  # Output: Banana

Hash Chaining in Python

python

class HashTable:
    def __init__(self, size):
        self.table = [None] * size

    def hash_function(self, key, table_size):
        total = 0
        for char in key:
            total += ord(char)
        return total % table_size

    def store(self, key, value):
        index = self.hash_function(key, len(self.table))

        if self.table[index] is None:
            self.table[index] = [key, value]
        else:
            self.table[index].append([key, value])

    def retrieve(self, key):
        index = self.hash_function(key, len(self.table))

        for item in self.table[index]:
            if item[0] == key:
                return item[1]

# Example usage
ht = HashTable(10)
ht.store("apple", "Apple")
ht.store("banana", "Banana")

print(ht.retrieve("apple"))  # Output: Apple
print(ht.retrieve("banana"))  # Output: Banana

Hash Function Properties 🎯

Hash Function Properties 🎯

What are Hash Functions? 📝

Properties of Hash Functions 💡

1. Deterministic

2. Easy to Compute

3. Fast

4. Unique Output

5. Low Collision Rate

6. Pseudorandom

Common Types of Hash Functions 📝

Code Examples 💡

Simple Hashing in Python

Hash Chaining in Python

Quiz 💡