Welcome to our deep dive into the fascinating world of Hashing in Python! This tutorial is designed to help both beginners and intermediates understand and apply this essential concept in programming. Let's start by understanding what hashing is all about!
In simple terms, hashing is a technique used to convert data (like strings or numbers) of arbitrary size into fixed size strings called hash codes. The primary purpose of hashing is to improve the efficiency of searching and comparing large amounts of data.
š” Pro Tip: Hashing is extensively used in data structures like hash tables, databases, and cryptography for fast lookup and efficient data management.
A hash function is a mathematical function that converts data of arbitrary size into a fixed size. The hash function we will be focusing on in this tutorial is the built-in Python function hash().
When two different data items produce the same hash code, it's called a collision. To handle collisions, we use different strategies like open addressing and chaining. Python primarily uses chaining, which will be explained later in the tutorial.
Let's get our hands dirty by creating a simple hash table in Python!
class SimpleHashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def get_hash(self, key):
return hash(key) % self.size
def set_item(self, key, value):
hash_index = self.get_hash(key)
while self.table[hash_index] is not None:
hash_index = (hash_index + 1) % self.size
self.table[hash_index] = [key, value]
def get_item(self, key):
hash_index = self.get_hash(key)
while self.table[hash_index] is not None:
if self.table[hash_index][0] == key:
return self.table[hash_index][1]
hash_index = (hash_index + 1) % self.size
return None
# Creating a hash table of size 5
my_hash_table = SimpleHashTable(5)
# Setting items in the hash table
my_hash_table.set_item("Apple", 1)
my_hash_table.set_item("Banana", 2)
my_hash_table.set_item("Cherry", 3)
my_hash_table.set_item("Durian", 4)
# Retrieving items from the hash table
print(my_hash_table.get_item("Apple")) # Output: 1
print(my_hash_table.get_item("Banana")) # Output: 2
What does the `hash()` function do in Python?
To handle collisions in our simple hash table, we will implement chaining by storing a list of key-value pairs at each table index. This way, when a collision occurs, we simply append the new key-value pair to the existing list at the colliding index.
class ChainedHashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def get_hash(self, key):
return hash(key) % self.size
def set_item(self, key, value):
hash_index = self.get_hash(key)
while self.table[hash_index] is not None:
if self.table[hash_index][0] == key:
self.table[hash_index].append(value)
return
hash_index = (hash_index + 1) % self.size
self.table[hash_index] = [key, [value]]
def get_item(self, key):
hash_index = self.get_hash(key)
while self.table[hash_index] is not None:
if self.table[hash_index][0] == key:
return self.table[hash_index][1][0]
hash_index = (hash_index + 1) % self.size
return None
# Creating a chained hash table of size 5
my_chained_hash_table = ChainedHashTable(5)
# Setting items in the chained hash table
my_chained_hash_table.set_item("Apple", 1)
my_chained_hash_table.set_item("Banana", 2)
my_chained_hash_table.set_item("Cherry", 3)
my_chained_hash_table.set_item("Durian", 4)
# Retrieving items from the chained hash table
print(my_chained_hash_table.get_item("Apple")) # Output: 1
print(my_chained_hash_table.get_item("Banana")) # Output: 2
How does chaining work in a hash table?
Congratulations on mastering the basics of hashing in Python! We've learned what hashing is, created a simple hash table, and understood how chaining works to handle collisions.
Now, you can apply these concepts to various projects, from managing data in applications to implementing efficient search algorithms.
š” Pro Tip: Always remember, hashing can greatly enhance the performance of your code, especially when dealing with large amounts of data.
Happy coding, and we'll see you in the next lesson! š