Hash Function & Storage in Data Structures

What is a Hash Function?

A hash function is a function that takes input (or 'key') and returns an integer called a hash code or hash value, which is used as an index to store the associated data in a hash table.

How Data is Stored Using Hashing

• The hash function calculates an index based on the key.
• Data is stored at the computed index in a fixed-size array or table.
• If multiple keys hash to the same index, it's called a collision, and various methods are used to resolve collisions.

Popular Collision Handling Techniques

• Separate Chaining: Store multiple elements in a linked list at the same index.
• Open Addressing: Probe other locations in the table (linear probing, quadratic probing, double hashing).

Basic Hash Function Example in Python

This example sums the ASCII values of characters in a string and uses modulo to get an index within table size.

def hash_function(key, table_size):
    hash_sum = 0
    for char in key:
        hash_sum += ord(char)  # ASCII value of char
    return hash_sum % table_size

# Example usage:
table_size = 10
keys = ["Bob", "Alice", "Eve", "Charlie"]

for key in keys:
    print(f"Key: {key}, Hash value: {hash_function(key, table_size)}")

Storing Data Using Hash Function

Below is a simple hash table implementation with separate chaining collision handling.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return sum(ord(c) for c in key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        # Check if key exists, update
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        # Otherwise add new
        self.table[index].append([key, value])

    def search(self, key):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        return None

# Usage example
ht = HashTable(10)
ht.insert("Bob", 25)
ht.insert("Alice", 30)
ht.insert("Eve", 22)

print("Searching for Alice:", ht.search("Alice"))
print("Searching for Bob:", ht.search("Bob"))
print("Searching for Dan:", ht.search("Dan"))  # None