C++_哈希-EW帮帮网

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2 N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同

哈希表与红黑树封装出来的容器的区别

1undered_xxx是单向迭代器

2unordered_xxx遍历出来不是有序

在用法上undered_xxx和xxx基本上没什么区别就是底层的实现一个是哈希一个是红黑树

哈希：存储的值跟存储的位置建立出一个对应的关系

2. 底层结构

2.1哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O($log_2 N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

这种函数就是哈希函数，用来求一个哈希值

2.2哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

2.3哈希函数

引起哈希冲突的一个原因就是哈希函数设计的不够合理。

常见哈希函数

1 直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2 除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p将关键码转换成哈希地址

3. 平方取中法--(了解)

4. 折叠法--(了解)

5. 随机数法--(了解)

6. 数学分析法--(了解)

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4哈希冲突解决

1 闭散列-开放定址法

1.线性探测

线性探测当遇到挨着的一系列值的时候，会发生拥堵

缺点就是你的位置被占用的时候最好不要取占用别人的位置

当删除的时候，不能随便删除已有元素，而是用标记法来伪删除一个元素

那么哈希表什么情况下发生扩容讷？如何扩容

线性探测的实现：
bool Insert(const pair<K, V>& kv)
{
	//通过载荷因子来判断是否需要扩容
	if ((double)_n / (double)_table.size() >= 0.7)
	{
		//这时候扩容，新创建一个表， 然后将旧表的数据插入到新的表里面
		//最后交换新旧表的_table
		HashTable<K, V, HashiFunc> newTB;
		size_t newsize = _table.size() * 2;
		newTB._table.resize(newsize);
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]._state == EXIST)
			{
				newTB.Insert(_table[i]._kv);
			}
		}
		_table.swap(newTB._table);
	}

	//线性探索
	HashiFunc hfunc;
	size_t Hashi = hfunc(kv.first) % _table.size();
	while (_table[Hashi]._state != EMPTY)
	{
		Hashi++;
		Hashi %= _table.size();
	}

	_table[Hashi]._kv = kv;
	_table[Hashi]._state = EXIST;
	_n++;
	return true;
}
2.二次探测

其实就是找空位置的方法是通过另外一种算hashi值的方法去找空位

2 开散列-链地址法

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

字符串哈希值的特殊算法：

template<class T>  
size_t BKDRHash(const T *str)  
{  
    register size_t hash = 0;  
    while (size_t ch = (size_t)*str++)  
    {         
        hash = hash * 131 + ch;         
    }  
    return hash;  
}

2.5开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a ，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

3. 模拟实现

模拟实现需要按照步骤完成

1、哈希表

注意这里传的是T,T可以位K,也可以为pair<K,V>，封装的时候再去处理

template <class T>
struct HashiNode
{
	T _Data;
	HashiNode<T>* next;
	
	HashiNode(const T& Data)
		:_Data(Data)
		,next(nullptr)
	{

	}

};

迭代器的实现

//前置声明，因为这个迭代器里面用到了
template <class K, class T, class KeyOfT, class HashiFunc>
class HashBucket;

template <class K, class T,class Ptr,class Ref, class KeyOfT, class HashiFunc>
struct HTIterator
{
	typedef HashiNode<T> Node;
	typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashiFunc> Self;
	typedef HTIterator<K, T, T*, T&, KeyOfT, HashiFunc> Iterator;

	Node* _node;
	const HashBucket<K, T, KeyOfT, HashiFunc>* _pht;//因为这里要传一个表，在const_iterator
	//里面end()返回的是带const修饰的

	HTIterator(Node* node,const HashBucket<K, T, KeyOfT, HashiFunc>* pht)
		:_node(node)
		,_pht(pht)
	{

	}

	HTIterator(const Iterator& it)
		:_node(it._node)
		, _pht(it._pht)
	{
	}

	Self& operator++()
	{
		//一个桶找完了之后要找到下一个桶
		if (_node->next)
		{
			_node = _node->next;
		}
		else
		{
			KeyOfT kot;
			HashiFunc hf;
			size_t Hashi = hf(kot(_node->_Data))%_pht->_hashtable.size();
			++Hashi;
			//查找下一个不为空的桶
			while (Hashi < _pht->_hashtable.size())
			{
				if (_pht->_hashtable[Hashi])
				{
					_node = _pht->_hashtable[Hashi];
					return *this;
				}
				else
				{
					Hashi++;
				}
			}
			_node =  nullptr;
		}
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	Ref operator*()
	{
		return _node->_Data;
	}
	Ptr operator->()
	{
		return &_node->_Data;
	}

};

哈希表的实现（底层用桶）

template <class K,class T, class KeyOfT,class HashiFunc>
class HashBucket
{
	typedef HashiNode<T> Node;
	

	template <class K, class T,class Ptr,class Ref, class KeyOfT, class HashiFunc>
	friend struct HTIterator;
public:
	typedef HTIterator<K, T,T*,T&, KeyOfT, HashiFunc> iterator;
	typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashiFunc> const_iterator;

	iterator begin()
	{
		//找到第一个桶
		for (size_t i = 0; i < _hashtable.size(); i++)
		{
			if (_hashtable[i])
			{
				return iterator(_hashtable[i], this);
			}
		}
		return iterator(nullptr, this);
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	const_iterator begin()const
	{
		//找到第一个桶
		for (size_t i = 0; i < _hashtable.size(); i++)
		{
			if (_hashtable[i])
			{
				return const_iterator(_hashtable[i], this);
			}
		}
		return const_iterator(nullptr, this);
	}

	const_iterator end()const
	{
		return const_iterator(nullptr, this);
	}

	HashBucket()
	{
		_hashtable.resize(10,nullptr);
	}
	
	~HashBucket()
	{
		for (size_t i = 0; i < _hashtable.size(); i++)
		{
			Node* cur = _hashtable[i];
			Node* next = nullptr;
			while (cur)
			{
				next = cur->next;
				delete cur;
				cur = next;
			}
			_hashtable[i] = nullptr;
		}
	}

	pair<iterator,bool> Insert(const T& Data)
	{
		KeyOfT kot;
		iterator it = Find(kot(Data));
		if (it!=end())
		{
			return make_pair(it,false);
		}
		if (_n == _hashtable.size())
		{
			size_t newsize = _hashtable.size() * 2;
			vector<Node*> Newhb ;
			Newhb.resize(newsize, nullptr);
			//将原来表里面的数据插入到新的表里面
			for (size_t i = 0; i < _hashtable.size(); i++)
			{
				Node* cur = _hashtable[i];
				while (cur)
				{
					Node* next = cur->next;
					//头插到新的表里面
					HashiFunc hf;
					size_t Hashi = hf(kot(cur->_Data)) % Newhb.size();
					cur->next = Newhb[Hashi];
					Newhb[Hashi] = cur;
					cur = next;

				}
				_hashtable[i] = nullptr;
			}
			_hashtable.swap(Newhb);
		}
		HashiFunc hf;
		size_t Hashi = hf(kot(Data)) % _hashtable.size();
		Node* newnode = new Node(Data);
		newnode->next = _hashtable[Hashi];
		_hashtable[Hashi] = newnode;
		_n++;
		return make_pair(iterator(newnode,this),true);
	}

	void Print()
	{
		for (size_t i = 0; i < _hashtable.size(); i++)
		{
			Node* cur = _hashtable[i];
			printf("[%d]:", i);
			while (cur)
			{
				//cout << cur->_Data << "->";
				cur = cur->next;
			}
			cout << "NULL";
			cout << endl;
		}
	}

	iterator Find(const K& key)
	{
		HashiFunc hf;
		KeyOfT kot;
		size_t Hashi = hf(key) % _hashtable.size();
		Node* cur = _hashtable[Hashi];
		while (cur)
		{
			if (kot(cur->_Data) == key)
			{
				return iterator(cur, this);
			}
			cur = cur->next;
		}
		return end();
	}

	bool Earse(const K& key)
	{
		HashiFunc hf;
		KeyOfT kot;
		size_t Hashi = hf(key) % _hashtable.size();
		Node* prev = nullptr;
		Node* cur = _hashtable[Hashi];
		if (kot(cur->_Data) == key)
		{
			_hashtable[Hashi] = cur->next;
			delete cur;
			return true;
		}
		while (cur)
		{
			if (kot(cur->_Data) == key)
			{
				prev->next = cur->next;
				_n--;
				delete cur;
				return true;
			}
			prev = cur;
			cur = cur->next;
		}
		return false;

	}
private:
	vector<Node*> _hashtable;
	size_t _n = 0;
};

2、封装map和set

set:

template<class K, class HashiFunc = DefHashiFunc<K>>
class unordered_set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	typedef typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::const_iterator iterator;
	typedef typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::const_iterator const_iterator;

public:
	pair<iterator, bool> insert(const K& key)
	{
		//return _ht.Insert(key);
		pair<typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::iterator, bool> ret = _ht.Insert(key);
		return pair<const_iterator, bool>(ret.first, ret.second);
	}
	iterator begin()const
	{
		return _ht.begin();
	}
	iterator end()const
	{
		return _ht.end();
	}
	

private:
	Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc> _ht;
};

map:

template<class K,class V, class HashiFunc = DefHashiFunc<K>>
class unordered_map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename Hash_Bucket::HashBucket<K, pair<K, V>, MapKeyOfT, HashiFunc>::iterator iterator;
	typedef typename Hash_Bucket::HashBucket<K, pair<const K, V>, MapKeyOfT, HashiFunc>::const_iterator const_iterator;

public:
	pair<iterator,bool> insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}
	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
		return ret.first->second;
	}
private:
	Hash_Bucket::HashBucket<K, pair<K, V>, MapKeyOfT, HashiFunc> _ht;

};

3、普通迭代器

4、const迭代器

5、insert返回值 operator[]

6、key不能修改的问题

4.哈希的应用

4.1 位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的实现：

template<size_t N>
class bitset
{
public:
	bitset()
	{
		_a.resize(N / 32 + 1);
	}
	void set(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_a[i] |= (1 << j);
	}
	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_a[i] &= (~(1 << j));
	}
	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _a[i] & (1 << j);
	}
private:
	vector<int> _a;
};

位图的应用

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

C++_哈希

1. unordered系列关联式容器

2. 底层结构

3. 模拟实现

4.哈希的应用

4.1 位图

//位图就比较与我专业有点偏

网站公告

今日签到

热门文章

最新发布