hashtable.cpp

#include "LinkedList.cpp"
#include <utility>
#include <typeinfo>

using namespace std;

template<class key_type, class value_type>
class HashTable {

	const int size;
	LinkedList<pair<key_type, value_type> > *_table;

public:

	HashTable() : size(128) {
		_table = new LinkedList<pair<key_type, value_type> > [size];
	}

	int hash(key_type key) {
		long sum = 0;
		for(int i = 0; i < key.size(); ++i) {
			sum += key[i];
		}

		return sum % size;

	}

	void insert(key_type key, value_type value) {
		auto it = find(key);

		if(it) {
			it->second = value;
		}
		else {
			int hash_value = hash(key);
			_table[hash_value].insert({key, value});		
		}
	}

	pair<key_type, value_type>* find(key_type key) {
		int hash_value = hash(key);

		LinkedListNode<pair<key_type, value_type> > *it = _table[hash_value].getHead();

		while(it != NULL and it->value.first != key) {
			it = it->next;
		}

		return &(it->value);
	}
};

linkedlist.cpp

using namespace std;

template<class type>
struct LinkedListNode {
	type value;
	LinkedListNode *next;

	LinkedListNode(type value) {
		this->value = value;
		this->next = NULL;
	}
};

template<class type>
class LinkedList {

	LinkedListNode<type> *head, *tail;

public:

	LinkedList() {
		head = tail = NULL;
	}

	void insert(type value) {
		if(head == NULL) {
			head = tail = new LinkedListNode<type>(value);
			return;
		}

		tail->next = new LinkedListNode<type>(value);
		tail = tail->next;
	}

	void print() {
		LinkedListNode<type> *iter = head;

		while(iter != NULL) {
			cout<<iter->value<<endl;
			iter = iter->next;
		}
	}

	LinkedListNode<type>* find(type value) {
		LinkedListNode<type> *iter = head;

		while(iter != NULL and iter->value != value)
			iter = iter->next;

		return iter;
	}

	LinkedListNode<type>* getHead() {
		return head;
	}

};