DEV Community

Cover image for Hash Table data structure
Aya Bouchiha
Aya Bouchiha

Posted on • Edited on

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

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
Enter fullscreen mode Exit fullscreen mode

Getting the hashed names ( hashed keys ) 

#! collision
print(table.hashKey('aya')) # 15
print(table.hashKey('yaa')) # 15
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Hash Table Class 

class HashTable:
    def __init__(self,size):
        self.table =[None] * size
        self.size = size
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

get method 

    def get(self, key) -> any:
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            return self.table[idx].find(key)
Enter fullscreen mode Exit fullscreen mode

delete method 

    def delete(self, key):
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            self.table[idx].remove(key)
Enter fullscreen mode Exit fullscreen mode

printAll 

    def printAll(self):
        for i in self.table:
            if i is not None:
                i.printAll()
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

Exercises

Exercises

References and useful Resources

Have a great day :)

Top comments (2)

Collapse
 
mayankpathak profile image
Mayank Pathak •

Great explaination @ayabouchiha

Collapse
 
ayabouchiha profile image
Aya Bouchiha •

Thank you so much @mayankpathak 🙏🙏
Have a good day 😊

Read next

code42cate profile image

Day 16: Introduction to DockerHub

Jonas Scholz -

mjoycemilburn profile image

NgSysV2-5.2: Git for Beginners

MartinJ -

elukuro profile image

Set Git to Recognize Case Changes

Heru Hartanto -

michael_linson_0078 profile image

Ping Pong game in Pygame python

Michael Linson -