Program to implement Hash Table using Open Addressing
The task is to design a general Hash Table data structure with Collision case handled and that supports the Insert(), Find(), and Delete() functions.
Examples:
Suppose the operations are performed on an array of pairs, {{1, 5}, {2, 15}, {3, 20}, {4, 7}}. And an array of capacity 20 is used as a Hash Table:
- Insert(1, 5): Assign the pair {1, 5} at the index (1%20 =1) in the Hash Table.
- Insert(2, 15): Assign the pair {2, 15} at the index (2%20 =2) in the Hash Table.
- Insert(3, 20): Assign the pair {3, 20} at the index (3%20 =3) in the Hash Table.
- Insert(4, 7): Assign the pair {4, 7} at the index (4%20 =4) in the Hash Table.
- Find(4): The key 4 is stored at the index (4%20 = 4). Therefore, print the 7 as it is the value of the key, 4, at index 4 of the Hash Table.
- Delete(4): The key 4 is stored at the index (4%20 = 4). After deleting Key 4, the Hash Table has keys {1, 2, 3}.
- Find(4): Print -1, as the key 4 does not exist in the Hash Table.
Approach: The given problem can be solved by using the modulus Hash Function and using an array of structures as Hash Table, where each array element will store the {key, value} pair to be hashed. The collision case can be handled by Linear probing, open addressing. Follow the steps below to solve the problem:
- Define a node, structure say HashNode, to a key-value pair to be hashed.
- Initialize an array of the pointer of type HashNode, say *arr[] to store all key-value pairs.
- Insert(Key, Value): Insert the pair {Key, Value} in the Hash Table.
- Initialize a HashNode variable, say temp, with value {Key, Value}.
- Find the index where the key can be stored using the, Hash Function and then store the index in a variable say HashIndex.
- If arr[HashIndex] is not empty or there exists another Key, then do linear probing by continuously updating the HashIndex as HashIndex =(HashIndex+1)%capacity.
- If arr[HashIndex] is not null, then insert the given Node by assigning the address of temp to arr[HashIndex].
- Find(Key): Finds the value of the Key in the Hash Table.
- Find the index where the key may exist using a Hash Function and then store the index in a variable, say HashIndex.
- If the arr[HashIndex] contains the key, Key then returns the value of it.
- Otherwise, do linear probing by continuously updating the HashIndex as HashIndex =(HashIndex+1)%capacity. Then, if Key is found, then return the value of the Key at that HashIndex and then return true.
- If the Key is not found, then return -1 representing not found. Otherwise, return the value of the Key.
- Delete(Key): Deletes the Key from the Hash Table.
- Find the index where the key may exist using a Hash Function and then store the index in a variable, say HashIndex.
- If the arr[HashIndex] contains the key, Key then delete by assigning {-1, -1} to the arr[HashIndex] and then return true.
- Otherwise, do linear probing by continuously updating the HashIndex as HashIndex =(HashIndex+1)%capacity. Then, if Key is found then delete the value of the Key at that HashIndex and then return true.
- If the Key is not found, then the return is false.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; struct HashNode { int key; int value; }; const int capacity = 20; int size = 0; struct HashNode** arr; struct HashNode* dummy; // Function to add key value pair void insert( int key, int V) { struct HashNode* temp = ( struct HashNode*) malloc ( sizeof ( struct HashNode)); temp->key = key; temp->value = V; // Apply hash function to find // index for given key int hashIndex = key % capacity; // Find next free space while (arr[hashIndex] != NULL && arr[hashIndex]->key != key && arr[hashIndex]->key != -1) { hashIndex++; hashIndex %= capacity; } // If new node to be inserted // increase the current size if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1) size++; arr[hashIndex] = temp; } // Function to delete a key value pair int deleteKey( int key) { // Apply hash function to find // index for given key int hashIndex = key % capacity; // Finding the node with given // key while (arr[hashIndex] != NULL) { // if node found if (arr[hashIndex]->key == key) { // Insert dummy node here // for further use arr[hashIndex] = dummy; // Reduce size size--; // Return the value of the key return 1; } hashIndex++; hashIndex %= capacity; } // If not found return null return 0; } // Function to search the value // for a given key int find( int key) { // Apply hash function to find // index for given key int hashIndex = (key % capacity); int counter = 0; // Find the node with given key while (arr[hashIndex] != NULL) { int counter = 0; // If counter is greater than // capacity if (counter++ > capacity) break ; // If node found return its // value if (arr[hashIndex]->key == key) return arr[hashIndex]->value; hashIndex++; hashIndex %= capacity; } // If not found return // -1 return -1; } // Driver Code int main() { // Space allocation arr = ( struct HashNode**) malloc ( sizeof ( struct HashNode*) * capacity); // Assign NULL initially for ( int i = 0; i < capacity; i++) arr[i] = NULL; dummy = ( struct HashNode*) malloc ( sizeof ( struct HashNode)); dummy->key = -1; dummy->value = -1; insert(1, 5); insert(2, 15); insert(3, 20); insert(4, 7); if (find(4) != -1) cout << "Value of Key 4 = " << find(4) << endl; else cout << ( "Key 4 does not exists\n" ); if (deleteKey(4)) cout << ( "Node value of key 4 is deleted " "successfully\n" ); else { cout << ( "Key does not exists\n" ); } if (find(4) != -1) cout << ( "Value of Key 4 = %d\n" , find(4)); else cout << ( "Key 4 does not exists\n" ); } // This code is contributed by Lovely Jain |
C
// C program for the above approach #include <stdio.h> #include <stdlib.h> struct HashNode { int key; int value; }; const int capacity = 20; int size = 0; struct HashNode** arr; struct HashNode* dummy; // Function to add key value pair void insert( int key, int V) { struct HashNode* temp = ( struct HashNode*) malloc ( sizeof ( struct HashNode)); temp->key = key; temp->value = V; // Apply hash function to find // index for given key int hashIndex = key % capacity; // Find next free space while (arr[hashIndex] != NULL && arr[hashIndex]->key != key && arr[hashIndex]->key != -1) { hashIndex++; hashIndex %= capacity; } // If new node to be inserted // increase the current size if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1) size++; arr[hashIndex] = temp; } // Function to delete a key value pair int delete ( int key) { // Apply hash function to find // index for given key int hashIndex = key % capacity; // Finding the node with given // key while (arr[hashIndex] != NULL) { // if node found if (arr[hashIndex]->key == key) { // Insert dummy node here // for further use arr[hashIndex] = dummy; // Reduce size size--; // Return the value of the key return 1; } hashIndex++; hashIndex %= capacity; } // If not found return null return 0; } // Function to search the value // for a given key int find( int key) { // Apply hash function to find // index for given key int hashIndex = (key % capacity); int counter = 0; // Find the node with given key while (arr[hashIndex] != NULL) { int counter = 0; // If counter is greater than // capacity if (counter++ > capacity) break ; // If node found return its // value if (arr[hashIndex]->key == key) return arr[hashIndex]->value; hashIndex++; hashIndex %= capacity; } // If not found return // -1 return -1; } // Driver Code int main() { // Space allocation arr = ( struct HashNode**) malloc ( sizeof ( struct HashNode*) * capacity); // Assign NULL initially for ( int i = 0; i < capacity; i++) arr[i] = NULL; dummy = ( struct HashNode*) malloc ( sizeof ( struct HashNode)); dummy->key = -1; dummy->value = -1; insert(1, 5); insert(2, 15); insert(3, 20); insert(4, 7); if (find(4) != -1) printf ( "Value of Key 4 = %d\n" , find(4)); else printf ( "Key 4 does not exists\n" ); if ( delete (4)) printf ( "Node value of key 4 is deleted " "successfully\n" ); else { printf ( "Key does not exists\n" ); } if (find(4) != -1) printf ( "Value of Key 4 = %d\n" , find(4)); else printf ( "Key 4 does not exists\n" ); } |
Java
// Java program for the above approach class HashNode { int key; int value; public HashNode( int key, int value) { this .key = key; this .value = value; } } public class Main { static int capacity = 20 ; static int size = 0 ; static HashNode[] arr = new HashNode[capacity]; static HashNode dummy = new HashNode(- 1 , - 1 ); static void insert( int key, int value) { HashNode temp = new HashNode(key, value); int hashIndex = key % capacity; while (arr[hashIndex] != null && arr[hashIndex].key != key && arr[hashIndex].key != - 1 ) { hashIndex++; hashIndex %= capacity; } if (arr[hashIndex] == null || arr[hashIndex].key == - 1 ) { size++; } arr[hashIndex] = temp; } static int deleteKey( int key) { int hashIndex = key % capacity; while (arr[hashIndex] != null ) { if (arr[hashIndex].key == key) { arr[hashIndex] = dummy; size--; return 1 ; } hashIndex++; hashIndex %= capacity; } return 0 ; } static int find( int key) { int hashIndex = key % capacity; int counter = 0 ; while (arr[hashIndex] != null ) { if (counter > capacity) { break ; } if (arr[hashIndex].key == key) { return arr[hashIndex].value; } hashIndex++; hashIndex %= capacity; counter++; } return - 1 ; } public static void main(String[] args) { insert( 1 , 5 ); insert( 2 , 15 ); insert( 3 , 20 ); insert( 4 , 7 ); if (find( 4 ) != - 1 ) { System.out.println( "Value of Key 4 = " + find( 4 )); } else { System.out.println( "Key 4 does not exists" ); } if (deleteKey( 4 ) == 1 ) { System.out.println( "Node value of key 4 is deleted successfully" ); } else { System.out.println( "Key does not exists" ); } if (find( 4 ) != - 1 ) { System.out.println( "Value of Key 4 = " + find( 4 )); } else { System.out.println( "Key 4 does not exists" ); } } } //This code is cotriuted by shivamsharma215 |
Python3
# Python program for the above approach # Struct for HashNode class HashNode: def __init__( self , key: int , value: int ): self .key = key self .value = value # Constants capacity = 20 size = 0 # Array for HashNode arr = [ None ] * capacity # Dummy node dummy = HashNode( - 1 , - 1 ) # Function to add key value pair def insert(key: int , value: int ): global size temp = HashNode(key, value) # Apply hash function to find index for given key hash_index = key % capacity # Find next free space while arr[hash_index] is not None and arr[hash_index].key ! = key and arr[hash_index].key ! = - 1 : hash_index + = 1 hash_index % = capacity # If new node to be inserted increase the current size if arr[hash_index] is None or arr[hash_index].key = = - 1 : size + = 1 arr[hash_index] = temp # Function to delete a key value pair def delete_key(key: int ): global size hash_index = key % capacity # Finding the node with given key while arr[hash_index] is not None : # if node found if arr[hash_index].key = = key: # Insert dummy node here for further use arr[hash_index] = dummy # Reduce size size - = 1 # Return the value of the key return 1 hash_index + = 1 hash_index % = capacity # If not found return null return 0 # Function to search the value for a given key def find(key: int ): global size hash_index = key % capacity counter = 0 # Find the node with given key while arr[hash_index] is not None : if counter > capacity: break # If node found return its value if arr[hash_index].key = = key: return arr[hash_index].value hash_index + = 1 hash_index % = capacity counter + = 1 # If not found return -1 return - 1 # Driver code if __name__ = = "__main__" : # Space allocation insert( 1 , 5 ) insert( 2 , 15 ) insert( 3 , 20 ) insert( 4 , 7 ) if find( 4 ) ! = - 1 : print ( "Value of Key 4 = " , find( 4 )) else : print ( "Key 4 does not exists" ) if delete_key( 4 ): print ( "Node value of key 4 is deleted successfully" ) else : print ( "Key does not exists" ) if find( 4 ) ! = - 1 : print ( "Value of Key 4 = " , find( 4 )) else : print ( "Key 4 does not exists" ) # This code is contributed by Vikram_Shirsat |
C#
using System; // Class for HashNode class HashNode { public int Key { get ; set ; } public int Value { get ; set ; } public HashNode( int key, int value) { Key = key; Value = value; } } class HashMap { // Constants private const int Capacity = 20; private int size = 0; // Array for HashNode private HashNode[] arr = new HashNode[Capacity]; // Dummy node private readonly HashNode dummy = new HashNode(-1, -1); // Function to add key value pair public void Insert( int key, int value) { HashNode temp = new HashNode(key, value); // Apply hash function to find index for given key int hashIndex = key % Capacity; // Find next free space while (arr[hashIndex] != null && arr[hashIndex].Key != key && arr[hashIndex].Key != -1) { hashIndex++; hashIndex %= Capacity; } // If new node to be inserted, increase the current size if (arr[hashIndex] == null || arr[hashIndex].Key == -1) { size++; } arr[hashIndex] = temp; } // Function to delete a key value pair public bool DeleteKey( int key) { int hashIndex = key % Capacity; // Finding the node with given key while (arr[hashIndex] != null ) { // If node found if (arr[hashIndex].Key == key) { // Insert dummy node here for further use arr[hashIndex] = dummy; // Reduce size size--; // Return true, indicating successful deletion return true ; } hashIndex++; hashIndex %= Capacity; } // If key not found, return false return false ; } // Function to search the value for a given key public int Find( int key) { int hashIndex = key % Capacity; int counter = 0; // Find the node with given key while (arr[hashIndex] != null ) { if (counter > Capacity) { break ; } // If node found, return its value if (arr[hashIndex].Key == key) { return arr[hashIndex].Value; } hashIndex++; hashIndex %= Capacity; counter++; } // If key not found, return -1 return -1; } } class Program { // Driver code static void Main() { HashMap hashMap = new HashMap(); // Space allocation hashMap.Insert(1, 5); hashMap.Insert(2, 15); hashMap.Insert(3, 20); hashMap.Insert(4, 7); if (hashMap.Find(4) != -1) { Console.WriteLine( "Value of Key 4 = " + hashMap.Find(4)); } else { Console.WriteLine( "Key 4 does not exist" ); } if (hashMap.DeleteKey(4)) { Console.WriteLine( "Node value of key 4 is deleted successfully" ); } else { Console.WriteLine( "Key does not exist" ); } if (hashMap.Find(4) != -1) { Console.WriteLine( "Value of Key 4 = " + hashMap.Find(4)); } else { Console.WriteLine( "Key 4 does not exist" ); } } } |
Javascript
// Struct for HashNode class HashNode { constructor(key, value) { this .key = key; this .value = value; } } // Constants const capacity = 20; let size = 0; // Array for HashNode let arr = new Array(capacity); // Dummy node const dummy = new HashNode(-1, -1); // Function to add key value pair function insert(key, value) { let temp = new HashNode(key, value); // Apply hash function to find index for given key let hash_index = key % capacity; // Find next free space while (arr[hash_index] !== undefined && arr[hash_index].key !== key && arr[hash_index].key !== -1) { hash_index++; hash_index %= capacity; } // If new node to be inserted increase the current size if (arr[hash_index] === undefined || arr[hash_index].key === -1) { size++; } arr[hash_index] = temp; } // Function to delete a key value pair function delete_key(key) { let hash_index = key % capacity; // Finding the node with given key while (arr[hash_index] !== undefined) { // if node found if (arr[hash_index].key === key) { // Insert dummy node here for further use arr[hash_index] = dummy; // Reduce size size--; // Return the value of the key return 1; } hash_index++; hash_index %= capacity; } // If not found return null return 0; } // Function to search the value for a given key function find(key) { let hash_index = key % capacity; let counter = 0; // Find the node with given key while (arr[hash_index] !== undefined) { if (counter > capacity) { break ; } // If node found return its value if (arr[hash_index].key === key) { return arr[hash_index].value; } hash_index++; hash_index %= capacity; counter++; } // If not found return -1 return -1; } // Driver code // Space allocation insert(1, 5); insert(2, 15); insert(3, 20); insert(4, 7); if (find(4) !== -1) { console.log( "Value of Key 4 = " , find(4)); } else { console.log( "Key 4 does not exist" ); } if (delete_key(4)) { console.log( "Node value of key 4 is deleted successfully" ); } else { console.log( "Key does not exist" ); } if (find(4) !== -1) { console.log( "Value of Key 4 = " , find(4)); } else { console.log( "Key 4 does not exist" ); } |
Output
Value of Key 4 = 7 Node value of key 4 is deleted successfully Key 4 does not exists
Time Complexity: O(capacity), for each operation
Auxiliary Space: O(capacity)