Posted on Jun 16, 2021 • Edited on Jul 8, 2021

Hash Table data structure

#algorithms #beginners #codenewbie #python

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."

www.educative.io

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)

wikipedia
freeCodeCamp

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 value table[(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 keyhashTable[(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()