C++哈希(个人笔记)

C++哈希

    • 1.unordered_mapd
      • 1.1unordered_map的构造函数
      • 1.2unorder_map的容量
      • 1.3unordered_map的迭代器
      • 1.4unordered_map的元素访问
      • 1.5unorder_map的查找
      • 1.6unordered_map的修改操作
      • 1.7unordered_map的桶操作
    • 2.unordered_set
    • 3.unordered_set和unordered_set的笔试题
    • 4.哈希
      • 4.1哈希概念
      • 4.2哈希冲突
      • 4.3哈希函数
      • 4.4哈希冲突解决
        • 4.4.1闭散列
          • 4.4.1.1线性探测的实现
        • 4.4.2开散列
          • 4.4.2.1开散列的实现
    • 4.unordered_map和unordered_set模拟实现
      • 4.1哈希表的改造
      • 4.2unordered_set模拟实现
      • 4.3unordered_map模拟实现
    • 5.位图
      • 5.1位图的实现
      • 5.2布隆过滤器
        • 5.2.1布隆过滤器的实现

1.unordered_mapd

C++unorder_map官方文档

1.1unordered_map的构造函数

函数声明功能介绍
unordered_map构造不同格式的unordered_map对象

1.2unorder_map的容量

函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数

1.3unordered_map的迭代器

函数声明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器

1.4unordered_map的元素访问

函数声明功能介绍
operator[]返回与key对应的value，没有则返回一个默认值

注意：
该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

1.5unorder_map的查找

函数声明功能介绍
iterator find(const K& key)返回key在哈希桶中的位置
size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

1.6unordered_map的修改操作

函数声明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap(unorder map&)交换两个容器中的元素

1.7unordered_map的桶操作

函数声明功能介绍
size_t bucket count()const返回哈希桶中桶的总个数
size_t bucket size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

2.unordered_set

C++unordered_set官方文档
这里不在一 一列举

3.unordered_set和unordered_set的笔试题

在长度 2N 的数组中找出重复 N 次的元素
在这里插入图片描述

class Solution {
public:
    int repeatedNTimes(vector<int>& nums)
    {
        unordered_map<int, int> found;
        for (int num : nums)
        {
            found[num]++;
        }
        for (auto it = found.begin(); it != found.end(); ++it)
        {
            if (it->second == nums.size() / 2)
            {
                return it->first;
            }
        }
        return -1;
    }
};

两个数组的交集
在这里插入图片描述

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        auto it1=s1.begin();
        auto it2=s2.begin();
        vector<int> v;
        while(it1!=s1.end()&&it2!=s2.end())
        {
            if(*it1<*it2)
            {
                ++it1;
            }
            else if(*it1>*it2)
            {
                ++it2;
            }
            else
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return v;
    }
};

两个数组的交集 II
在这里插入图片描述

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        multiset<int> s1(nums1.begin(),nums1.end());
        multiset<int> s2(nums2.begin(),nums2.end());
        auto it1=s1.begin();
        auto it2=s2.begin();
        vector<int> v;
        while(it1!=s1.end()&&it2!=s2.end())
        {
            if(*it1<*it2)
            {
                it1++;
            }
            else if(*it1>*it2)
            {
                it2++;
            }
            else
            {
                v.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return v;
    }
};

存在重复元素
在这里插入图片描述

class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int,int> mp;
        for(int num:nums)
        {
            mp[num]++;
        }
        auto it=mp.begin();
        while(it!=mp.end())
        {
            if(it->second>=2)
            {
                return true;
            }
            ++it;
        }
        return false;
    }
};

两句话中的不常见单词
在这里插入图片描述

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2)
    {
        vector<string> v;
        unordered_map<string,int> mp;
        stringstream ss1(s1);
        string word;
        while(ss1>>word)
        {
            mp[word]++;
        }

        stringstream ss2(s2);
        while(ss2>>word)
        {
            mp[word]++;
        }
        for(auto& w:mp)
        {
            if(w.second==1)
            {
                v.push_back(w.first);
            }
        }
        return v;
    }
};

4.哈希

4.1哈希概念

通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系，在查找时通过该函数可以很快找到该元素。

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

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

哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

4.2哈希冲突

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

4.3哈希函数

哈希函数设计原则：

  1. 1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

  2. 哈希函数计算出来的地址能均匀分布在整个空间中

  3. 哈希函数应该比较简单
    常见的哈希函数

  4. 直接定址法–(常用)
    取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
    优点：简单、均匀
    缺点：需要事先知道关键字的分布情况
    使用场景：适合查找比较小且连续的情况

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

4.4哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

4.4.1闭散列

也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

1.插入

  1. 通过哈希函数获取待插入元素在哈希表中的位置
  2. 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素
    在这里插入图片描述
    2.删除
    采用闭散列处理哈希冲突时，不能物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。（也就是给位置标记状态）
// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
4.4.1.1线性探测的实现
enum Status
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Status _s;          //状态
};

//HashFunc<int>
template<class K>
struct HashFunc
{
	size_t operator()(const K& Key)
	{
		return (size_t)Key;
	}
};

//HashFunc<string>
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		cout << key << ":" << hash << endl;
		return hash;
	}
};

template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
public:
	HashTable()
	{
		_tables.resize(10);
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
		{
			return false;
		}
		//负载因子0.7就扩容
		if (_n * 10 / _tables.size() == 7)
		{
			size_t newSize = _tables.size() * 2;
			HashTable<K, V> newHT;
			newHT._tables.resize(newSize);
			for (size_t i = 0;i < _tables.size();i++)
			{
				if (_tables[i]._s == EXIST)
				{
					newHT.Insert(_tables[i]._kv);
				}
			}
			_tables.swap(newHT._tables);
		}

		Hash hf;
		size_t hashi = hf(kv.first) % _tables.size();
		while (_tables[hashi]._s == EXIST)
		{
			hashi++;
			hashi %= _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._s = EXIST;
		++_n;
		return true;
	}

	HashData<K, V>* Find(const K& key)
	{
		Hash hf;
		size_t hashi = hf(key) % _tables.size();
		while (_tables[hashi]._s != EMPTY)
		{
			if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}
			hashi++;
			hashi %= _tables.size();
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_s = DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}

	void Print()
	{
		for (size_t i = 0;i < _tables.size();i++)
		{
			if (_tables[i]._s == EXIST)
			{
				cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
			}
			else if (_tables[i]._s == EMPTY)
			{
				printf("[%d]->\n", i);
			}
			else
			{
				printf("[%d]->D\n", i);
			}
		}
		cout << endl;
	}

private:
	vector<HashData<K,V>> _tables;
	size_t _n = 0;//存储的关键字的个数
};

线性探测优点：实现非常简单

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同
关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。

4.4.2开散列

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

4.4.2.1开散列的实现
//HashFunc<int>
template<class K>
struct HashFunc
{
	size_t operator()(const K& Key)
	{
		return (size_t)Key;
	}
};

//HashFunc<string>
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		cout << key << ":" << hash << endl;
		return hash;
	}
};

template<class K, class V>
struct HashNode
{
	HashNode* _next;
	pair<K, V> _kv;

	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};

template<class K, class V,class Hash=HashFunc<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	HashTable()
	{
		_tables.resize(10);
	}

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;

		Hash hf;

		// 负载因子最大到1
		if (_n == _tables.size())
		{
			vector<Node*> newTables;
			newTables.resize(_tables.size() * 2, nullptr);
			// 遍历旧表
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;

					//挪动到映射的新表
					size_t hashi = hf(cur->_kv.first) % newTables.size();

					cur->_next = newTables[hashi];//标记
					newTables[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}

			_tables.swap(newTables);
		}

		size_t hashi = hf(kv.first) % _tables.size();
		Node* newnode = new Node(kv);

		// 头插
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;

		return true;
	}

	Node* Find(const K& key)
	{
		Hash hf;
		size_t hashi = hf(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		Hash hf;
		size_t hashi = hf(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}

	void Some()
	{
		size_t bucketSize = 0;
		size_t maxBucketLen = 0;
		size_t sum = 0;
		double averageBucketLen = 0;

		for (size_t i = 0;i < _tables.size();i++)
		{
			Node* cur = _tables[i];
			if (cur)
			{
				++bucketSize;
			}
			size_t bucketLen = 0;
			while (cur)
			{
				++bucketLen;
				cur = cur->_next;
			}

			sum += bucketLen;
			if (bucketLen > maxBucketLen)
			{
				maxBucketLen = bucketLen;
			}
		}
		printf("all bucketSize:%d\n", _tables.size());
		printf("bucketSize:%d\n", bucketSize);
		printf("maxBucketLen:%d\n", maxBucketLen);
		printf("averageBucketLen:%lf\n\n", averageBucketLen);
	}

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

4.unordered_map和unordered_set模拟实现

4.1哈希表的改造

//HashFunc<int>
template<class K>
struct HashFunc
{
	size_t operator()(const K& Key)
	{
		return (size_t)Key;
	}
};

//HashFunc<string>
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		cout << key << ":" << hash << endl;
		return hash;
	}
};
namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		HashNode* _next;
		T _data;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	// 前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;
		size_t _hashi;

		__HTIterator(Node* node,HashTable<K,T,KeyOfT,Hash>* pht,size_t hashi)
			:_node(node)
			,_pht(pht)
			,_hashi(hashi)
		{}

		__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				++_hashi;
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					++_hashi;
				}
				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

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

	//unordered_set->HashTable<K,K>
	//unordered_map->HashTable<K,pair<K,V>>
	template<class K, class T,class KeyOfT,class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;

		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

		iterator begin()
		{
			for (size_t i = 0;i < _tables.size();i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this, i);
				}
			}
			return end();
		}

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

		const_iterator begin() const
		{
			for (size_t i = 0;i < _tables.size();i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}

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

		HashTable()
		{
			_tables.resize(10);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<iterator,bool> Insert(const T& data)
		{
			Hash hf;
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}

			// 负载因子最大到1
			if (_n == _tables.size())
			{
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				// 遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						//挪动到映射的新表
						size_t hashi = hf(kot(data)) % newTables.size();

						cur->_next = newTables[hashi];//标记
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			size_t hashi = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);

			// 头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(iterator(newnode,this,hashi),true);
		}

		iterator Find(const K& key)
		{
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this,hashi);
				}
				cur = cur->_next;
			}
			return end();
		}

		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			size_t sum = 0;
			double averageBucketLen = 0;

			for (size_t i = 0;i < _tables.size();i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}
				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;
				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}
			averageBucketLen = (double)sum / (double)bucketSize;
			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}

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

4.2unordered_set模拟实现

#pragma once
#include"HashTable.h"

namespace ljh
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

		/*iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}*/

		const_iterator begin() const
		{
			return _ht.begin();
		}

		const_iterator end() const
		{
			return _ht.end();
		}

		pair<const_iterator, bool> insert(const K& key)
		{
			auto ret = _ht.Insert(key);
			return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
	};
}

4.3unordered_map模拟实现

#pragma once
#include"HashTable.h"
namespace ljh
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

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

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

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

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};
}

5.位图

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
解决方案：
1：暴力遍历：时间复杂度O（N）
2.快排（O（NlogN）)+二分查找（logN）
3.位图
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，可以使用一个二进制比特位来代表数据是否存在，如果二进制比特位为1，代表存在，为0代表不存在。

5.1位图的实现

//N为需要多少比特位
template<size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 32 + 1);
	}

	void set(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] |= (1 << j);
	}

	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] &= ~(1 << j);
	}

	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _bits[i] & (1 << j);
	}

private:
	vector<int> _bits;
};

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		//00->01
		//01->10
		//10->11
		//11->不变
		if (_bs1.test(x) == false && _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false && _bs2.test(x) == true)
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		else if (_bs1.test(x) == true && _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
	}

	void Print()
	{
		for (size_t i = 0;i < N;i++)
		{
			if (_bs1.test(i) == false && _bs2.test(i) == true)
			{
				cout << "1->" << i << endl;
			}
			else if (_bs1.test(i) == true && _bs2.test(i) == false)
			{
				cout << "2->" << i << endl;
			}
		}
		cout << endl;
	}

private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

5.2布隆过滤器

具体实现思想：用多个哈希函数，将一个数据映射到位图结构中
作用：某样东西一定不存在或者可能存在
在这里插入图片描述
在这里插入图片描述

5.2.1布隆过滤器的实现
#include<string>
#include<iostream>
#include<vector>
using namespace std;
#include"bitset.h"
struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template<size_t N,class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;
		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	//void Reset(const K& key);一般不支持删除

	bool Test(const K& key)
	{
		//判断不存在是准确的，其他的都是存在偏差的
		size_t hash1 = HashFunc1()(key) % N;
		if (_bs.test(hash1) == false)
		{
			return false;
		}

		size_t hash2 = HashFunc2()(key) % N;
		if (_bs.test(hash2) == false)
		{
			return false;
		}

		size_t hash3 = HashFunc3()(key) % N;
		if (_bs.test(hash3) == false)
		{
			return false;
		}
		// 存在误判的
		return true;
	}

private:
	ljh::bitset<N> _bs;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/624549.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LVS负载均衡超详细入门介绍

LVS负载均衡超详细入门介绍

LVS 一、LVS入门介绍 1.1.LVS负载均衡简介 1.2.负载均衡的工作模式 1.2.1.地址转换NAT&#xff08;Network Address Translation&#xff09; 1.2.2.IP隧道TUN&#xff08;IP Tunneling&#xff09; 1.2.3.直接路由DR&#xff08;Direct Routing&#xff09; 1.3.…
阅读更多...
AI图像生成-原理

AI图像生成-原理

一、图像生成流程总结 【AI绘画】深入理解Stable Diffusion&#xff01;站内首个深入教程&#xff0c;30分钟从原理到模型训练 买不到的课程_哔哩哔哩_bilibili 二、如果只是用comfy UI生成图片 1、找到下面几个文件&#xff0c;把对应模型移动到对应文件夹即可使用 2、选择对…
阅读更多...
（八）SQL基础知识练习题（选择题）（下）#CDA学习打卡

（八）SQL基础知识练习题（选择题）（下）#CDA学习打卡

本文整理了SQL基础知识相关的练习题&#xff0c;共133道&#xff0c;可作为CDA一级的补充习题&#xff0c;也适用于刚入门初级SQL想巩固基础的同学。来源&#xff1a;如荷学数据科学题库&#xff08;技术专项-SQL&#xff09;。暂时按照原题库顺序present&#xff0c;如有需要之…
阅读更多...
Android XML的使用详解

Android XML的使用详解

一、布局文件&#xff1a; 在layout目录下&#xff0c;使用比较广泛&#xff1b;我们可以为应用定义两套或多套布局&#xff0c;例如&#xff1a;可以新建目录layout_land(代表手机横屏布局)&#xff0c;layout_port(代表手机竖屏布局)&#xff0c;系统会根据不同情况自动找到…
阅读更多...
Linux安装MySQL（CentOS 7）

Linux安装MySQL（CentOS 7）

安装步骤 下载的MySQL版本为mysql-8.0.26 进入网站MySQL&#xff0c;点击下载 找到mysql社区版 点击Archive&#xff0c;查看所有相关不同版本 点击MySQL Community Server 注意下载MySQL对应的Linux版本&#xff0c;CentOS7 对应 Linux7&#xff0c;如果下成Linux 8 则后面…
阅读更多...
【文末福利送资料】深度探索GPT模型，竟然10个字都不会说？

【文末福利送资料】深度探索GPT模型，竟然10个字都不会说？

目录 导读 自回归模型 那么什么时候停下呢&#xff1f; 该停下来&#xff0c;但是概率不让啊 GPT欠缺的两种能力 目录 导读 自回归模型 那么什么时候停下呢&#xff1f; 该停下来&#xff0c;但是概率不让啊 GPT欠缺的两种能力 缺少规划 反省和修订 所有的人工智能…
阅读更多...
Flume 的安装和使用方法(Spark-2.1.0)

Flume 的安装和使用方法(Spark-2.1.0)

一、Flume的安装 1.下载压缩包 https://www.apache.org/dyn/closer.lua/flume/1.7.0/apache-flume-1.7.0-bin.tar.gz 2.上传到linux中 3.解压安装包 cd #进入加载压缩包目录sudo tar -zxvf apache-flume-1.7.0-bin.tar.gz -C /usr/local # 将 apache-flume-1.7.0-bin.tar.g…
阅读更多...
透明加密软件推荐:哪款实用又高效?

透明加密软件推荐:哪款实用又高效?

透明加密软件是一种专门针对文件保密需求的计算机加密工具。 其核心在于“透明”二字&#xff0c;意味着整个加密过程对于使用者来说是无形且无感知的。 当用户进行文件的日常操作&#xff0c;如打开、编辑或保存时&#xff0c;透明加密软件会在后台自动进行加密和解密工作&a…
阅读更多...
Microsoft Edge浏览器，便携增强版 v118.0.5993.69

Microsoft Edge浏览器，便携增强版 v118.0.5993.69

01 软件介绍 Microsoft Edge浏览器&#xff0c;便携增强版&#xff0c;旨在无需更新组件的情况下提供额外的功能强化。这一增强版专注于优化用户体验和系统兼容性&#xff0c;具体包含以下核心功能的提升&#xff1a; 数据保存&#xff1a;通过优化算法增强了其数据保存能力&…
阅读更多...
AI系列：大语言模型的RAG（检索增强生成）技术（下）-- 使用LlamaIndex

AI系列：大语言模型的RAG（检索增强生成）技术（下）-- 使用LlamaIndex

目录 前言什么是LlamaIndex?LlamaIndex代码设置embedding模型设置LLM模型索引查询机 验证使用感受参考资料 前言 继上一篇文章AI系列&#xff1a;大语言模型的RAG&#xff08;检索增强生成&#xff09;技术&#xff08;上&#xff09;&#xff0c;这篇文章主要以LlamaIndex为…
阅读更多...
2024最新网络安全零基础入门学习路线，学网安看这篇就够了！

2024最新网络安全零基础入门学习路线，学网安看这篇就够了！

前言 一、什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“ 安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与…
阅读更多...
高通QCC3071 ANC调试录音新方法

高通QCC3071 ANC调试录音新方法

1， 从QCC307X和QCC517X的芯片开始ANC调试录音不再使用QACT软件了，而是使用Qualcomm ANC Filter Designer使用耳机进入Recording模式，再使用第三方的音频编辑软件来播放和录取声音。 2， 本文以QCC3071做Hybrid ANC，FF MIC使用数字MIC FB MIC使用模拟MEMS MIC为例来讲解具体…
阅读更多...
IDEA里面数据库编辑数据库链接/重命名库的操作

IDEA里面数据库编辑数据库链接/重命名库的操作

选中数据库图标&#xff0c;点击号&#xff0c;打开MySql 图片的每一处都可以修改&#xff0c;改完再点test connection&#xff0c;没问题再点确定按钮就可以
阅读更多...
4万字一文带你看懂车载摄像头技术、市场、发展前景

4万字一文带你看懂车载摄像头技术、市场、发展前景

1、小孔成像 在战国初期&#xff0c;我国学者墨子&#xff08;公元前468年-公元前376年&#xff09;和弟子们完成了世界上第一个小孔成像的实验&#xff0c;并记录在《墨经》中&#xff1a;“景到&#xff0c;在午有端&#xff0c;与景长。说在端。”“景。光之人&#xff0c;煦…
阅读更多...
从旺店通·企业奇门到金蝶云星空通过接口配置打通数据

从旺店通·企业奇门到金蝶云星空通过接口配置打通数据

从旺店通企业奇门到金蝶云星空通过接口配置打通数据 接通系统&#xff1a;旺店通企业奇门 慧策最先以旺店通ERP切入商家核心管理痛点——订单管理&#xff0c;之后围绕电商经营管理中的核心管理诉求&#xff0c;先后布局流量获取、会员管理、仓库管理等其他重要经营模块。慧策的…
阅读更多...
Spring事务和事务传播机制（@Transactional）

Spring事务和事务传播机制（@Transactional）

文章目录 Spring事务&#xff08;Transactional详解&#xff09;什么是事务为什么需要事务事务的操作(sql) Spring中的事务实现Spring编程式事务Spring声明式事务 TransactionalTransactional可以用来修饰方法或类对异常进行捕获细节&#xff1a; Transactional详解三个属性1. …
阅读更多...
牛客NC363 开锁【中等 BFS Java/Go/PHP】

牛客NC363 开锁【中等 BFS Java/Go/PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/e7cbabbf7e0a41ec98055ee5f3d33bbe https://www.lintcode.com/problem/796 思路 Java代码 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#x…
阅读更多...
在PyQt5中实现点击按钮打开新窗口功能—窗口的跳转功能实现

在PyQt5中实现点击按钮打开新窗口功能—窗口的跳转功能实现

百度搜索“pyqt5中如何点击按钮打开新的窗口”&#xff0c;自动生成以下参考代码。 在PyQt5中&#xff0c;要实现点击按钮打开新窗口&#xff0c;你需要定义一个新的窗口类&#xff0c;并在按钮的点击信号&#xff08;clicked&#xff09;处理函数中创建并显示这个新窗口。以下…
阅读更多...
Eclipse 里如何建立SAP应用服务层的CDS

Eclipse 里如何建立SAP应用服务层的CDS

关于Core Data Service(CDS) CDS:Core Data Ser vice.核心数据服务。CDS 是使用基于 SQL的数据定义语言(DDL)定义的&#xff0c;该语言基于标准 SQL 并带有一些附加概念。使用类似 SQL的灵活表达式可以进行复杂的数据建模。有两种类型的 CDS:ABAP CDS 和 HANA CDS。 S/4 HANA…
阅读更多...
安装HTTPS证书后，网站安全性会有哪些提升？

安装HTTPS证书后，网站安全性会有哪些提升？

在当今数字化时代&#xff0c;网络安全已成为一个不可忽视的话题。随着网络攻击的日益频繁&#xff0c;保护网站和用户数据的安全变得尤为重要。HTTPS作为一种加密的HTTP协议&#xff0c;为我们提供了一种安全的网络数据传输方式。本文将详细介绍HTTPS的工作原理、端口号以及如…
阅读更多...
最新文章

Copyright @ 2022~2023