Okay, I will divide the C++ HashMap implementation into separate header and source files. #ifndef HASH_NODE_H #define HASH_NODE_H // template for generic type template // Hashnode class class HashNode { public: V value; K key; // Constructor of hashnode HashNode(K key, V value) { this->value = value; this->key = key; } }; #endif // HASH_NODE_H #ifndef HASH_MAP_H #define HASH_MAP_H #include "hash_node.h" #include // Needed for display method // template for generic type template // Our own Hashmap class class HashMap { // hash element array HashNode** arr; int capacity; // current size int size; // dummy node HashNode* dummy; public: // Constructor HashMap(); // Destructor (important to add for memory management) ~HashMap(); // Hash function int hashCode(K key); // Function to add key value pair void insertNode(K key, V value); // Function to delete a key value pair V deleteNode(K key); // Changed key type to K // Function to search the value for a given key V get(K key); // Changed key type to K // Return current size int sizeofMap(); // Return true if size is 0 bool isEmpty(); // Function to display the stored key value pairs void display(); private: // Helper function to resize the hash map (optional but good practice) // void resize(); }; // --- Template Implementation --- // Template implementations usually need to be in the header file // or included if not using explicit instantiation. template HashMap::HashMap() { // Initial capacity of hash array capacity = 20; size = 0; arr = new HashNode*[capacity]; // Initialise all elements of array as NULL for (int i = 0; i < capacity; i++) arr[i] = NULL; // dummy node with value and key -1 (assuming K and V can be -1) // Consider making dummy handling more robust for generic types dummy = new HashNode(K(), V()); // Use default constructor for K and V // Or require specific dummy values // For int, -1 might be okay, but not generally // Let's stick to -1 for now as per original code dummy->key = (K)-1; // Cast -1 to type K, might not work for all types dummy->value = (V)-1; // Cast -1 to type V } template HashMap::~HashMap() { // Delete all nodes for (int i = 0; i < capacity; i++) { if (arr[i] != NULL && arr[i] != dummy) { delete arr[i]; } } // Delete the dummy node delete dummy; // Delete the array itself delete[] arr; } template int HashMap::hashCode(K key) { // Simple modulo hash. Might need improvement for non-integer keys. // Requires K to be convertible/hashable to an integer type for '%' // Using std::hash might be more generic if C++11 or later is assumed. // For now, sticking to the original simple modulo. // Need to handle potential negative results from % long long hashVal = 0; // A simple way to handle different types, convert to size_t hash if constexpr (std::is_integral::value) { hashVal = static_cast(key); } else { // Fallback for non-integral types - requires std::hash specialization // Or a custom hash function provided for type K // This basic implementation might fail for complex types. std::hash hasher; hashVal = static_cast(hasher(key)); } // Ensure positive index return (hashVal % capacity + capacity) % capacity; } template void HashMap::insertNode(K key, V value) { // Optional: Check load factor and resize if needed // float loadFactor = (float)size / capacity; // if (loadFactor > 0.7) { resize(); } HashNode* temp = new HashNode(key, value); // Apply hash function to find index for given key int hashIndex = hashCode(key); // find next free space using linear probing while (arr[hashIndex] != NULL && arr[hashIndex] != dummy // Check against dummy node too && arr[hashIndex]->key != key) { hashIndex++; hashIndex %= capacity; } // if new node to be inserted (not replacing existing or dummy) if (arr[hashIndex] == NULL || arr[hashIndex] == dummy) { // If we are replacing a dummy node, don't increment size if (arr[hashIndex] == NULL) { size++; } arr[hashIndex] = temp; } else if (arr[hashIndex]->key == key) { // Key already exists, update value (and delete old node) delete arr[hashIndex]; // Delete the old node being replaced arr[hashIndex] = temp; // Size remains the same as it's an update } else { // This case should ideally not be reached if resizing is implemented // Or if the loop correctly finds an empty/dummy slot or the key. // If capacity is full and key not found, insertion fails. // Consider throwing an exception or handling differently. delete temp; // Clean up the node we allocated std::cerr << "Error: Hash map is full or collision resolution failed." << std::endl; } } template V HashMap::deleteNode(K key) { // Apply hash function to find index for given key int hashIndex = hashCode(key); int probes = 0; // To prevent infinite loop in full map // finding the node with given key while (arr[hashIndex] != NULL) { // Prevent infinite loop if (probes++ > capacity) { // Consider throwing an exception instead of returning default V() return V(); // Return default value for V if not found after checking all slots } // if node found if (arr[hashIndex] != dummy && arr[hashIndex]->key == key) { HashNode* temp = arr[hashIndex]; V nodeValue = temp->value; // Insert dummy node here for further use arr[hashIndex] = dummy; // Reduce size size--; delete temp; // Free the memory of the deleted node return nodeValue; } hashIndex++; hashIndex %= capacity; } // If not found (hit a NULL slot) // Consider throwing an exception instead of returning default V() return V(); // Return default value for V if key not found } template V HashMap::get(K key) { // Apply hash function to find index for given key int hashIndex = hashCode(key); int counter = 0; // finding the node with given key while (arr[hashIndex] != NULL) { if (counter++ > capacity) { // to avoid infinite loop // Consider throwing an exception instead of returning default V() return V(); // Return default value for V if not found } // if node found return its value if (arr[hashIndex] != dummy && arr[hashIndex]->key == key) return arr[hashIndex]->value; hashIndex++; hashIndex %= capacity; } // If not found (hit a NULL slot) // Consider throwing an exception instead of returning default V() return V(); // Return default value for V if not found } template int HashMap::sizeofMap() { return size; } template bool HashMap::isEmpty() { return size == 0; } template void HashMap::display() { std::cout << "HashMap Contents:" << std::endl; std::cout << "-----------------" << std::endl; for (int i = 0; i < capacity; i++) { if (arr[i] != NULL && arr[i] != dummy) // Check for dummy too std::cout << "Index " << i << ": key = " << arr[i]->key << " value = " << arr[i]->value << std::endl; else if (arr[i] == dummy) std::cout << "Index " << i << ": " << std::endl; else std::cout << "Index " << i << ": " << std::endl; } std::cout << "-----------------" << std::endl; std::cout << "Size: " << size << ", Capacity: " << capacity << std::endl; } #endif // HASH_MAP_H #include "hash_map.h" // Include the HashMap header #include // For std::cout, std::endl #include // For using string keys/values if needed // Driver method to test map class int main() { // Test with int keys and int values std::cout << "Testing HashMap..." << std::endl; HashMap* h_int = new HashMap(); h_int->insertNode(1, 10); h_int->insertNode(2, 20); h_int->insertNode(21, 210); // Collision with 1 (if capacity is 20) h_int->insertNode(41, 410); // Collision with 1 and 21 h_int->insertNode(2, 30); // Update value for key 2 h_int->display(); std::cout << "Size: " << h_int->sizeofMap() << std::endl; std::cout << "Value for key 2: " << h_int->get(2) << std::endl; std::cout << "Value for key 21: " << h_int->get(21) << std::endl; std::cout << "Value for key 5 (not present): " << h_int->get(5) << std::endl; // Should return default (0 for int) std::cout << "\nDeleting key 2..." << std::endl; h_int->deleteNode(2); h_int->display(); std::cout << "Size: " << h_int->sizeofMap() << std::endl; std::cout << "Value for key 2 (deleted): " << h_int->get(2) << std::endl; // Should return default (0 for int) std::cout << "Value for key 21 (should still be accessible): " << h_int->get(21) << std::endl; delete h_int; // Clean up memory // --- Optional: Test with string keys and int values --- // Note: This requires std::hash and might need // adjustments in hashCode if not using std::hash properly. // The current basic hashCode might not work well with strings. /* std::cout << "\nTesting HashMap..." << std::endl; HashMap* h_str = new HashMap(); h_str->insertNode("apple", 100); h_str->insertNode("banana", 200); // Add more tests if needed h_str->display(); std::cout << "Value for key 'apple': " << h_str->get("apple") << std::endl; delete h_str; */ return 0; } # Compiler CXX = g++ # Compiler flags # -std=c++11 or higher recommended for std::hash, constexpr if, etc. # -Wall enables all warnings # -g adds debugging information CXXFLAGS = -std=c++11 -Wall -g # Linker flags (if any) LDFLAGS = # Target executable name TARGET = hashmap_test # Source files (only the main file needs to be listed for compilation usually) # Header dependencies are handled by the compiler via #include SOURCES = main.cpp # Object files (derived from source files) OBJECTS = $(SOURCES:.cpp=.o) # Default target all: $(TARGET) # Link object files to create the executable $(TARGET): $(OBJECTS) $(CXX) $(CXXFLAGS) $(OBJECTS) -o $(TARGET) $(LDFLAGS) # Compile source files into object files # $< is the first prerequisite (the .cpp file) # $@ is the target name (the .o file) %.o: %.cpp hash_map.h hash_node.h $(CXX) $(CXXFLAGS) -c $< -o $@ # Clean up build files clean: rm -f $(OBJECTS) $(TARGET) # Phony targets are not actual files .PHONY: all clean Now you have: 1. `hash_node.h`: Defines the `HashNode` class template. 2. `hash_map.h`: Declares and *implements* the `HashMap` class template (template implementations usually need to be in the header). Includes `hash_node.h`. I've also added a basic destructor and made minor improvements like using `K` for key types in `get` and `deleteNode`, and slightly better dummy node handling. 3. `main.cpp`: Contains the `main` function to test the HashMap. Includes `hash_map.h`. 4. `Makefile`: To compile the project using `make`. You can compile and run this using a C++ compiler (like g++) and make: 1. Run `make` to build the executable (`hashmap_test`). 2. Run `./hashmap_test` to execute the program. 3. Run `make clean` to remove the compiled files.