開散列法實作哈希桶

上節我們介紹了閉散列法實作哈希表的操作，今天我們來看開散列法實作哈希桶的操作。

開散列法（鍊位址法(開鍊法)）

開散列法首先對關鍵碼集合用散列函數計算散列位址，具有相同位址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單連結清單連結起來，各連結清單的頭結點組成一個向量，是以，向量的元素個數與可能的桶數一緻。

設元素的關鍵碼為37,25,14,36,49,68,57,11,散清單為HT[12]，表的大小為12，散列函數為Hash(x) = x % 11 Hash(37)=4 Hash(25)=3 Hash(14)=3 Hash(36)=3

Hash(49)=5 Hash(68)=2 Hash(57)=2 Hash(11)=0

開散列法實作哈希桶

通常，每個桶中的同義詞子表都很短，設有n個關鍵碼通過某一個散列函數，存放到散清單中的m個桶中，那麼每一個桶中的同義詞子表的平均長度為n/m。這樣以搜尋平均長度為n/m的同義詞子表代替了搜尋長度為n的順序表，搜尋效率快的多。

應用鍊位址法處理溢出，需要增設連結指針，似乎增加了存儲開銷。事實上，由于開位址法必須保持大量的空閑空間以確定搜尋效率，如二次探查法要求裝載因子a <= 0.7 而表項所占空間又比指針大的多，是以使用鍊位址法反而比開位址法節省存儲空間。

在此次操作中，我們對關鍵元素key 和下标value 值用鍵值對（pair<K,V>）進行封裝，并對程式加入了疊代器，增加了難度。

但是原理不變。

（1）仿函數

class KeyToIntDef
{
public:
	size_t operator()(const size_t& key)
	{
		return key;
	}
};
class stringToInt
{
public:
	size_t operator()(const string& key)
	{
		return BKDRHash(key.c_str());
	}
private:
	static size_t BKDRHash(const char* str)
	{
		unsigned int seed = 131;
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash*seed + (*str++);

		}
		return (hash & 0x7FFFFFFF);
	}
};

（2）素數表增容

const int _PriSize = 28;
static size_t GetNextPrime(const size_t& value)
{
	
		static const unsigned long _PrimeList[_PriSize] =
		{

			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 < _PriSize; i++)
		{
			if (_PrimeList[i]>value)
				return _PrimeList[i];
		}
		return _PrimeList[_PriSize - 1];
}

（3）哈希桶的結點元素

template<class K, class V>
struct HashBucketNode
{
	HashBucketNode(const pair<K, V>& key)
	:_key(key)
	, _PNext(NULL)
	{}

	pair<K, V> _key;
	HashBucketNode<K, V>* _PNext;
};

（4）疊代器對指針的封裝

包括構造函數，拷貝構造函數，前置++，後置++，->的重載，*的重載，判斷是否相等或不相等等操作；

//疊代器
template<class K,class V,class KToInt>
class HashBucketIterator
{
	typedef HashBucketNode<K, V> Node;
	typedef Node* PNode;
	typedef HashBucketIterator<K, V, KToInt> IteratorSelf;
public:
	PNode _Pcur; //疊代器成員變量
	HashBucket<K, V, KToInt>* _hb; //指向哈希表的指針
public: 

	HashBucketIterator()
		:_Pcur(NULL)
		,_hb(NULL)
	{}
	HashBucketIterator(const PNode pcur, HashBucket<K, V, KToInt>*hb)
		:_Pcur(pcur)
		, _hb(hb)
	{}
	HashBucketIterator(const IteratorSelf& s)
		:_Pcur(s._Pcur)
		, _hb(s._hb)
	{}

	IteratorSelf& operator++()
	{
		Next();
		return *this;
	}
	IteratorSelf operator++(int)
	{
		IteratorSelf temp(*this);
		Next();
		return temp;
	}
	pair<K, V>& operator*()
	{
		return _Pcur->_key;
	}
	pair<K, V>* operator->()
	{
		return &(operator*());
	}
	bool operator==(const IteratorSelf& s)
	{
		return _Pcur == s._Pcur;
	}
	bool operator != (const IteratorSelf& s)
	{
		return !(operator==(s));
	}

private:
	void Next()
	{
		if (_Pcur->_PNext)
			_Pcur = _Pcur->_PNext;
		else
		{
			//找下一個哈希桶
			size_t bucketNo = _hb->HashFunc(_Pcur->_key.first) + 1;
			for (; bucketNo < _hb->BucketCount(); bucketNo++)
			{
				if (_hb->_table[bucketNo])
				{
					_Pcur = _hb->_table[bucketNo];
					return;
				}
					
            }
			_Pcur = NULL;
		}
		return;
	}


};

（5）哈希桶的實作

template<class K,class V,class KToInt>
class HashBucket
{
	typedef HashBucketNode<K, V> Node;
	typedef Node* PNode;
	friend HashBucketIterator<K, V, KToInt>;
public:
 typedef HashBucketIterator<K, V, KToInt> Iterator;
public:
	HashBucket( size_t capacity=10)
		:_size(0)
	{
     	capacity = GetNextPrime(capacity);
		_table.resize(capacity);
	}
	Iterator Begin()
	{
		for (size_t bucketNo = 0; bucketNo < _table.capacity(); ++bucketNo)
		{
			if (_table[bucketNo])
				return Iterator(_table[bucketNo], this);
		}
		return Iterator(NULL, this);
	}
	Iterator End()
	{
		return Iterator(NULL, this);
	}
	//插入重複元素
	pair<Iterator, bool> InsertEqual(const pair<K, V>& key)
	{
		CheckCapacity();
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		PNode newNode = new Node(key);
		//頭插
		newNode->_PNext = pcur;
		_table[addre] = newNode;

		_size++;
		return make_pair(Iterator(newNode, this), true);

	}
	//插入唯一進制素
	pair<Iterator, bool> InsertUnique(const pair<K, V>& key)
	{
		CheckCapacity();
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		//查找是否有相同元素
		while (pcur)
		{
			if (pcur->_key.first == key.first)
				return make_pair(Iterator(NULL,this), false);
			pcur = pcur->_PNext;
		}

		//插入結點
		PNode newNode = new Node(key);
		newNode->_PNext = _table[addre];
		_table[addre] = newNode;
		_size++;
		return make_pair(Iterator(newNode, this), true);
	}

	//查找元素
	Iterator Find(const pair<K,V>& key)
	{
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		while (pcur)
		{
			if (pcur->_key.first == key.first)
				return Iterator(pcur, this);
			pcur = pcur->_PNext;
		}
		return Iterator(NULL, this);
	}

	//删除唯一進制素
	pair<Iterator, bool> EraseUnique(const pair<K, V>& key)
	{
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		PNode pre = NULL;
		if (_table[addre] == NULL)
			return make_pair(Iterator(NULL, this), false);
		while (pcur)
		{
			if (pcur->_PNext->_key.first == key.first)
			{
				if (pcur == _table[addre])
				{
					_table[addre] = NULL;
				}
				else
				{
					pre->_PNext = pcur->_PNext;
				}
				delete pcur;
				pcur = NULL;
				--size;
				return make_pair(Iterator(pre, this), true);
			}
			pre = pcur;
			pcur = pcur->_PNext;
		}
		return make_pair(Iterator(NULL, this), false);
	}

	//删除值不唯一
	pair<Iterator, bool> EraseEqual(const pair<K, V>& key)
	{
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		PNode pre = NULL;
		if (_table[addre] == NULL)
			return make_pair(Iterator(NULL, this), false);
		while (pcur)
		{
			if (pcur->_key.first == key.first)
			{
				 if (pcur == _table[addre])
				{
					 _table[addre] = pcur->_PNext;
					 delete pcur;
					 pcur = NULL;
				}
				 else
				 {
					 pre->_PNext = pcur->_PNext;
					 delete pcur;
					 pcur = pcur->_PNext;
				 }
				 _size--;
				
			}
			else
			{
				pre = pcur;
				pcur = pre->_PNext;
			}
		}
		return make_pair(Iterator(NULL, this), false);

	}
	//值為key 的元素個數
	size_t Count(const pair<K, V>& key)
	{
		size_t addre = HashFunc(key.first);
		size_t count = 0;
		PNode pcur = _table[addre];
		while (pcur)
		{
			if (pcur->_key.first == key.first)
				count++;
			pcur = pcur->_PNext;
		}
		return count;
	}
	//桶的個數
	size_t BucketCount()const 
	{
		return _table.capacity();
	}
	//桶内元素的個數
	size_t BucketElemSize(size_t bucketNo)const
	{
		size_t count = 0;
		PNode pcur = _table[bucketNo];
		while (pcur)
		{
			count++;
			pcur = pcur->_PNext;
		}
		return count;

	}
	//查找值為key,如果找到了，傳回對應的value；如果沒有找到，則插入該節點，傳回預設的value。
	V& FindOrInsert(const pair<K,V>& key)
	{
		size_t addre = HashFunc(key.first);
		PNode pcur = _table[addre];
		while (pcur)
		{
			if (pcur->_key.first == key.first)
				return pcur->_key.second;
			pcur = pcur->_PNext;
		}
		pair<Iterator, bool> ret = InsertUnique(make_pair(key.first, V()));
		return (*(ret.first)).second;
			
	}
	//判斷是否為空
	bool Empty()const 
	{
		return _size == 0;
	}
	//插入的總數
	size_t numsize()const
	{
		return _size;
	}
	//清空
	void clear()
	{
		for (size_t bucketNo = 0; bucketNo < _table.capacity(); ++bucketNo)
		{
			PNode pcur = _table[bucketNo];
			while (pcur)
			{
				PNode pDel = pcur->_PNext;
				delete pcur;
				pcur = pDel;
				_size--;
			}
		}
	}
	~HashBucket()
	{
		clear();
	}
private:
	void CheckCapacity()
	{
		size_t capacity = _table.capacity();
		if (_size==capacity)
		{
			size_t newcapacity = GetNextPrime(capacity);
			HashBucket<K, V, KToInt> hb(newcapacity);
			for (size_t bucketNo = 0; bucketNo < capacity; bucketNo++)
			{
				PNode pcur = _table[bucketNo];
				while (pcur)
				{
					hb.InsertEqual(pcur->_key);
					pcur = pcur->_PNext;
				}
			}
			swap(hb._table, _table);
			_size = hb._size;
		}

	}
	size_t HashFunc(const K& key)
	{
		return KToInt()(key) % _table.capacity();
	}
private:
	vector<PNode> _table;
	size_t _size;
};

（6）測試函數

void test()
{
	HashBucket<int, int, KeyToIntDef> hb(20);
	hb.InsertUnique(make_pair(2,2));
	hb.InsertUnique(make_pair(3, 3));
	hb.InsertUnique(make_pair(4, 4));
	hb.InsertUnique(make_pair(2, 5));

	/*hb.InsertEqual(make_pair(3, 3));
	hb.InsertEqual(make_pair(3, 4));

	hb.EraseEqual(make_pair(3, 3));*/
	
	/*cout<<hb.FindOrInsert(make_pair(2, 2));
	cout << hb.FindOrInsert(make_pair(9, 2));*/
	HashBucket<int, int, KeyToIntDef>::Iterator it = hb.Begin();
	if (!hb.Empty())
	{
		while (it != hb.End())
		{
			cout << it->first << " ";
			cout << (*it).second << endl;
			it++;
		}
		cout << hb.BucketCount();
		cout << hb.numsize();
	}

	//HashBucket<string, string, stringToInt>hb2(20);
	//hb2.InsertUnique(make_pair("1111", "1111"));
	//hb2.InsertUnique(make_pair("2222", "2222"));
	//hb2.InsertUnique(make_pair("3333", "3333"));
	//hb2.InsertUnique(make_pair("2222", "1111"));

	//cout << hb2.BucketCount();
	//cout << hb2.numsize();

	cout << hb2.FindOrInsert(make_pair("2222", "2222"));
	cout << hb2.FindOrInsert(make_pair("4444", "4444"));
}

大家可以自己利用哈希桶封裝unordered_map啊！

開散列法實作哈希桶

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器