您现在的位置是：首页 > Javascript

当前栏目

【C++进阶】哈希（万字详解）—— 运用篇(下）

哈希

2023-04-18 16:07:26 时间

🎇C++学习历程：入门

博客主页：一起去看日落吗
持续分享博主的C++学习历程
博主的能力有限，出现错误希望大家不吝赐教
分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。

🍁 🍃 🍂 🌿

🍃 1. 模拟实现

🌿 1.1 哈希表代码

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

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

	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		static const size_t primeList[PRIMECOUNT] =
		{
			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
		};

		size_t i = 0;
		for (; i < PRIMECOUNT; ++i)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}

		return primeList[i];
	}

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:

		// 拷贝 和 赋值 需要自己实现桶的拷贝

		~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;
			}
			_n = 0;
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hf;
			// 素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 1、cur是头结点
					// 2、非头节点
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash hf;

			//当负载因子到1时，进行扩容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());

				//HashTable<K, V> newHT;
				vector<Node*> newtables;
				newtables.resize(newSize, nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t index = hf(cur->_kv.first) % newSize;
						cur->_next = newtables[index];
						newtables[index] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				newtables.swap(_tables);
			}

			size_t index = hf(kv.first) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == kv.first)
				{
					return false;
				}
				else
				{
					cur = cur->_next;
				}
			}

			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;

			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0; // 存储多少有效数据
	};
}

🌿 1.2 哈希表的改造

模板参数的改造

K:关键码类型
V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是unordered_set,V为 K
KeyOfT: 在哈希表中需要取到value，因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现
Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，如果是Key为string类型，需要将Key转换为整形数字才能取模

template<class K, class T, class KeyOfT, class Hash = HashFunc<T> >
class HashBucket;

哈希表节点结构

template<class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;

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

如果是unordered_map，v代表一个键值对，如果是unordered_set,v为 K

operator++模拟实现

当下一个节点不为空时，++后的节点就在当前桶，返回即可，当下一个节点为空时，我们需要找下一个桶，首先通过当前节点计算找到当前节点所在桶的位置index，计算出后，++index即找到了下一个桶，当下一个桶存在时，如果下一个桶里面有数据(即不为空)，则将第一个数据给当前节点，就实现了++，否则继续找下一个桶，当循环出来时，有可能是找到++后的节点了，也有可能说明走完了后面没有桶了，所以循环出来需要判断是不是没有桶了，没有桶则返回nullptr

Self operator++()
{
    if (_node->_next) // 在当前桶迭代
    {
        _node = _node->_next;
    }
    else // 找下一个桶
    {
        KeyOfT kot;
        const K& key = kot(_node->_data);
        Hash hf;
        size_t index = hf(key) % _ht->_tables.size();
        ++index;
        _node = nullptr;
        while (index < _ht->_tables.size())
        {
            if (_ht->_tables[index])
            {
                _node = _ht->_tables[index];
                break;
            }
            else
            {
                ++index;
            }
        }

        // 后面没有桶了
        if (index == _ht->_tables.size())
        {
            _node = nullptr;
        }
    }

    return *this;
}

operator*的模拟实现

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

operator->的模拟实现

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

operator==和operator!=的模拟实现

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

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

🌿 1.3 哈希表的最终代码

namespace Byih
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

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

	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		static const size_t primeList[PRIMECOUNT] =
		{
			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
		};

		size_t i = 0;
		for (; i < PRIMECOUNT; ++i)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}

		return primeList[i];
	}

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

	template<class K, class T, class Hash, class KeyOfT>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, Hash, KeyOfT> HT;
		typedef HTIterator<K, T, Hash, KeyOfT> Self;

		Node* _node;
		HT* _ht;

		HTIterator(Node* node, HT* ht)
			:_node(node)
			, _ht(ht)
		{}

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

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


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

		Self operator++()
		{
			if (_node->_next) // 在当前桶迭代
			{
				_node = _node->_next;
			}
			else // 找下一个桶
			{
				KeyOfT kot;
				const K& key = kot(_node->_data);
				Hash hf;
				size_t index = hf(key) % _ht->_tables.size();
				++index;
				_node = nullptr;
				while (index < _ht->_tables.size())
				{
					if (_ht->_tables[index])
					{
						_node = _ht->_tables[index];
						break;
					}
					else
					{
						++index;
					}
				}

				// 后面没有桶了
				if (index == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}
	};

	template<class K, class T,  class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<T> Node;

		//template<class K, class T, class Hash, class KeyOfT>
		friend struct HTIterator<K, T, Hash, KeyOfT>;
	public:
		typedef HTIterator<K, T, Hash, KeyOfT> iterator;

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

			return end();
		}

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

		// 拷贝 和 赋值 需要自己实现桶的拷贝

		~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;
			}

			_n;
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hf;
			KeyOfT kot;

			// 素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					// 1、cur是头结点
					// 2、非头节点
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hf;
			KeyOfT kot;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}

			return nullptr;
		}

		bool Insert(const T& data)
		{
			Hash hf;
			KeyOfT kot;

			//当负载因子到1时，进行扩容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());

				//HashTable<K, V> newHT;
				vector<Node*> newtables;
				newtables.resize(newSize, nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						const K& key = kot(cur->_data);
						size_t index = hf(key) % newSize;

						cur->_next = newtables[index];
						newtables[index] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				newtables.swap(_tables);
			}

			const K& key = kot(data);
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (kot(cur->_data) == kot(data))
				{
					return false;
				}
				else
				{
					cur = cur->_next;
				}
			}

			Node* newnode = new Node(data);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;

			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0; // 存储多少有效数据
	};
}

🌿 1.4 unordered_map 的模拟实现

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

		iterator end()
		{
			return _ht.end();
		}
        //插入
		pair<iterator,bool> insert(const pair<const K, V>& kv)
		{
			return _ht.Insert(kv);
		}
        //[]运算符重载
         V& operator[](const K& key)
         {
             pair<iterator,bool> ret = insert(make_pair(key,V()));
             iterator it = ret.first;
             return it->second;
         }
        //删除
        bool erase(const K& key)
        {
            return _ht.Erase(key);
        }
        //查找
        iterator find(const K& key)
        {
            return _ht.Find(key);
        }
	private:
		Byih::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
	};
}

实现unordered_map只需要调用底层哈希表对应的接口即可，实现unordered_set不一样的是它不需要实现[]运算符重载

🍃 2. 位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。适用于海量数据的状态：比如：40亿数据，需要16G内存；若用位图存放这些数据在不在的状态，只需要16/32G，约500M。

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

在这里插入图片描述

主要应用：

快速查找某个数据是否在一个集合中
排序 + 去重
求两个集合的交集、并集等
操作系统次磁盘中的标记等

优点：节省空间，速度快
缺点：只能处理整形数据

🌿 2.1 库中的位图

主要接口：set（将某位设为1） reset（将某位设为0） test（判断某一位是否为1）

	bitset<100> bs;
	//将某位设置为1
	bs.set(11);bs.set(5);bs.set(78);bs.set(23);bs.set(12);
	//将某位设置为0
	bs.reset(11);
 
	//判断某位是否为1
	for (size_t i = 0; i < 100; i++)
	{
		//cout << i << ":" << bs.test(i) << " ";
		//if (i != 0 && i % 10 == 0)
		//	cout << endl;
		if (bs.test(i) == 1)
			cout << i << " ";
	}
	cout << endl;

🌿 2.2 模拟实现位图

	template<size_t N>
	class byh
	{
	public:
		BitSet()
		{
			_bits.resize(N / 32 + 1, 0);//默认构造，会对位图进行初始化
		}
 
		// 把x映射的位标记成1
		void Set(size_t x)
		{
			assert(x < N);
 
			// 算出x映射的位在第i个整数
			// 算出x映射的位在这个整数的第j个位
			size_t i = x / 32;
			size_t j = x % 32;
 
			// _bits[i] 的第j位标记成1，并且不影响他的其他位
			_bits[i] |= (1 << j); //或等于
			//(1 << j)
			//00000001000000000
		}
 
		void Reset(size_t x)
		{
			assert(x < N);
 
			size_t i = x / 32;
			size_t j = x % 32;
 
			// _bits[i] 的第j位标记成0，并且不影响他的其他位
			_bits[i] &= (~(1 << j)); //与等于
			//对 1 << j 取反就行
			//~(1 << j)
			//1111111101111111111	
		}
 
 
		bool Test(size_t x)
		{
			assert(x < N);
 
			size_t i = x / 32;
			size_t j = x % 32;
 
			// 如果第j位是1，结果是非0，非0就是真
			// 如果第j为是0，结果是0，0就是假
			return _bits[i] & (1 << j);//直接把这一位取出来是1还是0
			//return (_bits[i] >> j) & 1;//这样写也可以
		}
	private:
		vector<int> _bits;
	};

🍃 3. 布隆过滤器

🌿 3.1 布隆过滤器提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

用哈希表存储用户记录，缺点：浪费空间
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器

🌿 3.2 布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

在这里插入图片描述
原理讲解

🌿 3.3 布隆过滤器优点

增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
哈希函数相互之间没有关系，方便硬件并行运算
布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
使用同一组散列函数的布隆过滤器可以进行交、并、差运算

🌿 3.4 布隆过滤器缺陷

有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
不能获取元素本身
一般情况下不能从布隆过滤器中删除元素
如果采用计数方式删除，可能会存在计数回绕问题

🌿 3.5 布隆过滤器模拟实现

//布隆过滤器实际上是对位图的改进，所以实现上也是对位图的封装，一般只提供set和test接口，不能实现reset（删除）
template<size_t N, class K = std::string,class Hash1 = HashBKDR,class Hash2 = HashAP,class Hash3 = HashDJB>
//后面几个是字符串哈希函数的仿函数
class BloomFilter
{
public:
	void Set(const K& key)
	{
		//Hash1 hf1;
		//size_t i1 = hf1(key);//以下写法也可以
		size_t i1 = Hash1()(key) % N;//Hash1()是仿函数的匿名对象
		size_t i2 = Hash2()(key) % N;
		size_t i3 = Hash3()(key) % N;
 
		cout << i1 << " " << i2 << " " << i3 << endl;
 
		_bitset.Set(i1);
		_bitset.Set(i2);
		_bitset.Set(i3);
	}
 
	bool Test(const K& key)//判断是否存在
	{
		size_t i1 = Hash1()(key) % N;
		if (_bitset.Test(i1) == false)
		{
			return false;
		}
 
		size_t i2 = Hash2()(key) % N;
		if (_bitset.Test(i2) == false)
		{
			return false;
		}
 
		size_t i3 = Hash3()(key) % N;
		if (_bitset.Test(i3) == false)
		{
			return false;
		}
 
		// 这里3个位都在，有可能是其他key占了，在是不准确的，存在误判
		// 不在是准确的
		return true;
	}
 
private:
	byh::BitSet<N> _bitset; // 对位图的封装
	//byh::vector<char> _bitset;
};

🍃 4. 海量数据面试题

🌿 4.1 位图应用

题目一

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

思路：100亿的整数范围还是42亿，因此用一个位图来存储只需要512M
将一个文件映射到位图中，再依次读取另一个文件的数据，看在不在位图中，在就是交集；或者构建两个位图，求他们的交集；

题目二

给定100亿个整数，设计算法找到只出现一次的整数？

思路：用位图的思想，一个bit位能表示两种状态，这里至少是3种状态，因此需要两个bit位00表示没出现；01表示只出现一次；10表示出现过2次及以上；将所有数插入位图中，然后遍历位图，找出标志位01的位即为所求

🌿 4.2 哈希切分+布隆过滤器应用

哈希切分的原理：就是将一个大文件，利用哈希的原理（i = Hash()(ip) % 100， i表示小文件的编号），将其分为若干个小文件。

哈希切割的特点：相同的ip一定进入了同一个小文件当中。

题目三

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

近似算法：利用布隆过滤器100亿个query（ip），可以看做string，假设为100G，那么两个文件一共是200G。将A文件依次映射到一个布隆过滤器中，再依次读取B文件中的数据，与布隆过滤器里的内容比较，在就是交集，但是会有一定的误判率。
精确算法：利用哈希切分 + 布隆过滤器
可以将AB文件都切割成200个小文件（哈希切分并不是均匀的，依次要保证小文件小于内存大小），按照同样的映射函数 i = Hash()(ip) % 200 这样AB中相同的ip，都进了各自对应的编号i的小文件，因此只需要依次比较Ai和Bi中的交集即可

在这里插入图片描述

题目四

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

思路：哈希切分，切分成100个小文件（相同的ip一定进入了同一个小文件）然后只需统计各个小文件各个ip的频次（比如用一个map<string, int>统计），找出每个小文件频次最高的ip地址进行比较即可；要求 top K的ip，可以建一个K个元素小堆，后面的元素依次与堆顶元素比较，比它大就替换进堆，最终这个小堆就是top K ；

在这里插入图片描述

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程

当前栏目

【C++进阶】哈希（万字详解）—— 运用篇(下）

目录

🍃 1. 模拟实现

🌿 1.1 哈希表代码

🌿 1.2 哈希表的改造

🌿 1.3 哈希表的最终代码

🌿 1.4 unordered_map 的模拟实现

🍃 2. 位图

🌿 2.1 库中的位图

🌿 2.2 模拟实现位图

🍃 3. 布隆过滤器

🌿 3.1 布隆过滤器提出

🌿 3.2 布隆过滤器概念

🌿 3.3 布隆过滤器优点

🌿 3.4 布隆过滤器缺陷

🌿 3.5 布隆过滤器模拟实现

🍃 4. 海量数据面试题

🌿 4.1 位图应用

🌿 4.2 哈希切分+布隆过滤器应用

相关文章