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

enum Stat
{
	EMPTY,
	EXIST,
	DELETE
};

template<class T>
struct HashNode
{
	T _val;
	Stat _st = EMPTY;//该位置的状态，默认为空
};


static size_t GetNextPrime(size_t prime)
{
	static const int PRIMECOUNT = 28;
	static const size_t primeList[PRIMECOUNT] =
	{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};

	size_t i = 0;
	for (; i < PRIMECOUNT; ++i)
	{
		if (primeList[i] > prime)
			return primeList[i];
	}

	return primeList[i];
}

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct Hash < string >//模板特化
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			//hash += ch;
			hash = hash * 131 + ch;
		}

		return hash;
	}
};

template<class T,class HashFunc = Hash<T>>
class HashTable
{
public:
	bool insert(const T& key)
	{
		/*1、判断是否需要扩容：
		 *   ·哈希表为空时需要扩容
		 *   ·哈希表为满时需要扩容
		 *   ·扩容时需要注意的是：如果哈希表为空，该扩容为多少呢？
		 *   ·本质上说，这个值由我们自己定，但是研究表明当哈希函数的模数为质数时，效率较高
		 *   ·因此，这里扩容我们使用STL库中的扩容方法：调用GetNextPrime按照模数为质数的情况进行扩容
		 *   ·还有一个问题：如果哈希表满了，如何扩容？
		 *   ·如果直接扩容，不对之前插入的数据处理，会导致之前的数据的查找效率会变得非常的低
		 *   ·因此，在扩容时还需要将之前插入的数据在新的哈希表中进行重新插入。
		*/
		if (_htb.size() == 0 || _size*10 /_htb.size() >= 7)
		{
			size_t newSize = GetNextPrime(_htb.size());
			//将旧的哈希表插入到新的哈希表中---构造一个哈希对象，调用该对象的额insert方法
			HashTable<T, HashFunc> ht;
			ht._htb.resize(newSize);//对象中的哈希表的大小为newsize
			for (auto& e : _htb)
			{
				//将旧哈希表中的数据插入到对象中的新的大小为newsize的哈希表中
				ht.insert(e._val);
			}
			//交换两个哈希表，出了作用域对象会自动调用析构函数释放原来的空间
			_htb.swap(ht._htb);
		}

		/*需要注意的是，如果该值已经存在则不需要再进行插入*/
		if (find(key) != nullptr)
			return false;

		/*2、使用hash函数计算出插入位置
		 *	·这里的哈希函数使用除留余数法
		 *  ·需要注意的是，使用除留余数法对于int类型来说可以直接取模
		 *  ·对于string等其他类型不能直接取模，因此需要自定义取模方法
		 *  ·这里，我们对string的处理方式为：所有字符的ASCII求和在取模
		 *  ·因此，类模板参数中应该还有一个用来控制取模方法的仿函数
		*/
		HashFunc hf;
		int index = hf(key) % _htb.size();

		/*3、解决哈希冲突
		 *  ·线性探测：查找空位置
		 *	·这里需要注意的是，如果我们直接在哈希表中存储T类型的关键码
		 *  ·当一个元素从哈希表中删除后，它的位置实际上会变成随机值
		 *  ·那么在插入时，我们不知道这个位置是删除后的随机值还是没有插入的空值
		 *  ·或者说，这个位置就是我们存储的关键码。
		 *  ·因此，我们需要标记每一个位置，到底是empty还是delete或者是exist
		 *  ·因此，我们在哈希表中存储的是一个节点，这个节点中一个是值一个是状态，状态使用了一个枚举类型来表示
		 */
		if (_htb[index]._st == EXIST)
		{
			//存在哈希冲突，解决哈希冲突
			while (_htb[index]._st == EXIST)
			{
				index++;
				//为了防止数组越界，需要取模
				index %= _htb.size();
			}
		}
		/*4、插入元素*/
		_htb[index]._val = key;
		_htb[index]._st = EXIST;

		return true;
	}
	//查找
	HashNode<T>* find(const T& key)
	{
		//取模找到位置
		HashFunc hf;
		int index = hf(key) % _htb.size();
		//位置冲突，线性查找，找到第一个空位置停止查找
		if (_htb[index]._val != key)
		{
			while (_htb[index]._st != EMPTY && _htb[index]._val != key)
			{
				++index;
				index %= _htb.size();
			}

		}
		if (_htb[index]._st == EMPTY)
			return nullptr;
		return &_htb[index];
	}
	bool erase(const T& key)
	{
		HashNode<T>* ret = find(key);
		if (ret == false)
		{
			return false;
		}
		else
		{
			ret->_state = DELETE;
			return true;
		}
	}
private:
	vector<HashNode<T>> _htb;//哈希表
	size_t _size;//实际存储元素的个数
};

void TestHashTable()
{
	HashTable<int> ht;
	ht.insert(5);
	ht.insert(15);
	ht.insert(16);
	ht.insert(17);
	ht.insert(25);
	ht.insert(35);
	ht.insert(45);
	ht.insert(55);

	struct StrHash
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
			}

			return hash;
		}
	};

	//HashTable<string, string, StrHash> strht;
	HashTable<string> strht;
	strht.insert("sort");
	strht.insert("insert");

}