實現哈希桶（空間利用率較高的哈希表）

  前面幾篇博客已經寫過了哈希表的閉散列法，也寫過哈希表的應用，在這里就不贅述。今天我們要實現的是一個哈希桶。什么哈希桶呢？

• 哈希桶：哈希桶就是盛放不同key鏈表的容器（即是哈希表），在這里我們可以把每個key的位置看作是一個孔，孔里放了一個鏈表

• 相信大家可以看出來，使用一個數組來存放記錄方法的哈希沖突太多，基于載荷因子的束縛，空間利用率不高，在需要節省空間的情況下，我們可以用哈希桶來處理哈希沖突。

• 哈希桶是使用一個順序表來存放具有相同哈希值的key的鏈表的頭節點，利用這個頭節點可以找到其它的key。

• 

• #pragma once
  #include<iostream>
  #include<string>
  #include<vector>
  
  using namespace std;
  
  template<class T>
  struct DefaultFunc
  {
  	size_t operator()(const T& data)
  	{
  		return (size_t)data;
  	}
  };
  
  struct StringFunc
  {
  	size_t operator()(const string& str)
  	{
  		size_t sum = 0;
  		for (size_t i = 0; i < str.size(); ++i)
  		{
  			sum += str[i];
  		}
  		return sum;
  	}
  };
  
  template<class K, class V>
  struct HashBucketNode
  {
  	K _key;
  	V _value;
  	HashBucketNode<K, V>* _next;
  	HashBucketNode(const K& key, const V& value)
  		:_key(key)
  		, _value(value)
  		, _next(NULL)
  	{}
  };
  
  template<class K, class V, class FuncModle = DefaultFunc<K>>
  class HashBucket
  {
  	typedef HashBucketNode<K, V> Node;
  public:
  	HashBucket();
  	//~HashBucket();
  	HashBucket(const HashBucket<K, V, FuncModle>& h);
  	HashBucket<K, V, FuncModle>& operator=(HashBucket<K, V, FuncModle> h);
  	bool Insert(const K& key, const V& value);
  	Node* Find(const K& key);
  	bool Remove(const K& key);
  	//bool Alter(const K& key);//用Find實現
  	void Print();
  protected:
  	void _CheckExpand();//檢查是否需要擴容
  	size_t _GetNextPrime(size_t size);//從素數表中得到比當前素數大的素數
  	size_t _HashFunc(const K& key,size_t mod);//哈希函數
  protected:
  	vector<Node*> _table;
  	size_t _size;//記錄的個數
  };

得到哈希桶的結構以后，我們來實現幾個比較重要的函數：

（一）bool Insert(const K& key, const V& value)

  插入函數是最難實現的，它涉及到是否需要擴容。為插入函數我們寫了兩個內部函數void _CheckExpand(); 和 size_t _GetNextPrime(size_t size);

template<class K, class V, class FuncModle>
bool HashBucket<K, V, FuncModle>::Insert(const K& key, const V& value)
{
	_CheckExpand();
	//使用頭插法插入
	size_t index = _HashFunc(key,_table.size());
	Node* tmp=new Node(key, value);//一定要用new出結點
	if (_table[index] == NULL)
	{
		_table[index] = tmp;
	}
	else
	{
		//不為NULL則使用頭插法插入新結點
		tmp->_next = _table[index];
		_table[index] = tmp;
	}
	_size++;
	return true;
}
template<class K, class V, class FuncModle>
size_t  HashBucket<K, V, FuncModle>::_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 (int i = 0; i < _PrimeSize; ++i)
	{
		if (_PrimeList[i] > size)
			return _PrimeList[i];
	}
	assert(false);
	return 4294967291ul;
}
template<class K, class V, class FuncModle>
void HashBucket<K, V, FuncModle>::_CheckExpand()
{
	if (_size == _table.size())
	{
		size_t newsize = _GetNextPrime(_size);//從素數表中取出下一個素數
		if (newsize == _size)
			return;
		vector<Node*> newtable;
		newtable.resize(newsize);
		for (size_t i = 0; i < _size; ++i)
		{
			size_t index = _HashFunc(_table[i]->_key,newsize);
			if (_table[i])
			{
				Node* head = _table[i];//保存頭節點
				newtable[index] = head;//摘下vector的第一個指針為新表的頭節點
				_table[i] = _table[i]->_next;
				while (_table[i])//依次摘結點
				{
					Node* tmp = _table[i];
					_table[i] = _table[i]->_next;
					head->_next = tmp;
					head = head->_next;
				}
			}
			else
				newtable[index] = NULL;
			_table[i] = NULL;
		}
		swap(_table, newtable);
	}
}

  在擴容的函數中我們使用了素數表，有大師證明Mod素數表中的素數可以減少哈希沖突，其實我也感覺很奇妙。

  在調用哈希函數HashFunc的時候一定要注意，我們用key取模一定模的是vector當前的容量。

  在插入的時候使用頭插法是很高效的！！！

（二）Node* Find(const K& key);

  查找函數返回一個結點的指針方便我們在外部更改數據。

emplate<class K, class V, class FuncModle>
HashBucketNode<K,V>* HashBucket<K, V, FuncModle>::Find(const K& key)
{
	size_t index = _HashFunc(key, _table.size());
	while (_table[index])
	{
		if (_table[index]->_key == key)
		{
			return _table[index];
		}
		_table[index] = _table[index]->_next;
	}
	return NULL;
}

（三）bool Remove(const K& key);

   我們在寫刪除節點函數時最好別調用Find函數去查找要刪除的結點，如果要刪除的結點是頭節點或者尾節點的話就無法修改要刪除指針的前一個指針的_next域；

template<class K, class V, class FuncModle>
bool HashBucket<K, V, FuncModle>::Remove(const K& key)
{
	//不能用find找到，然后刪。
	size_t index = _HashFunc(key,_table.size());
	if (_table[index] == NULL)
		return false;
	Node* cur = _table[index];
	if (cur->_key==key)
	{
		Node* del = cur;
		_table[index] = cur->_next;
		delete del;
		_size--;
		return true;
	}
	else
	{
		Node* prev = NULL;
		while (cur)
		{
			if (cur->_key == key)
			{
				prev->_next = cur->_next;
				delete cur;
				_size--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
}

  其他的函數比較的簡單，在這里我就不寫出來了；