开散列法实现哈希桶

上节我们介绍了闭散列法实现哈希表的操作，今天我们来看开散列法实现哈希桶的操作。

开散列法（链地址法(开链法)）

开散列法首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点组成一个向量，因此，向量的元素个数与可能的桶数一致。

设元素的关键码为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设备模型（中）之上层容器