哈希结构（图文详解）【哈希表，哈希桶，位图，布隆过滤器】

野性酷女 2022-10-16 08:45 261阅读 0赞

# 哈希结构 #

### 哈希概念 ###

常见的K-V结构，实现了元素关键码与元素值的映射关系，但没有实现元素关键值与元素存储位置的映射关系，在遍历过程中，一般的顺序表或搜索二叉树要进行关键值的多次比较，其中顺序表的时间复杂度为O(n),二叉搜索树的时间复杂度O(lgn)

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

### 哈希函数 ###

常见哈希函数  
**1. 直接定制法**  
取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况  
**2. 除留余数法**  
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

### 哈希操作 ###

*  **插入元素**

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

*  **搜索元素**

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

*  **删除元素**

根据待删除元素的关键码，以此函数计算出该元素的存储位置并按此位置进行删除

*  ### 哈希冲突解决 ###
 *  **闭散列（线性探测法）**

**哈希表结构：在闭散列中，将哈希表底层结构设置为vector容器，容器中每一个元素为一个hashNode结构体，包括kv键值对和状态标志位**

**初始化将其hashNode的状态设置为空**

template <class k,class v>
    struct HashNode
    {
    	pair<k, v> kv;
    	STATE state = EMPTY;
    };
    
    template <class k, class v>
    class HashTable
    {
    public:
    	typedef HashNode<k, v> Node;
    	HashTable(size_t n = 10)
    		:HSTable(n)
    		,_size(0)
    	{
    	}
    private:
    	vector<Node> HSTable;
    	size_t _size;
    };

上述插入操作，可能会产生哈希冲突，通过线性探测法，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，插入一个新元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

在查找过程值，要想找到发生冲突元素，就必须给标志位

删除也类似，采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

enum STATE{
    	EXIST  //已存在
    	,DELETE  //删除过
    	,EMPTY   //空位置
    };

通过定义一个枚举类型，包括已存在不可插入状态（EXIST），空位置可插入状态(EMPTY)，删除过的位置状态(DELETE)

插入代码如下：

bool insert(const pair<k, v>& kv)
    	{
    		checkcapacity();
    		//计算hash位置
    		int idx = kv.first%HSTable.size();
    		//搜索
    		while (HSTable[idx].state != EMPTY)//其余两种状态都需要继续查找
    		{
    			//当前位置已经有数据，且与要插入新数据相同，则插入失败
    			if (HSTable[idx].state ==EXIST&& kv.first == HSTable[idx].kv.first)
    				return false;
    			++idx;
    			if (idx == HSTable.size() - 1)//向后查找过程到结尾 从头再开始找空位
    				idx = 0;
    		}
    		//此时找到空位置,插入新元素，状态置为已存在，hash表大小+1
    		HSTable[idx].kv = kv;
    		HSTable[idx].state = EXIST;
    		_size++;
    		return true;
    		//插满扩容
    		
    	}

由于插入过程实际上是在vector容器基础上完成，如果需要插入元素足够多，可能导致当前所创造的哈希表插满，此时就需要检查容量，进行扩充操作

扩容判断条件是：负载因子>0.7,此时认为产生冲突的可能性大，需要进行扩容

扩容并非在原表基础上增大size，而是开辟新表，将原表已存在状态位置元素进行逐一存放，代码如下：

void checkcapacity()
    	{
    		//负载因子控制是否增容
    		//负载因子越小，冲突越小，但空间浪费越大
    		if (HSTable.size()==0&&_size * 10 / HSTable.size() > 7)
    		{
    			//开新表
    			int newcap = HSTable.size() == 0 ? 10 : 2 * HSTable.size();
    			HashTable<k, v> newHST(newcap);
    			//直接拷贝会导致hash值计算前后不一致
    			//需要重新计算hash位置
    			for (int i = 0; i < HSTable.size(); i++)
    			{
    				if (HSTable[i].state == EXIST)
    				{
    					newHST.insert(HSTable[i].kv);
    				}
    			}
    			swap(newHST);
    		}
    	}
    	void swap(HashTable<k, v>& HT)
    	{
    		swap(HSTable,HT.HSTable);
    		swap(_size, HT._size);
    	}

查找：由于hash冲突，直接通过索引查找难以找到发生hash冲突而通过线性探测法存放的元素，非空位置逐一查找，如果索引超过了表大小，需要循环从头开始

Node* find(const k& key)
    	{
    		//计算hash位置
    		int idx = key%HSTable.size();
    		//搜索
    		while (HSTable[idx].state != EMPTY)
    		{
    			if (HSTable[idx].state == EXIST && key == HSTable[idx].first)
    				return &HSTable[idx];
    			++idx;
    			if (idx == HSTable.size() - 1)
    				idx = 0;
    		}
    		return nullptr;
    	}

删除：删除并非真删除，释放元素，而是改变对应元素位置状态信息

bool erase(const k& key)
    	{
    		Node* node = find(key);
    		if (node)
    		{
    			node->state = DELETE;
    			_size--;
    			return true;
    		}
    		return false;
    	}

*  **开散列（哈希桶）**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

bool insert(const V& val)
    	{
    		checkcapacity();
    		KeyofValue kov;
    		int idx = kov(val) % _hst.size();
    
    		//查找
    		Node* cur = _hst[idx];
    		while (cur)
    		{
    			if (kov(cur->_val) == kov(val))
    			{
    				//key重复
    				return false;
    			}
    			cur = cur->_next;
    		}
    		//插入  头插
    		cur = new Node(val);
    		cur->_next = _hst[idx];
    		_hst[idx] = cur;
    		_size++;
    		return true;
    	}

**哈希桶通过建立新连接进行扩容操作：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

void checkcapacity()
    	{
    		if (_size == _hst.size())
    		{
    			int newcap = _size == 0 ? 10 : 2 * _size;
    			vector<Node*> newhst(newcap);
    			KeyofValue kov;
    			for (int i = 0; i < _hst.size(); i++)
    			{
    				Node* cur = _hst[i];
    				while (cur)
    				{
    					Node* next = cur->_next;
    					int idx = kov(cur->_val) % newhst.size();
    					//新表头插
    					cur->_next = newhst[idx];
    					newhst[idx] = cur;
    
    					cur = next;
    				}
    				//原表断开 置空
    				_hst[i] = nullptr;
    			}
    			swap(_hst,newhst);
    		}
    	}

*  **迭代器操作：**

**迭代器的++步骤：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

#include<iostream>
    #include<vector>
    using namespace std;
    
    template <class V>
    struct HashNode
    {
    	V _val;
    	HashNode<V>* _next;
    
    	HashNode(const V& val)
    		:_val(val)
    		,_next(nullptr)
    	{
    
    	}
    };
    
    //hash表的前置声明
    template<class K, class V, class KeyofValue>
    class HSTable;
    
    
    //hash表迭代器  封装单链表节点
    template<class K, class V, class KeyofValue>
    struct HashIterator{
    	typedef HashNode<V> Node;
    	typedef HSTable<K, V, KeyofValue> ht;
    	typedef HashIterator<K, V, KeyofValue> Self;
    	//成员：节点指针，哈希表指针
    	Node* _node;
    	ht* _hptr;
    
    	HashIterator(Node* node,ht* hptr)
    		:_node(node)
    		,_hptr(hptr)
    	{
    
    	}
    
    	Self& operator++()
    	{
    		if (_node->_next)
    		{
    			_node = _node->_next;
    		}
    		//找下一个非空链表头结点
    		else
    		{
    			//计算当前节点在hash表中位置
    			KeyofValue kov;
    			int idx = kov(_node->_val) % _hptr->_hst.size();
    			//从下一位置开始查找
    			++idx;
    			for (int; idx < _hptr->_hst.size(); idx++)
    			{
    				if (_hptr->_hst[idx])
    				{
    					_node = _hptr->_hst[idx];//找到非空链表头结点给node记录
    					break;
    				}
    			}
    			if (idx = _hptr->_hst.size())//此时走到end位置  将node节点置为空
    			{
    				_node = nullptr;
    			}
    		}
    		return *this;
    	}
    };
    
    
    
    template<class K,class V,class KeyofValue>
    class HSTable
    {
    public:
    	typedef HashNode<V> Node;
    	typedef HashIterator<K, V, KeyofValue> iterator;
    
    	//由于迭代器需要访问其私有成员_hst  声明为友元类
    	friend HashIterator<K, V, KeyofValue>;
    	HSTable(int n=10)
    		:_hst(n)
    		,_size(0)
    	{
    
    	}
    
    	iterator begin()
    	{
    		for (int i = 0; i < _hst.size(); i++)
    		{
    			if (_hst[i])
    			{
    				return iterator(_hst[i], this);
    			}
    			else
    				return iterator(nullptr,this);
    
    		}
    	}
    	iterator end()
    	{
    		return iterator(nullptr, this);
    	}
    
    
    private:
    	vector<Node*> _hst;
    	int _size;
    };

### 哈希表的应用 ###

*  位图

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

比如Tencent的一道面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

此题解法较多，一般容易想到的就是暴力求解，直接遍历查询，但海量数据导致时间复杂度过大，无法实际中应用；稍微进阶一些的会想到采用二分查找，虽然相比较于直接遍历，把时间复杂度从O(n)提升到O(lgn)，但对于40亿数据还是难以实现

而通过位图可以实现：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

代码实现如下：

#include<iostream>
    #include<vector>
    using namespace std;
    
    /*
    位图应用：
    （1）存放不重复数据简单信息，不需要存放数据本身   优点：节省空间，查找效率高
    
    */
    class bitset
    {
    public:
    	//位图内存大小与数据范围有关
    	bitset(size_t range)
    		:_bit(range/32+1)
    	{
    
    	}
    	//存储信息
    	void set(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位置1  按位或运算
    		_bit[idx] |= (1 << bitidx);  //把1向左移动bixidx位置  或运算之后  将其置为1
    	}
    	//查找信息
    	bool test(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位右移bitidx后 与1 与运算  如果为1 则为1  否则为0
    		return (_bit[idx] >> bitidx)&1;		
    	}
    
    	//删除信息
    	void reset(size_t num)
    	{
    		//计算整数位置
    		int idx = num / 32;
    		//计算比特位置
    		int bitidx = num % 32;
    		//对应比特位置10
    		_bit[idx] &= ~(1 << bitidx);
    	}
    private:
    	//数组
    	vector<int> _bit;
    	//默认bit位个数为 32 位
    };

*  布隆过滤器

布隆过滤器是用**多个哈希函数**，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器的实现依然需要借助位图的实现来完成，依然依靠0-1进行标记数据是否存在

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

**注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。**

*  **查找：**

**布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。**

*  **删除：**

**布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。  
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。**

**代码如下：**

//布隆过滤器
    // 假设布隆过滤器中元素类型为K，每个元素对应3个哈希函数
    template<class T, class KToInt1, class KToInt2,class KToInt3>
    class BloomFilter
    {
    public:
    	BloomFilter(size_t size) // 布隆过滤器中元素个数
    		: _bmp(3 * size), _bitcount(3 * size)
    	{}
    
    	//存储信息：使用多个bit位存储
    	void set(const T& val)
    	{
    		KToInt1 k1;
    		KToInt2 k2;
    		KToInt3 k3;
    		int idx1 = k1(val) % _bitcount;
    		int idx2 = k2(val) % _bitcount;
    		int idx3 = k3(val) % _bitcount;
    		
    		_bmp.set(idx1);
    		_bmp.set(idx2);
    		_bmp.set(idx3);
    	}
    
    	bool test(const T& val)
    	{
    		KToInt1 k1;
    		KToInt2 k2;
    		KToInt3 k3;
    		int idx1 = k1(val) % _bitcount;
    		int idx2 = k2(val) % _bitcount;
    		int idx3 = k3(val) % _bitcount;
    
    		if (!_bmp.test(idx1))
    			return false;//三个有一个为0 肯定不存在  三个均为1  可能存在（不能说一定存在）
    		if (!_bmp.test(idx2))
    			return false;
    		if (!_bmp.test(idx3))
    			return false;
    		if (_bmp.test(idx1) && _bmp.test(idx2) && _bmp.test(idx3))
    			return true;
    	}
    private:
    	bitset _bmp;
    	size_t _bitcount; // bit位的个数
    };
    
    struct KToInt1
    {
    	//hash函数计算方式1  
    };
    
    struct KToInt2
    {
    	//hash函数计算方式2 
    };
    
    struct KToInt3
    {
    	//hash函数计算方式3 
    };
    void test()
    {
    	BloomFilter<string, KToInt1, KToInt2, KToInt3> bf(10);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221014/a8055b2fc3ca464cacbaeebad1774d49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221014/d741090355994af2b233939cf4f9f9f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221014/54d719bfae9549c0a668443d403ff187.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221014/57875441827c4a0e9566a0923a1e7d52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221014/828dbd423abc44909b260769acd668d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221014/176d87157e974785a8840c86802e3e0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221014/bfba2c7a30034418892a3de8bbd8f0c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: /images/20221014/5aae91d12d784adca809afe1958fdca7.png