🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
Hash tables are a type of data structure that offers fast insertion, deletion, and search operations. Underlying a hash table is an array combined with a hashing function. This function maps keys to indices in the array, ensuring a quick retrieval of the value associated with a given key.
In this post, we'll walk you through a basic implementation of a hash table in C++.
2. Program Overview
Our program will:
1. Define a HashTable class that uses open addressing (linear probing) to handle collisions.
2. The HashTable class will have functions to:
- Insert a key-value pair.
- Search for a key and retrieve its associated value.
- Delete a key-value pair.
3. Demonstrate these functions in the main program.
3. Code Program
#include<iostream>
#include<vector>
using namespace std;
// Size for the hash table
const int TABLE_SIZE = 13;
// Entry for the hash table
class Entry {
public:
int key;
int value;
Entry(int key, int value) {
this->key = key;
this->value = value;
}
};
class HashTable {
private:
vector<Entry*> table;
// Hash function to compute index
int hash(int key) {
return key % TABLE_SIZE;
}
public:
// Constructor to initialize table
HashTable() {
table.assign(TABLE_SIZE, nullptr);
}
// Insert key-value into the hash table
void insert(int key, int value) {
int index = hash(key);
while(table[index] != nullptr && table[index]->key != key) {
index = (index + 1) % TABLE_SIZE; // Linear probing
}
if(table[index] != nullptr) {
delete table[index];
}
table[index] = new Entry(key, value);
}
// Search for a key and return its value
int get(int key) {
int index = hash(key);
while(table[index] != nullptr && table[index]->key != key) {
index = (index + 1) % TABLE_SIZE;
}
if(table[index] == nullptr) {
return -1; // Not found
}
return table[index]->value;
}
// Delete a key from the hash table
void remove(int key) {
int index = hash(key);
while(table[index] != nullptr) {
if(table[index]->key == key) {
delete table[index];
table[index] = nullptr;
return;
}
index = (index + 1) % TABLE_SIZE;
}
}
};
int main() {
HashTable ht;
ht.insert(1, 10);
ht.insert(2, 20);
ht.insert(3, 30);
cout << "Value for key 2: " << ht.get(2) << endl;
ht.remove(2);
cout << "Value for key 2 after removal: " << ht.get(2) << endl;
return 0;
}
Output:
Value for key 2: 20 Value for key 2 after removal: -1
4. Step By Step Explanation
1. The Entry class represents each key-value pair in the hash table.
2. Our HashTable class uses an array (implemented using a vector) to store these entries.
3. The hash function computes the index in the array for a given key by taking its modulo with the table size.
4. The insert method adds a key-value pair, using linear probing to find an open slot if the initial index is taken.
5. The get method retrieves the value associated with a given key, again using linear probing to handle collisions.
6. The remove method deletes a key-value pair from the hash table.
7. In the main function, we demonstrate inserting key-value pairs, retrieving a value, and deleting a key from the hash table.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment