In Open Addressing, all elements are stored directly in the hash table itself. Therefore, the size of the hash table must be greater than the total number of keys. To maintain good performance, the load factor (number of keys divided by table size) should be kept below a certain limit, usually 0.7. If needed, the table size can be increased by rehashing the existing elements.
Insert(k): The hash function is applied to the key to generate an index. If that slot is occupied, probing continues until an empty or deleted slot is found, and the key is inserted there.
Search(k): The hash function generates the starting index, and probing continues until the key is found or an empty slot is encountered.
Delete(k): Instead of removing an element completely, its slot is marked as "deleted" using a dummy node (key = –1, value = –1). This ensures that searching does not stop prematurely and that future insert operations can reuse deleted slots.
This process ensures that every key is mapped to a valid index within the hash table and that values are stored based on the position generated by the hash function. Searching, insertion, and deletion take O(1) average time, but in the worst case, these operations may take O(n) time if the table becomes too full or has many deleted slots.
Implementation:
Try it on GfG Practice
#include <bits/stdc++.h>
using namespace std;
// Class representing a single node in the hash map
class HashNode {
public:
int key, value;
// Constructor to initialize key-value pair
HashNode(int k, int v) {
key = k;
value = v;
}
};
// HashMap class using open addressing with linear probing
class HashMap {
int capacity; // Maximum size of the hash table
int size; // Current number of elements in the map
HashNode** arr; // Array of pointers to HashNode
HashNode* dummy; // Dummy node to mark deleted positions
public:
// Constructor
HashMap() {
capacity = 20; // Initial capacity
size = 0; // Initially empty
arr = new HashNode*[capacity];
// Initialize all positions as NULL
for (int i = 0; i < capacity; i++)
arr[i] = NULL;
// Dummy node represents a deleted slot
dummy = new HashNode(-1, -1);
}
// Simple hash function (modulo operation)
int hashCode(int key) {
return key % capacity;
}
// Rehashing function to resize the table when load factor >= 0.7
void rehash() {
HashNode** oldArr = arr;
int oldCap = capacity;
capacity *= 2; // Double the capacity
size = 0; // Reset size
arr = new HashNode*[capacity];
for (int i = 0; i < capacity; i++)
arr[i] = NULL;
// Re-insert all old elements into the new array
for (int i = 0; i < oldCap; i++) {
if (oldArr[i] != NULL && oldArr[i]->key != -1) {
insertNode(oldArr[i]->key, oldArr[i]->value);
}
}
}
// Insert a key-value pair into the hash map
void insertNode(int key, int value) {
// Rehash if load factor exceeds 0.7
if ((double)size / capacity >= 0.7)
rehash();
HashNode* temp = new HashNode(key, value);
int hashIndex = hashCode(key);
int counter = 0;
// Linear probing to find an empty or deleted slot
while (arr[hashIndex] != NULL &&
arr[hashIndex]->key != key &&
arr[hashIndex]->key != -1) {
if (counter++ >= capacity) // Prevent infinite loop
return;
hashIndex = (hashIndex + 1) % capacity;
}
// If inserting into empty or deleted slot, increase size
if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp; // Insert node
}
// Delete a key from the hash map
int deleteNode(int key) {
int hashIndex = hashCode(key);
int counter = 0;
// Linear probing to find the key
while (arr[hashIndex] != NULL) {
if (counter++ >= capacity)
return -1; // Key not found
if (arr[hashIndex]->key == key) {
int val = arr[hashIndex]->value;
delete arr[hashIndex]; // Free memory
arr[hashIndex] = dummy; // Mark as deleted
size--;
return val;
}
hashIndex = (hashIndex + 1) % capacity;
}
return -1; // Key not found
}
// Get value for a key
int get(int key) {
int hashIndex = hashCode(key);
int counter = 0;
// Linear probing to find the key
while (arr[hashIndex] != NULL) {
if (counter++ >= capacity)
return -1; // Key not found
if (arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex = (hashIndex + 1) % capacity;
}
return -1; // Key not found
}
// Get current number of elements in the map
int sizeofMap() {
return size;
}
// Check if the map is empty
bool isEmpty() {
return size == 0;
}
// Display all key-value pairs
void display() {
for (int i = 0; i < capacity; i++) {
if (arr[i] != NULL && arr[i]->key != -1)
cout << arr[i]->key << " " << arr[i]->value << endl;
}
}
};
int main() {
HashMap h;
// Insert elements
h.insertNode(1, 10);
h.insertNode(2, 20);
h.insertNode(3, 30);
h.insertNode(22, 220);
h.insertNode(42, 420);
cout << "Hash Map Elements:\n";
h.display(); // Display elements
cout << "\nSize of map: " << h.sizeofMap() << endl;
// Delete a key
cout << "\nDeleting key 2 -> " << h.deleteNode(2) << endl;
cout << "Size after deletion: " << h.sizeofMap() << endl;
// Access values
cout << "\nValue of key 3: " << h.get(3) << endl;
cout << "Value of key 2: " << h.get(2) << endl; // Key 2 deleted
// Check if map is empty
cout << "\nIs map empty? " << (h.isEmpty() ? "Yes" : "No") << endl;
return 0;
}
import java.lang.*;
class hashNode {
int key;
int value;
// constructor
public hashNode(int key, int value) {
this.key = key;
this.value = value;
}
}
class hashMap {
hashNode[] arr;
int capacity;
int size;
hashNode dummy;
// constructor
public hashMap() {
capacity = 20;
size = 0;
arr = new hashNode[capacity];
dummy = new hashNode(-1, -1);
}
// hash function
int hashCode(int key) {
return key % capacity;
}
// insert key-value pair
void insertNode(int key, int value) {
hashNode temp = new hashNode(key, value);
int hashIndex = hashCode(key);
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;
}
// delete by key
int deleteNode(int key) {
int hashIndex = hashCode(key);
while (arr[hashIndex] != null) {
if (arr[hashIndex].key == key) {
hashNode temp = arr[hashIndex];
arr[hashIndex] = dummy;
size--;
return temp.value;
}
hashIndex++;
hashIndex %= capacity;
}
return -1;
}
// get value by key
int get(int key) {
int hashIndex = hashCode(key);
int counter = 0;
while (arr[hashIndex] != null) {
if (counter++ > capacity)
return -1;
if (arr[hashIndex].key == key)
return arr[hashIndex].value;
hashIndex++;
hashIndex %= capacity;
}
return -1;
}
// size of map
int sizeofMap() {
return size;
}
// check if map is empty
boolean isEmpty() {
return size == 0;
}
// display key-value pairs
void display() {
for (int i = 0; i < capacity; i++) {
if (arr[i] != null && arr[i].key != -1) {
System.out.println(arr[i].key +
" " + arr[i].value);
}
}
}
public static void main(String[] args) {
hashMap h = new hashMap();
h.insertNode(1, 1);
h.insertNode(2, 2);
h.insertNode(2, 3);
h.display();
System.out.println(h.sizeofMap());
System.out.println(h.deleteNode(2));
System.out.println(h.sizeofMap());
System.out.println(h.isEmpty());
System.out.println(h.get(2));
}
}
class hashNode:
# constructor
def __init__(self, key, value):
self.key = key
self.value = value
class hashMap:
# constructor
def __init__(self):
self.capacity = 20
self.size = 0
self.arr = [None] * self.capacity
self.dummy = hashNode(-1, -1)
# hash function
def hashCode(self, key):
return key % self.capacity
# insert key-value pair
def insertNode(self, key, value):
temp = hashNode(key, value)
hashIndex = self.hashCode(key)
while self.arr[hashIndex] is not None and \
self.arr[hashIndex].key != key and \
self.arr[hashIndex].key != -1:
hashIndex = (hashIndex + 1) % self.capacity
if self.arr[hashIndex] is None or \
self.arr[hashIndex].key == -1:
self.size += 1
self.arr[hashIndex] = temp
# delete by key
def deleteNode(self, key):
hashIndex = self.hashCode(key)
while self.arr[hashIndex] is not None:
if self.arr[hashIndex].key == key:
temp = self.arr[hashIndex]
self.arr[hashIndex] = self.dummy
self.size -= 1
return temp.value
hashIndex = (hashIndex + 1) % self.capacity
return -1
# get value by key
def get(self, key):
hashIndex = self.hashCode(key)
counter = 0
while self.arr[hashIndex] is not None:
if counter > self.capacity:
return -1
if self.arr[hashIndex].key == key:
return self.arr[hashIndex].value
hashIndex = (hashIndex + 1) % self.capacity
counter += 1
return -1
# return map size
def sizeofMap(self):
return self.size
# check if map is empty
def isEmpty(self):
return self.size == 0
# display all key-value pairs
def display(self):
for node in self.arr:
if node is not None and node.key != -1:
print(f"{node.key} {node.value}")
if __name__ == "__main__":
h = hashMap()
h.insertNode(1, 1)
h.insertNode(2, 2)
h.insertNode(2, 3)
h.display()
print(h.sizeofMap())
print(h.deleteNode(2))
print(h.sizeofMap())
print(str(h.isEmpty()).lower())
print(h.get(2))
using System;
class hashNode {
public int key;
public int value;
// constructor
public hashNode(int key, int value) {
this.key = key;
this.value = value;
}
}
class hashMap {
hashNode[] arr;
int capacity;
int size;
hashNode dummy;
// constructor
public hashMap() {
capacity = 20;
size = 0;
arr = new hashNode[capacity];
dummy = new hashNode(-1, -1);
}
// hash function
int hashCode(int key) {
return key % capacity;
}
// insert key-value pair
public void insertNode(int key, int value) {
hashNode temp = new hashNode(key, value);
int hashIndex = hashCode(key);
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;
}
// delete by key
public int deleteNode(int key) {
int hashIndex = hashCode(key);
while (arr[hashIndex] != null) {
if (arr[hashIndex].key == key) {
hashNode temp = arr[hashIndex];
arr[hashIndex] = dummy;
size--;
return temp.value;
}
hashIndex++;
hashIndex %= capacity;
}
return -1;
}
// get value by key
public int get(int key) {
int hashIndex = hashCode(key);
int counter = 0;
while (arr[hashIndex] != null) {
if (counter++ > capacity)
return -1;
if (arr[hashIndex].key == key)
return arr[hashIndex].value;
hashIndex++;
hashIndex %= capacity;
}
return -1;
}
// size of map
public int sizeofMap() {
return size;
}
// check if map is empty
public bool isEmpty() {
return size == 0;
}
// display key-value pairs
public void display() {
for (int i = 0; i < capacity; i++) {
if (arr[i] != null && arr[i].key != -1) {
Console.WriteLine(arr[i].key +
" " + arr[i].value);
}
}
}
static void Main(string[] args) {
hashMap h = new hashMap();
h.insertNode(1, 1);
h.insertNode(2, 2);
h.insertNode(2, 3);
h.display();
Console.WriteLine(h.sizeofMap());
Console.WriteLine(h.deleteNode(2));
Console.WriteLine(h.sizeofMap());
Console.WriteLine(h.isEmpty().
ToString().ToLower());
Console.WriteLine(h.get(2));
}
}
class hashNode {
constructor(key, value) {
this.key = key;
this.value = value;
}
}
class hashMap {
constructor() {
this.capacity = 20;
this.size = 0;
this.arr = new Array(this.capacity).fill(null);
this.dummy = new hashNode(-1, -1);
}
hashCode(key) {
return key % this.capacity;
}
insertNode(key, value) {
let temp = new hashNode(key, value);
let hashIndex = this.hashCode(key);
while (this.arr[hashIndex] !== null &&
this.arr[hashIndex].key !== key &&
this.arr[hashIndex].key !== -1) {
hashIndex = (hashIndex + 1) % this.capacity;
}
if (this.arr[hashIndex] === null || this.arr[hashIndex].key === -1)
this.size++;
this.arr[hashIndex] = temp;
}
deleteNode(key) {
let hashIndex = this.hashCode(key);
while (this.arr[hashIndex] !== null) {
if (this.arr[hashIndex].key === key) {
let temp = this.arr[hashIndex];
this.arr[hashIndex] = this.dummy;
this.size--;
return temp.value;
}
hashIndex = (hashIndex + 1) % this.capacity;
}
return -1;
}
get(key) {
let hashIndex = this.hashCode(key);
let counter = 0;
while (this.arr[hashIndex] !== null) {
if (counter++ > this.capacity)
return -1;
if (this.arr[hashIndex].key === key)
return this.arr[hashIndex].value;
hashIndex = (hashIndex + 1) % this.capacity;
}
return -1;
}
sizeofMap() {
return this.size;
}
isEmpty() {
return this.size === 0;
}
display() {
for (let i = 0; i < this.capacity; i++) {
let node = this.arr[i];
if (node !== null && node.key !== -1)
console.log(`${node.key} ${node.value}`);
}
}
}
// Driver Code
let h = new hashMap();
h.insertNode(1, 1);
h.insertNode(2, 2);
h.insertNode(2, 3);
h.display();
console.log(h.sizeofMap());
console.log(h.deleteNode(2));
console.log(h.sizeofMap());
console.log(h.isEmpty());
console.log(h.get(2));
Output
Hash Map Elements: 1 10 2 20 3 30 22 220 42 420 Size of map: 5 Deleting key 2 -> 20 Size after deletion: 4 Value of key 3: 30 Value of key 2: -1 Is map empty? No
Complexity analysis for Insertion:
Time Complexity:
- Best Case: O(1)
- Worst Case: O(n). This happens when all elements have collided and we need to insert the last element by checking free space one by one.
- Average Case: O(1) for good hash function, O(n) for bad hash function
Auxiliary Space: O(1)
Complexity analysis for Deletion:
Time Complexity:
- Best Case: O(1)
- Worst Case: O(n)
- Average Case: O(1) for good hash function; O(n) for bad hash function
Auxiliary Space: O(1)
Complexity analysis for Searching:
Time Complexity:
- Best Case: O(1)
- Worst Case: O(n)
- Average Case: O(1) for good hash function; O(n) for bad hash function
Auxiliary Space: O(1) for search operation