4. Example: Full Manual Implementation
This chapter combines all the concepts from Chapters 2 and 3 into a single, complete MyHashMap class. This class handles insertion, searching, deletion, and automatic rehashing.
4.1. Manual Implementation Using Separate Chaining
#include <iostream>
#include <string>
#include <vector>
#include <list>
// Data Node: Struct to store Key-Value pairs
struct KeyValuePair {
std::string key;
int value;
KeyValuePair(std::string k, int v) : key(k), value(v) {}
};
class MyHashMap {
private:
int n; // Number of items
int m; // Number of buckets (table size)
std::vector<std::list<KeyValuePair>> table;
const float MAX_LOAD_FACTOR = 0.75;
// Hash Function (Simple Division Method)
int hashFunction(std::string key) {
int hash = 0;
// A simple hash: sum ASCII values
for (char c : key) {
hash = (hash + (int)c);
}
return hash % m; // Use current table size 'm'
}
// Rehashing Function
void rehash() {
// Get old table and size
std::vector<std::list<KeyValuePair>> oldTable = table;
int oldSize = m;
// Allocate new, larger table
m = m * 2;
table.clear();
table.resize(m);
n = 0; // Reset item count
std::cout << ". New size: " << m << std::endl;
// Re-insert all elements from old table
for (int i = 0; i < oldSize; ++i) {
for (auto& pair : oldTable[i]) {
// Re-hash and insert into new table
insert(pair.key, pair.value);
}
}
}
public:
// Constructor: Initialize table
MyHashMap(int size = 10) { // Default size of 10
n = 0;
m = size;
table.resize(m);
}
// Insert Function (with rehashing)
void insert(std::string key, int value) {
// Check load factor before inserting
if ((float)(n + 1) / m > MAX_LOAD_FACTOR) {
rehash();
}
// Hash the key (uses the new 'm' if rehashed)
int index = hashFunction(key);
// Traverse chain to find or update
for (auto& pair : table[index]) {
if (pair.key == key) {
pair.value = value;
return;
}
}
// Not found, add new pair and increment item count
table[index].push_back(KeyValuePair(key, value));
n++;
}
// Search Function
int search(std::string key) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.key == key) {
return pair.value;
}
}
return -1; // Not found
}
// Remove Function
void remove(std::string key) {
int index = hashFunction(key);
auto& chain = table[index];
for (auto it = chain.begin(); it != chain.end(); ++it) {
if (it->key == key) {
chain.erase(it); // Remove element at position 'it'
n--; // Decrement item count
return;
}
}
}
};
4.2. Manual Implementation Using Open Addressing
#include <iostream>
#include <string>
#include <vector>
// Define the state for each slot
enum class SlotState {
EMPTY, // The slot has never been used
OCCUPIED, // The slot contains an active key-value pair
DELETED // The slot used to have data, but it was removed
};
struct HashSlot {
std::string key;
int value;
SlotState state;
// Constructor to initialize new slots as EMPTY
HashSlot() : key(""), value(0), state(SlotState::EMPTY) {}
};
class MyHashMap {
private:
int n; // Number of items
int m; // Number of buckets (table size)
std::vector<HashSlot> table;
const float MAX_LOAD_FACTOR = 0.75;
// Hash Function (Simple Division Method)
int hashFunction(std::string key) {
int hash = 0;
for (char c : key) {
hash = (hash + (int)c);
}
// Ensure hash is positive before modulo
return (hash & 0x7FFFFFFF) % m;
}
// Rehashing Function
void rehash() {
std::cout << "[Info] Rehashing triggered. Old size: " << m;
// Save the old table
std::vector<HashSlot> oldTable = table;
int oldSize = m;
// Create a new, larger table.
m = m * 2;
table.clear();
table.resize(m);
n = 0; // Reset item count
std::cout << ". New size: " << m << std::endl;
// 6. Re-insert all active elements from the old table
for (int i = 0; i < oldSize; ++i) {
// Only re-insert items that are currently occupied
if (oldTable[i].state == SlotState::OCCUPIED) {
insert(oldTable[i].key, oldTable[i].value);
}
}
}
public:
// Constructor: Initialize table
MyHashMap(int size = 10) { // Default size of 10
n = 0;
m = size;
table.resize(m);
}
// Insert Function
void insert(std::string key, int value) {
// Check load factor before inserting
if ((float)(n + 1) / m > MAX_LOAD_FACTOR) {
rehash();
}
// Get the initial hash index
int index = hashFunction(key);
int firstDeletedSlot = -1; // To store the index of the first DELETED slot
// Start probing (loop max 'm' times)
for (int i = 0; i < m; ++i) {
int probedIndex = (index + i) % m;
auto& slot = table[probedIndex]; // Get a reference to the slot
// Case 1: Slot is OCCUPIED and the key matches
if (slot.state == SlotState::OCCUPIED && slot.key == key) {
// Key already exists, just update the value
slot.value = value;
return;
}
// Case 2: Slot is EMPTY
if (slot.state == SlotState::EMPTY) {
// We found an empty slot, so the key is not in the table.
// We should insert it here, OR in the first DELETED slot we found.
int insertIndex = (firstDeletedSlot != -1) ? firstDeletedSlot : probedIndex;
table[insertIndex].key = key;
table[insertIndex].value = value;
table[insertIndex].state = SlotState::OCCUPIED;
n++; // Increment item count
return;
}
// Case 3: Slot is DELETED
if (slot.state == SlotState::DELETED) {
// We can insert here, but we must keep searching
// to see if the key already exists further down the probe chain.
if (firstDeletedSlot == -1) {
firstDeletedSlot = probedIndex;
}
}
}
}
// Search Function
int search(std::string key) {
// Get the initial hash index
int index = hashFunction(key);
// Start probing
for (int i = 0; i < m; ++i) {
int probedIndex = (index + i) % m;
auto& slot = table[probedIndex];
// Case 1: Slot is OCCUPIED and key matches
if (slot.state == SlotState::OCCUPIED && slot.key == key) {
return slot.value; // Item found
}
// Case 2: Slot is EMPTY
if (slot.state == SlotState::EMPTY) {
// If we hit an EMPTY slot, the key cannot be
// further down the probe chain.
return -1; // Not found
}
// Case 3: Slot is DELETED
// We must continue probing, as the key we want
// might have collided and be after this deleted slot.
if (slot.state == SlotState::DELETED) {
continue;
}
}
// We looped through the entire table and didn't find it
return -1;
}
// Remove Function
void remove(std::string key) {
int index = hashFunction(key);
// Start probing to find the key
for (int i = 0; i < m; ++i) {
int probedIndex = (index + i) % m;
auto& slot = table[probedIndex];
// Case 1: Slot is OCCUPIED and key matches
if (slot.state == SlotState::OCCUPIED && slot.key == key) {
// Found it. Set state to DELETED.
slot.state = SlotState::DELETED;
n--; // Decrement item count
return;
}
// Case 2: Slot is EMPTY
if (slot.state == SlotState::EMPTY) {
// Key is not in the table
return;
}
// Case 3: Slot is DELETED
if (slot.state == SlotState::DELETED) {
// Keep probing
continue;
}
}
}
};
No comments to display
No comments to display