#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");

}