【C++篇】哈希表

//当前位置的状态
//存在  空  已删除
enum State
{
	EXIT,
	EMPTY,
	DELETE
};

template <class k,class v>
struct HashData
{
	pair<k, v> _kv;
	State _state = EMPTY;
};

template <class k,class v>
class HashTable
{
private:
	vector<Hashdata<k, v>> _tables; //哈希表
	size_t n = 0;                   //表中存储数据的个数
};

//当前位置的状态
//存在  空  已删除
enum State
{
	EXIT,
	EMPTY,
	DELETE
};

template <class k,class v>
struct HashData
{
	pair<k, v> _kv;
	State _state = EMPTY;
};

template <class k>
class HashFunc
{
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	// 字符串转换成整形，可以把字符ascii码相加即可
	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
	// 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131等效果会比较好
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};

template<class k, class v, class Hash = HashFunc<k>>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}


	bool insert(const pair<k, v>& kv)
	{
		Hash hash;
		//负载因子>=0.7  扩容
		if (_n * 10 / _tables.size() >= 7)
		{
			//创建一个新表
			HashTable<k, v, Hash> newht;
			//扩容
			newht._tables.resize(__stl_next_prime(_tables.size() + 1));
			//旧表数据映射到新表
			for (auto& data : _tables)
			{
				if (data._state == EXIST)
					newht.insert(data._kv);
			}
			//_tables=newht._tables;
			_tables.swap(newht._tables);
		}

		size_t hash0 = hash(kv.first) % _tables.size();
		size_t hashi = hash0;
		int i = 1;
		while (_tables[hashi]._state == EXIST)
		{
			//线性探测
			hashi = (hash0 + i) % _tables.size();//防止越界
			i++;
		}

		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		_n++;

		return true;
	}

	HashData<k, v>* find(const k& key)
	{
		Hash hash;
		size_t hash0 = hash(key) % _tables.size();
		size_t hashi = hash0;
		int i = 1;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
			{
				return &_tables[hashi];
			}
			//线性探测
			hashi = (hash0 + i) % _tables.size();//防止越界
			i++;
		}
		return nullptr;
	}

	bool erase(const k& key)
	{
		HashData<k, v>* ret = find(key);
		if (ret)
		{
			ret->_state = DELETE;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	vector<HashData<k, v>> _tables;
	size_t _n;
};

//链地址法
//哈希桶
template<class k, class v>
struct HashNode
{
	pair<k, v> _kv;
	HashNode<k, v>* _next;
	HashNode(const pair<k, v>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};
template<class  k, class v>
class Hash_bucket
{
public:
	typedef HashNode<k, v> Node;
	Hash_bucket()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}
	~Hash_bucket()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;

				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
    
	bool insert(const pair<k, v>& kv)
	{
		//防止键值冗余
		if (find(kv.first))
			return false;

		//负载因子>=1时，扩容
		if (_n / _tables.size() >= 1)
		{
			//创建新表
			vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
                //直接将旧表中的节点插入到新表中 所映射的位置
				while (cur)
				{
					Node* next = cur->_next;
					//直接插入到新表
					size_t hashi = cur->_kv.first % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;

					cur = next;
				}
			}
			_tables.swap(newtables);
		}

		size_t hashi = kv.first % _tables.size();
		Node* newnode = new Node(kv);
		//头插到新表
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;

		return true;
	}
	Node* find(const k& key)
	{
		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
				return cur;
			cur = cur->_next;
		}
		return nullptr;
	}
	bool erase(const k& key)
	{
		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				--_n;

				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return false;
	}

private:
	vector<Node*> _tables;
	size_t _n;
};