#include<iostream>
using namespace std;

template<typename KeyType,typename ValueType>
class HashNode {
public:
	KeyType key;//键
	ValueType value;//值
	HashNode* next;//链

	HashNode(const KeyType& key, const ValueType& value) {
		this->key = key;
		this->value = value;
		this->next = NULL;
	}
};

template<typename KeyType,typename ValueType>
class HashTable {
private:
	int size;//哈希表数组大小
	HashNode<KeyType, ValueType>** table;//存储哈希表节点的数组
	int hash(const KeyType& key)const {//第一个const代表传进来的键不能被改变，第二个代表不能改变哈希表成员变量
		int hashkey = key % size;
		if (hashkey < 0) {
			hashkey += size;//索引不能是负数，所以加一个哈希偏移
		}
		return hashkey;
	}
public:
	HashTable(int size = 256);
	~HashTable();
	void insert(const KeyType& key, const ValueType& value);
	void remove(const KeyType& key);
	bool find(const KeyType& key, ValueType& value)const;
};

template<typename KeyType, typename ValueType>
HashTable<KeyType,ValueType>::HashTable(int size) {
	this->size = size;
	this->table = new HashNode<KeyType, ValueType>* [size];//哈希表由一个个链表组成
	for (int i = 0; i < size; i++) {
		this->table[i] = NULL;
	}
}
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {
	//遍历数组每个元素删除
	for (int i = 0; i < size; i++) {
		if (table[i]) {//如果非空
			HashNode<KeyType, ValueType>* current = table[i];//链表头赋值给一个临时变量
			while (current) {//遍历链表
				HashNode<KeyType, ValueType>* temp = current->next;
				delete current;
				current = temp;
			}
			table[i] = NULL;//table[i]置空，不然就是野指针了
		}
	}
	delete table;
	table = NULL;
}
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {
	int index = hash(key);//利用哈希函数计算键的索引
	HashNode<KeyType, ValueType>* now = new HashNode<KeyType, ValueType>(key, value);//利用提供的键和值生成一个节点
	if (table[index] == NULL) {
		table[index] = now;//如果键对应的链表为空，则直接将该节点作为链表头
	}
	else {
		//头插法
		now->next = table[index];
		table[index] = now;
	}
}
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {
	int index = hash(key);//利用哈希函数计算键的索引
	if (table[index]) {//判断索引的链表是否为空
		//判断删除的键是否与链表头的相等
		if (table[index]->key == key) {
			HashNode<KeyType, ValueType>* next = table(index)->next;
			delete table[index];
			table[index] = next;
		}
		else {
			//如果不相同，缓存在current中
			HashNode<KeyType, ValueType>* current = table[index];
			while (current->next && current->next->key != key) {
				//如果current的键和要删除的键不相同，则继续往后遍历
				current = current->next;
			}
			if (current->next) {
				//把要删除节点的后继节点
				HashNode<KeyType, ValueType>* next = current->next->next;
				delete current->next;//清理要删除节点的内存
				current->next = next;//把要删除节点的前驱节点的后继节点指向，删除结点的后继节点
			}
		}
	}
}
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value)const {
	int index = hash(key);//利用哈希函数计算键的索引
	if (table[index]) {//判断索引的链表是否为空
		if (table[index]->key == key) {
			//如果找到了键，则返回true，并将值赋值给value
			value = table[index]->value;
			return true;
		}
		else {
			HashNode<KeyType, ValueType>* current = table[index];
			while (current->next && current->next->key != key) {
				//遍历到current的后继节点为空或者current的后继节点的键和查找的键匹配，则结束循环
				current = current->next;
			}
			if (current->next) {
				//如果后继节点不为空说明找到了键，则返回true，并将值赋值给value
				value=current->next->value;
				return true;
			}
		}
	}
	return false;
}
int main() {
	HashTable<int, char> h(1000);
	h.insert(1, 'a');
	h.insert(1, 'b');
	h.insert(1, 'c');
	h.insert(41012012, 'd');

	char val;
	if (!h.find(43, val)) {
		cout << "43 not found!" << endl;
	}
	if (h.find(41012012, val)) {
		cout << "41012012 found,value is " << val << endl;
	}
}