哈希桶處理哈希沖突

    哈希桶：哈希桶就是盛放不同key鏈表的容器（即是哈希表），我們可以把每個key的位置看作是一個指針，該指針?biāo)赶虻奈恢美锓帕艘粋€鏈表，可以認(rèn)為是指針數(shù)組，故該方法也叫開鏈?zhǔn)健?/span>

    相比閉散列，哈希桶提高了空間利用率：在實(shí)現(xiàn)哈希表時(shí)，常見的方法是線性探測、二次探測，這兩個算法的具體實(shí)現(xiàn)可以查看我的博客。但是這兩個算法有一個共同點(diǎn)就是：空間利用率低。為什么這么說呢？線性探測、二次探測的高效性很大程度上要取決于它的載荷因子，載荷因子即：存放關(guān)鍵字個數(shù) / 空間大小。

    通過查閱資料，我發(fā)現(xiàn)，使用素?cái)?shù)做除數(shù)可以減少哈希沖突。見下：

素?cái)?shù)表：使用素?cái)?shù)做除數(shù)可以減少哈希沖突

     // 使用素?cái)?shù)表對齊做哈希表的容量，降低哈希沖突

     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

    };

下圖進(jìn)行哈希桶處理哈希沖突的展示

下面通過庫中的vactor進(jìn)行存放指向鏈表的指針，每個結(jié)點(diǎn)里包含_key,_value和_next。

#pragma
template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
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 + (unsigned int)(*str++);
	}
	return (hash & 0x7FFFFFFF);
}
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		return BKDRHash(str.c_str());
	}
};
template<class K, class V>
struct HashTableNode//結(jié)點(diǎn)
{
	K _key;
	V _value;
	HashTableNode* _next;
	HashTableNode(const K& key, const V& value)
		:_key(key)
		, _value(value)
		, _next(NULL)
	{}
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTableBucket
{
	typedef HashTableNode<K, V> Node;
public:
	HashTableBucket();
	HashTableBucket(const HashTableBucket<K, V, HashFunc>& htb);
	HashTableBucket<K, V, HashFunc>& operator=(HashTableBucket<K, V, HashFunc> htb);
	void PrintTables();
	bool Insert(const K& key,const V& value);//防冗余，在刪除和查找時(shí)只需要key
	Node* Find(const K& key);
	bool Remove(const K& key);
protected:
	size_t _HashFunc(const K& key);
	size_t _GetNextPrime(size_t size);//獲取下一個素?cái)?shù)（利用素?cái)?shù)表，使用素?cái)?shù)做除數(shù)可以減少哈希沖突）
	void _CheckExpand();
private:
	vector<Node*> _tables;//開鏈?zhǔn)綖橹羔様?shù)組，指針指向鏈表
	size_t _size;//有效數(shù)據(jù)數(shù)，vector中的size()為有效空間數(shù)
};

實(shí)現(xiàn)_HashFunc(const K& key)，通過偽函數(shù)來判斷不同類型的key所在鏈表的位置。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
size_t HashTableBucket<K, V, HashFunc>::_HashFunc(const K& key)
{
	HashFunc htb;
	return htb(key) % (_tables.size());//htb(key)偽函數(shù)
}

1. 插入函數(shù)的實(shí)現(xiàn)（Insert）

（1）檢查容量。調(diào)用_CheckExpand()函數(shù)檢查負(fù)載因子a，考慮是否擴(kuò)張，當(dāng)a為1時(shí)進(jìn)行擴(kuò)容。

（2）檢查插入的key是否已經(jīng)存在，不存在返回false，存在進(jìn)行（3）操作。

（3）進(jìn)行頭插。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
bool HashTableBucket<K, V, HashFunc>::Insert(const K& key, const V& value)
{//防冗余，在刪除和查找時(shí)只需要key
	_CheckExpand();//檢查是否擴(kuò)容
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		Node* cur = _tables[i];
		while (cur)
		{//如果插入的元素存在就返回false
			if (cur->_key == key)
			{
				return false;
			}
			cur = cur->_next;
		}
	}	
	//頭插
	size_t index = _HashFunc(key);
	Node* tmp = new Node(key, value);
	tmp->_next = _tables[index];
	_tables[index] = tmp;
	++_size;
	return true;

2. 查找函數(shù)的實(shí)現(xiàn)（Find）

（1）調(diào)用_HashFunc()函數(shù)找到要尋找的Key所在的鏈表位置。

（2）通過遍歷鏈表查找key。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
HashTableNode<K, V>* HashTableBucket<K, V, HashFunc>::Find(const K& key)//查找
{
	size_t index = _HashFunc(key);//鏈表結(jié)點(diǎn)位置
	Node* cur = _tables[index];
	while (cur)
	{
		if (cur->_key == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

3. 刪除函數(shù)的實(shí)現(xiàn)（Remove）

（1）調(diào)用Find（）函數(shù)，判斷需要刪除的key是否存在，不存在就返回false，存在就進(jìn)行（2）操作。

（2）調(diào)用_HashFunc()函數(shù)找到key所在鏈表的位置，先通過遍歷鏈表找到del結(jié)點(diǎn)的上一個結(jié)點(diǎn)prev，然后使prev的下一個結(jié)點(diǎn)指向del的下一個結(jié)點(diǎn)。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
bool HashTableBucket<K, V, HashFunc>::Remove(const K& key)//刪除
{
	if (Find(key) == NULL)
	{
		return false;
	}
	size_t index = _HashFunc(key);
	//需要找到刪除結(jié)點(diǎn)的前后結(jié)點(diǎn)
	Node* del = Find(key);
	Node* next = del->_next;
	Node* prev = _tables[index];
	while (prev)
	{
		if (prev->_next == del)
		{
			break;
		}
		prev = prev->_next;
	}
	if (next)//如果next存在時(shí)，進(jìn)行鏈接
	{
		prev->_next = next;
	}
	del = NULL;
	return true;
}

檢查是否需要擴(kuò)容_CheckExpand()的實(shí)現(xiàn)。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
void HashTableBucket<K, V, HashFunc>::_CheckExpand()//檢查負(fù)載因子，考慮是否擴(kuò)容
{
	if (_size >= _tables.size())//負(fù)載因子達(dá)到了1，進(jìn)行擴(kuò)容
	{
		size_t NewSize = _GetNextPrime(_size);
		//進(jìn)行結(jié)點(diǎn)復(fù)制
		vector<Node*> NewTables;
		NewTables.resize(NewSize);
		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);//重新確定元素在表中位置
				tmp->_next = NewTables[index];
				NewTables[index] = tmp;
			}
		}
		_tables.swap(NewTables);//調(diào)用vector中的swap接口進(jìn)行交換
	}
}
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
size_t HashTableBucket<K, V, HashFunc>::_GetNextPrime(size_t size)
{//獲取下一個素?cái)?shù)（利用素?cái)?shù)表，使用素?cái)?shù)做除數(shù)可以減少哈希沖突）
	//使用素?cái)?shù)表對齊做哈希表的容量，降低哈希沖突
	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[i - 1];
	}
	return _PrimeList[_PrimeSize];//如果size大于或等于素?cái)?shù)表中數(shù)據(jù)，就返回表中最大數(shù)
}

測試用例如下，實(shí)現(xiàn)字典（可以一對多）查詢。

HashTableBucket<string, vector<string>> dict;
	vector<string> v;
	v.push_back("manager");
	dict.Insert("經(jīng)理", v);

	v.clear();
	v.push_back("移動");
	v.push_back("距離");
	dict.Insert("remove",v);
	HashTableNode<string, vector<string>>* ret = dict.Find("remove");
	ret->_value.push_back("搬家");

	vector<string>& words = ret->_value;
	for (size_t i = 0; i < words.size(); ++i)//打印對應(yīng)的多個字符串
	{
		cout << words[i].c_str() << endl;
	}