Seperate chain HashMap implementation in cpp.

hashmap.cpp

#include <iostream>
#include <vector>
using namespace std;

/**
 * Separate Chain HashMap implementation in C++
 * https://gist.github.com/abhinavvsinhaa/c6593a0076a048a2dc2c915331c3cc9d
 */
template <typename K, typename V> 
class Node {
	int hash;
	K key;
	V value;
	Node<K,V>* next;

	template <typename Y, typename Z> friend class HashMap;

public:
	Node() {}

	Node(K key, V value) {
		this->key = key;
		this->value = value; 
		this->next = NULL;
		// this->hash = hash(key);
	}
};

template <typename K, typename V> 
class HashMap {
private:	
	const static int DEFAULT_CAPACITY = 3;
	constexpr static float LOAD_FACTOR = 0.75;


	int capacity; // capacity of the hash table, i.e. total no. of elements allowed
	float load_factor; // no. of elements / capacity = load_factor
	int threshold; // capacity * load_factor, if no. of elements exceeds this threshold, we'll resize the hash table
	
	int cur_size = 0; // to store the current number of elements in the hash table
	
	vector<Node<K,V>*> table; // hash table

	// hash function
	size_t hashCode(K key) {
		// for integer type
		if (typeid(key).name() == typeid(int).name()) {
			return (size_t)((abs(key)) % capacity);
		}

		return 0;
	}

public:
	// constructor
	HashMap(int cap = DEFAULT_CAPACITY) {
		capacity = cap; 

		// load_factor = no. of elements in the hash table / capacity of the hash table
		load_factor = LOAD_FACTOR;

		// if the size of table exceeds this limit, we will increase the size of the hash table
		threshold = cap * load_factor; 
		cout << "Threshold: " << threshold << "\n\n";

		table = vector<Node<K,V>*>(capacity, NULL);
	}

	// size function
	int size(int key) {
		return cur_size;
	}

	// isEmpty function
	bool isEmpty() {
		return cur_size == 0;
	}

	// add function
	void add(K key, V value) {
		// get the index from the hash function
		size_t ind = hashCode(key);
		cout << "INSERTING AT INDEX: " << ind << "\n";

		// checks if the bucket at index "ind" is NULL, then create a new Linked list, otherwise append
		if (table[ind] == NULL) {
			cout << "INDEX NULL, CREATING NEW LIST" << "\n\n";
			// create a new linked list
			Node<K,V>* head = new Node<K,V>(key, value);
			table[ind] = head;
			
			++cur_size;
		} else {
			cout << "INDEX NOT NULL, SEPERATE CHAINING AT: " << ind << endl;
			// traverse to the last node
			Node<K,V>* tmp = table[ind];
			while (tmp && tmp->next) {
				tmp = tmp->next;
			}

			// create a new node and append
			Node<K,V>* node = new Node<K,V>(key, value);
			tmp->next = node;
			++cur_size;
		}

		// create a new hash table and rehash all the elements from the old hash table into the new hash table
		if (cur_size > threshold) {
			resize();
		}
	}

	// resize function
	void resize() {
		cout << "\n-----------RESIZING-----------" << "\n\n";
		
		int old_capacity = capacity;

		capacity = capacity * 2; // increasing the capacity by 2x
		threshold = capacity * load_factor; // calculating new threshold

		// creating a new hash table with double the capacity
		vector<Node<K,V>*> new_table(capacity, NULL);

		// rehashing key value pairs
		for (int i=0; i<old_capacity; i++) {
			if (table[i] != NULL) {
				
				Node<K,V>* node = table[i];

				size_t ind = hashCode(node->key);
				
				new_table[ind] = node;
			}
		}

		table = new_table;
	}

	// get function
	V get(K key) {
		size_t ind = hashCode(key);

		Node<K,V>* node = table[ind];

		while (node) {
			if (node->key == key) {
				return node->value;
			}

			node = node->next;
		}

		return V();
	}

	// set function
	void set(K key, V value) {
		size_t ind = hashCode(key);

		Node<K,V>* node = table[ind];

		while (node) {
			while (node) {
				if (node->key == key) {
					node->value = value;
					return;
				}
			}
			node = node->next;
		}
	}

	// print
	void print() {
		for (int i=0; i<capacity; i++) {
			if (table[i]) {
				Node<K,V>* node = table[i];
				while (node) {
					cout << node->key << ": " << node->value << endl;
					node = node->next;
				}
			}
		}
	}
	
	// destructor
	~HashMap() {
		for (int i = 0; i < capacity; i++) {
            Node<K, V>* node = table[i];
            while (node) {
                Node<K, V>* nextNode = node->next;
                delete node;
                node = nextNode;
            }
        }

	}
};



int main() {
	HashMap<int,int> mp;
	mp.add(1, 10);
	mp.add(2, 10);
	mp.add(4, 10);
	mp.add(5, 10);
	mp.add(3, 10);


	int marks = mp.get(1);
	cout << marks << endl;

	mp.set(3, 24);
	mp.print();

	return 0;
}