Hashing Problems Master List 📝

Welcome to this comprehensive guide on Hashing Problems Master List! This lesson is designed to help you understand and solve a variety of problems related to Hashing, a fundamental concept in Computer Science. Let's dive in!

What is Hashing? 🎯

Hashing is a technique used to map data of arbitrary size (like strings or integers) to a fixed size (like an array index) using a mathematical function, called a hash function. It's useful for creating data structures like hash tables, which provide fast data access.

Importance of Hashing 📝

Efficient Data Access: Hashing allows fast data access, as data is indexed by a fixed-size hash value.
Unique Keys: Hashing ensures that every data item gets a unique hash value, preventing collisions.
Data Structures: Hash tables, hash maps, and hash sets are all built on hashing.

Types of Hash Functions 🎯

Simple Hash Functions: These functions take input of any size and produce an output of fixed size.
Division Method: A simple hash function that uses the formula hash(key) = key mod m, where m is the size of the hash table.

Hashing Problems 🎯

In this section, we will explore various problems related to hashing, along with their solutions.

Problem 1: Simple Hash Table Implementation 📝

Implement a simple hash table using the division method.

Solution

python

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

    def hash_function(self, key):
        return key % self.size

    def set_item(self, key, value):
        hash_value = self.hash_function(key)
        self.table[hash_value] = (key, value)

    def get_item(self, key):
        hash_value = self.hash_function(key)
        item = self.table[hash_value]
        if item:
            return item[1]
        return None

    def delete_item(self, key):
        hash_value = self.hash_function(key)
        self.table[hash_value] = None

Quick Quiz

Question 1 of 1

What does the SimpleHashTable class do in the provided solution?

Problem 2: Handling Collisions 💡

Modify the SimpleHashTable to handle collisions.

Solution

python

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

    def hash_function(self, key):
        return key % self.size

    def get_index(self, key):
        index = self.hash_function(key)
        return index

    def get_load_factor(self):
        occupied_slots = sum(1 for i in range(self.size) if self.table[i])
        return occupied_slots / self.size

    def resize(self):
        new_table = [None] * (self.size * 2)
        for i in range(self.size):
            if self.table[i]:
                load_balance(self.table[i], new_table)
        self.size *= 2
        self.table = new_table

    def load_balance(self, item, table):
        old_index = item[0] % self.size
        new_index = old_index
        while table[new_index]:
            new_index += 1
        table[new_index] = item

    def set_item(self, key, value):
        if self.get_load_factor() >= self.load_factor:
            self.resize()
        index = self.get_index(key)
        self.table[index] = (key, value)

    def get_item(self, key):
        index = self.get_index(key)
        item = self.table[index]
        if item:
            return item[1]
        return None

    def delete_item(self, key):
        index = self.get_index(key)
        self.table[index] = None

Quick Quiz

Question 1 of 1

What does the HashTable class do in the provided solution?


## Conclusion 📝

Hashing is a crucial concept in Computer Science, enabling the creation of efficient data structures like hash tables. By understanding and solving these problems, you'll enhance your knowledge of hashing, preparing you for more complex projects in the future.

Happy coding! 🎯💡📝