Hi, this is #day_4, we are going to talk about hash tables
Definition of Hash table
"A hash table is a type of data structure that stores key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table."
Application of hash tables
- Password verification
- File System
- Programming Language
- Rabin-Karp Algorithm
- School system
- Search Engines
- Driver's license record
Space and Time complexity
The space complexity of the hash table is O(n)
insert | delete | search | |
---|---|---|---|
Average | O(1) | O(1) | O(1) |
Worst | O(n) | O(n) | O(n) |
Collision
Collision is when two keys or more result the same value after hashing them.
example:
Data:
Name ( key ) | grade ( value ) |
---|---|
aya | 77 |
yaa | 83 |
Hash function example
def hashKey(self,key) -> int:
"""
ord -> built-in method that returns the Unicode code of a character
size -> the hash table length
using (hashedString % self.size) -> for not getting an index out of the range of our hash table length
"""
hashedString = 0
for character in key:
hashedString += ord(character)
return hashedString % self.size
Getting the hashed names ( hashed keys )
#! collision
print(table.hashKey('aya')) # 15
print(table.hashKey('yaa')) # 15
Solutions of the Collision problem
1. Open Addressing
Linear Probing : is inserting the value directly if the
table[hashedKey]
is empty else inserting It into the next valuetable[(key + 1) % sizeOfTheTable ]
if it available Otherwise tring for the next index until finding an empty place more details...Quadratic Probing : operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found more details...
Double Hashing : is applying another hash function to key
hashTable[(hashfunc1(key) + i * hashfunc2(key)) % sizeOfTheTable]
more details...
2. Separate Chainings
This technique creates a linked list to the slot for which collision occurs and insert into the wanted value as a node which has three properties (key, value, next)more details...
Implementation of the hash table (separate chaining) using python
Although Hash table are built-in data structure in programming languages such as dictionary in python, Map in javascript, let's try to implement it in python.
if you are not familiar with python you can find the implementation of hash table in other langauges in these links:
Node & Linked List Class
if you're not familiar with linked list check this article
class Node:
def __init__(self,key,value,next = None):
self.key = key
self.value = value
self.next = next
class LinkedList:
def __init__(self) :
self.head = None
self.size = 0
def insertAtFirst(self,key,value):
self.head = Node(key,value,self.head)
self.size += 1
def insertAtLast(self,key,value):
current = self.head
while current.next:
current = current.next
current.next = Node(key,value)
self.size+=1
def remove(self, key):
current = self.head
previous = None
if current.key == key:
self.head = current.next
else:
while current.next:
previous = current
current = current.next
if current.key == key:
previous.next = current.next
self.size -= 1
def find(self, key):
current = self.head
while current:
if current.key == key:
return current.value
current = current.next
def printAll(self):
current = self.head
while current:
print(current.key,current.value)
current = current.next
Hash Table Class
class HashTable:
def __init__(self,size):
self.table =[None] * size
self.size = size
hashKey method
def hashKey(self,key) -> int:
"""
ord -> built-in method that returns the Unicode code of a character
size -> the hash table length
using (hashedString % self.size) -> for not getting an index out of the range of our hash table length
"""
hashedString = 0
for character in key:
hashedString += ord(character)
return hashedString % self.size
add method
def add(self, key, value):
"""
The Logic:
self.table[idx] is None
=> create a linked list and insert into it a node that contains the giving key and the giving value
self.table[idx] is not None:
=> insert into the linked list a node that contains the giving key and the giving value
"""
idx = self.hashKey(key)
if self.table[idx] is None:
newLinkedList = LinkedList()
newLinkedList.insertAtFirst(key,value)
self.table[idx] = newLinkedList
else:
self.table[idx].insertAtLast(key, value)
get method
def get(self, key) -> any:
idx = self.hashKey(key)
if self.table[idx] is not None:
return self.table[idx].find(key)
delete method
def delete(self, key):
idx = self.hashKey(key)
if self.table[idx] is not None:
self.table[idx].remove(key)
printAll
def printAll(self):
for i in self.table:
if i is not None:
i.printAll()
All hash table methods
class HashTable:
def __init__(self,size):
self.table =[None] * size
self.size = size
def hashKey(self,key) -> int:
"""
ord -> built-in method that returns the Unicode code of a character
size -> the hash table length
using (hashedString % self.size) -> for not getting an index out of the range of our hash table length
"""
hashedString = 0
for character in key:
hashedString += ord(character)
return hashedString % self.size
def add(self, key, value):
"""
The Logic:
self.table[idx] is None
=> create a linked list and insert into it a node that contains the giving key and the giving value
self.table[idx] is not None:
=> insert into the linked list a node that contains the giving key and the giving value
"""
idx = self.hashKey(key)
if self.table[idx] is None:
newLinkedList = LinkedList()
newLinkedList.insertAtFirst(key,value)
self.table[idx] = newLinkedList
else:
self.table[idx].insertAtLast(key, value)
def get(self, key) -> any:
idx = self.hashKey(key)
if self.table[idx] is not None:
return self.table[idx].find(key)
def delete(self, key):
idx = self.hashKey(key)
if self.table[idx] is not None:
self.table[idx].remove(key)
def printAll(self):
for i in self.table:
if i is not None:
i.printAll()
Final Code
class Node:
def __init__(self,key,value,next = None):
self.key = key
self.value = value
self.next = next
class LinkedList:
def __init__(self) :
self.head = None
self.size = 0
def insertAtFirst(self,key,value):
self.head = Node(key,value,self.head)
self.size += 1
def insertAtLast(self,key,value):
current = self.head
while current.next:
current = current.next
current.next = Node(key,value)
self.size+=1
def remove(self, key):
current = self.head
previous = None
if current.key == key:
self.head = current.next
else:
while current.next:
previous = current
current = current.next
if current.key == key:
previous.next = current.next
self.size -= 1
def find(self, key):
current = self.head
while current:
if current.key == key:
return current.value
current = current.next
def printAll(self):
current = self.head
while current:
print(current.key,current.value)
current = current.next
class HashTable:
def __init__(self,size):
self.table =[None] * size
self.size = size
def hashKey(self,key) -> int:
"""
ord -> built-in method that returns the Unicode code of a character
size -> the hash table length
using (hashedString % self. size) -> for not getting an index out of the range of our hash table length
"""
hashedString = 0
for character in key:
hashedString += ord(character)
return hashedString % self.size
def add(self, key, value):
"""
The Logic:
self.table[idx] is None
=> create a linked list and insert into it a node that contains the giving key and the giving value
self.table[idx] is not None:
=> insert into the linked list a node that contains the giving key and the giving value
"""
idx = self.hashKey(key)
if self.table[idx] is None:
newLinkedList = LinkedList()
newLinkedList.insertAtFirst(key,value)
self.table[idx] = newLinkedList
else:
self.table[idx].insertAtLast(key, value)
def get(self, key) -> any:
idx = self.hashKey(key)
if self.table[idx] is not None:
return self.table[idx].find(key)
def delete(self, key):
idx = self.hashKey(key)
if self.table[idx] is not None:
self.table[idx].remove(key)
def printAll(self):
for i in self.table:
if i is not None:
i.printAll()
Exercises
References and useful Resources
- https://en.wikipedia.org/wiki/Quadratic_probing
- https://www.geeksforgeeks.org/hashing-set-3-open-addressing/
- https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/
- https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/#:~:text=Separate%20chaining%20is%20one%20of,into%20a%20specific%20linked%20list.
- https://www.gatevidyalay.com/collision-resolution-techniques-separate-chaining/
- https://www.youtube.com/watch?v=1fEMyNXZynw
- https://www.youtube.com/watch?v=e1FbSMqyJRs
- https://www.geeksforgeeks.org/double-hashing/
- https://www.coursera.org/lecture/data-structures/applications-of-hashing-e4vuN
- https://www.youtube.com/watch?v=shs0KM3wKv8
- https://www.youtube.com/watch?v=sfWyugl4JWA
Have a great day :)
Top comments (2)
Great explaination @ayabouchiha
Thank you so much @mayankpathak 🙏🙏
Have a good day 😊