#pragma once

#include 
#include 

template
struct HashTableNode
{
	K _key;
	V _value;
	HashTableNode* _next;

	HashTableNode(const K& key, const V& value)
		:_key(key)
		,_value(value)
		,_next(NULL)
	{}
};

template
struct __HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct __HashFunc
{
	static size_t BKDRHash(const char * str)
	{
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
		return (hash & 0x7FFFFFFF);
	}

	size_t operator() (const string& key)
	{
		return BKDRHash(key.c_str());
	}
};

template>
class HashTable
{
	typedef HashTableNode Node;
public:
	HashTable(size_t capacity)
		:_size(0)
	{
		_tables.resize(_GetNextPrime(capacity));
	}

	HashTable(const HashTable& ht);
	HashTable& operator=(const HashTable& ht);

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];

			while (cur)
			{
				Node* del = cur;
				cur = cur->_next;
				delete del;
			}
		}
	}

	bool Insert(const K& key, const V& value)
	{
		_CheckCapacity();

		size_t index = _HashFunc(key, _tables.size());

		Node* cur = _tables[index];

		while (cur)
		{
			if (cur->_key == key)
				return false;

			cur = cur->_next;
		}

		Node* tmp = new Node(key, value);
		tmp->_next = _tables[index];
		_tables[index] = tmp;

		++_size;

		return true;
	}

	Node* Find(const K& key)
	{
		size_t index = _HashFunc(key, _tables.size());
		Node* cur = _tables[index];
		while (cur)
		{
			if (cur->_key == key)
				return cur;

			cur = cur->_next;
		}

		return NULL;
	}

	bool Remove(const K& key)
	{
		size_t index = _HashFunc(key, _tables.size());

		if (_tables[index] == NULL)
			return false;

		if (_tables[index]->_key == key)
		{
			Node* del = _tables[index];
			_tables[index] = _tables[index]->_next;
			delete del;

			return true;
		}

		Node* prev = _tables[index];
		Node* cur = prev->_next;
		while (cur)
		{
			if (cur->_key == key)
			{
				prev->_next = cur->_next;
				delete cur;

				return true;
			}

			prev = cur;
			cur = cur->_next;
		}

		return false;
	}

	void Print()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			printf("[%d]->", i);
			Node* cur = _tables[i];
			while (cur)
			{
				cout<_key<<":"<_value<<"->";

				cur = cur->_next;
			}

			cout<<"NULL"<& ht)
	{
		swap(_tables, ht._tables);
		swap(_size, ht._size);
	}

protected:
	void _CheckCapacity()
	{
		if (_size == _tables.size())
		{
			size_t newCapacity = _GetNextPrime(_tables.size());

			if (newCapacity == _tables.size())
				return;
/*

			vector newTables;
			newTables.resize(newCapacity);

			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];

				while (cur)
				{
					Node* tmp = cur;
					cur = cur->_next;

					size_t index = _HashFunc(tmp->_key, newCapacity);//???
					tmp->_next = newTables[index];
					newTables[index] = tmp;
				}

				_tables[i] = NULL;
			}

			_tables.swap(newTables);
*/

			HashTable tmp(_tables.size());
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				
				while (cur)
				{
					tmp.Insert(cur->_key, cur->_value);
					cur = cur->_next;
				}
			}

			this->Swap(tmp);
		}
	}

	// 使用素数表对齐做哈希表的容量，降低哈希冲突
	size_t _GetNextPrime(size_t size)
	{
		const int _PrimeSize = 28;
		static const unsigned long _PrimeList [_PrimeSize] =
		{
			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
		};

		for (size_t i = 0; i < _PrimeSize; ++i)
		{
			if (_PrimeList[i] > size)
			{
				return _PrimeList[i];
			}
		}

		return _PrimeList[_PrimeSize-1];
	}

	size_t _HashFunc(const K& key, const size_t capacity)
	{
		return HashFunc()(key) % capacity;
	}
protected:
	vector _tables;
	size_t _size;
};

void TestDic()
{
	HashTable dict(10);

	dict.Insert("he", "他");
	dict.Insert("she", "她");
	dict.Insert("hash", "哈希");
	dict.Insert("hello", "你好");
	dict.Print();

	HashTableNode* ret = dict.Find("hash");
	if (ret)
	{
		cout<_value<> ht(10);
	vector vec;

	vec.push_back("男");
	vec.push_back("20");
	vec.push_back("123456");

	ht.Insert("张三", vec);


	HashTableNode>* ret = ht.Find("张三");
	if (ret)
	{
		cout<<"姓名："<_key<_value[0]<_value[1]<_value[2]<
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、虚拟空间、营销软件、网站建设、兴县网站维护、网站推广。
#include 
using namespace std;
#include "HashTablesBucket.h"

int main()
{
	//TestDic();
	Test();

	return 0;
}
TestDic:
Test:
            
            
                            

                网站题目：C++实现哈希桶                

                文章起源：http://scyanting.com/article/jppeis.html