网站建设公司的服务特点,网络推广软件排行,河北关键词搜索排名公司,沈阳建站费用在一个数据序列中查找某一个数据元素#xff0c;是数据管理时经常涉及的#xff0c;通常以比较的方式来完成#xff0c;典型的案例有无序序列的暴力查找#xff08;O(N)#xff09;、有序序列的二分查找#xff08;O(logN)#xff09;、平衡搜索树#xff08;O(logN)是数据管理时经常涉及的通常以比较的方式来完成典型的案例有无序序列的暴力查找O(N)、有序序列的二分查找O(logN)、平衡搜索树O(logN)等。但它们所处理的数据元素与其所在序列中的存储位置并没有明确的关系数据元素在序列中的位置是随机的。因此在查找某一个数据时可能需要进行数次的数据比较也就是说它们的查找效率往往取决于查找过程中数据元素的比较次数。而当数据达到一定量级继续通过比较的方式显然查找的代价较大且效率较低情况并不理想。而最理想的情况应当是直接就能找到需要的数据。那么是否存在一种更高效的方案可以不通过比较就直接找到一个数据呢 20世纪50年代德国计算机科学家汉斯·彼得·卢恩(Hans Peter Luhn)为计算机解读信息、快速搜索信息提供了一种新的、被称为哈希函数Hash Function或称散列函数的方案。数据元素通过哈希函数可以得到其在序列中的存储位置使每一个数据元素与其所在序列中的存储位置建立起一个映射关系模拟出“每一个数据元素在序列中的位置是确定的”存储位置通过哈希函数可以还原成数据元素的值模拟出“每一个数据元素都可以被直接访问”最快能达到O(1)。而由“数据元素-哈希函数-存储位置”构造的数据结构就称为哈希表Hash table或称散列表。 本篇博客梳理了哈希思想和相关数据结构并搭配对STL源码中线性探测、哈希桶、位图、布隆过滤器的模拟实现旨在更好地帮助读者理解哈希的功能和适用情景。 目录
一、常见的哈希函数
1.直接定址法最常用 2.除留余数法最常用
3.平方取中法
4.折叠法
5.随机数法
6.数学分析法
二、哈希冲突与解决方法
1.哈希冲突
2.闭散列
2-1.线性探测
2-2.二次探测
3.闭散列的模拟实现
3-1.基本结构
3-2.插入
3-3.查找和删除
3-4.完整代码
4.开散列
5.开散列的模拟实现
5-1.基本结构
5-2.查找
5-3.插入 5-4.删除
5-5.特别的析构
5-6.完整代码
三、哈希的应用
1.哈希表
2.位图
2-1.原理与应用
2-2.模拟实现
3.布隆过滤器
3-1.原理与应用
3-2.模拟实现
补、海量数据问题
1.位图相关
2.布隆过滤器相关
3.哈希切割 一、常见的哈希函数 哈希函数本质是一个数学表达式作用是将数据元素的值或称关键码转换为数据元素在哈希表中的存储位置或称哈希地址最常见的形式是数组下标。 【补】哈希函数设计原则 定义域必须包含所有要存储的数据元素值域当一个哈希表有m个地址的大小时哈希函数的值域必须在0到m-1之间通过哈希函数得到的地址能均匀分布在哈希表中表达式应简洁明了。 1.直接定址法最常用 直接定址法的表达式为 HashKey A*Key B 其中key为数据元素的值 A和B为两个未知数它们的值视具体情景而定。表达式的结果即为数据元素的存储位置。 直接定址法的表达式十分简洁结果地址分布较为均匀但使用前需确定数据元素值的分布情况适用于数据量小且数据值连续分布值的分布范围集中的情景。 最典型的情景多与字符有关因为字符的分布范围就是连续集中的。 例如用一个大小为26的int类型的数组character来存26个英文小写字母要使character[0]acharacter[1]b...只需将小写字母的ASCII码值a对应97b对应98通过 表达式“1 * ASCII码值 - 97 数组下标”“1 * 97 - 97 0”“1 * 98 - 97 1”求得字符a、字符b...在数组中的下标并存入数组即可。 又例如这道题目“字符串中第一个不重复的字符”在一个字符串中找到它第一个不重复的字符并返回它的下标——
class Solution {
public:int firstUniqChar(string s) {unordered_mapint, int frequency; //unordered_map相当于是map的不排序但去重版本同样存的是key, value//这里的key代表字母的ASCII码value代表出现次数for (char ch: s) {frequency[ch]; //将字符的出现次数统计在unordered_map中}for (int i 0; i s.size(); i) { //将字符从前往后挨个在unordered_map查询就能找到第一个不重复的字符if (frequency[s[i]] 1) { //不重复的字符的出现次数为1return i; }}return -1; //没有找到则返回-1}
};//来源力扣官方题解2.除留余数法最常用 除留余数法的表达式为 Hash(key) key % p (pm) 其中key为数据元素的值m为哈希表的大小元素个数p是一个不大于m或等于m的质数。表达式的结果即为数据元素的存储位置。 除留余数法适用于值的分布范围分散的情景。 例如要将一个数据集合{176459}存入一个大小为10的int类型的数组中已知m10取p10则通过等式“数值 % 10 下标”可以求得每个数据在数组中的下标。 3.平方取中法 平方取中法适用于数据元素值的分布不明确但值本身不是特别大的情景一般取值平方的中间n位作为数据元素的存储位置。 例如一个数据元素的值为1234值的平方为1522756取值平方的中间3位“227”就是它的地址。又例如一个数据元素的值为4321值的平方为18671041取值平方的中间3位“671(或710)”就是它的地址。 4.折叠法 折叠法适合数据元素值的分布不明确但值本身特别大位数较多的情景。它是将数据元素的值从左到右分割成位数相等的几部分(一般最后一部分位数可以稍短)然后将这几部分叠加求和并按哈希表的大小取后n位作为数据元素的存储位置。 例如一个数据元素的值为123456取每3位为一组将值分割为123和459再将它们叠加求和求得579取最后一位9作为数据元素的存储位置。 5.随机数法 随机数法适用于数据元素值的长度不相等的情景。取一个随机数函数将数据元素值通过随机数函数求得的结果作为它的存储位置通式为Hash(key) random(key)其中random即为随机数函数。 6.数学分析法 数学分析法适用于数据元素的值特别大位数较多且位数本身分布均匀、重复较少的情景。 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各个位上出现的频率不一定 相同每种符号出现的机会均等在某些位上分布比较均匀在某些位上分布不均匀但只有某几种符号经常出现。可根据哈希表的大小选择其中各种符号分布均匀的若干位作为数据元素的存储位置。 例如要存储某家公司员工登记表将手机号作为数据元素选择手机号后四位作为存储位置。 二、哈希冲突与解决方法 1.哈希冲突 例如在除留余数法的案例中要将一个数据集合{176459}存入一个大小为10的int类型的数组中每一个数据都恰好有自己独立的存储位置。 若此时再按除留余数法向数组中放入数据44则数据44的存储位置为下标4。但下标4的位置先前已经被数据4占用了称数据44的存储位置与数据4发生了冲突数据44不能再放在下标4的位置上了。 不同的数据元素值通过哈希函数映射到了相同的存储位置这一现象被称为哈希冲突。 发生哈希冲突的原因之一可能是哈希函数设计得不够合理。 哈希函数设计得越精妙发生哈希冲突的概率就越低。但无论如何防备哈希冲突都是无法完全避免的只能通过一些特殊的方式来解决。 一般来说闭散列和开散列是解决哈希冲突最常用的两种方法。 2.闭散列 闭散列又称开放定址法。当哈希冲突发生时若哈希表未被装满就把数据元素按规则存放到冲突位置中的“下一个” 空位置去其实就是占用别的数据元素的位置这样做的缺陷是空间利用率往往较低但这也是哈希的缺陷本质上是在以空间换时间。 而寻找下一个空位置的方法主要有线性探测和二次探测两种。
2-1.线性探测 从冲突位置开始依次向后探测直到寻找到下一个空位置为止。 2-2.二次探测 二次探测是基于线性探测的改良。 线性探测存在的缺陷是当某一个冲突位置上堆积了许多数据元素那么线性探测的次数就可能会非常之多。二次探测是将每次向后探测的位置由“1234”这样的线性变化变成“14916”这样的非线性变化使得每次产生哈希冲突后下一个空位分部散乱再冲突的可能性降低。 3.闭散列的模拟实现
3-1.基本结构
#includevectornamespace open_address
{enum STATE //枚举体定义存储位置的状态{EXIST, //存在EMPTY, //为空即不存在标记这个位置为可覆盖的DELETE //被删除标记这个位置为可覆盖的};templateclass K, class Vstruct HashData //数据元素{pairK, V _kv; //数据元素的值STATE _state EMPTY; //存储位置的状态引入状态来更好地管理这个数据元素};templateclass K, class Vclass HashTable{public:HashTable() { _table.resize(10); }//构造函数bool Insert(const pairK, V kv); //插入HashDataconst K, V* Find(const K kv); //查找bool Erase(const K key); //删除private:vectorHashDataK, V _table;//哈希表size_t _n 0; //存储有效数据个数存放新数据可能涉及扩容故定义_n};}
3-2.插入 向哈希表插入一个新的数据元素既要找到合适的插入位置又要留意哈希表的容量是否充足不足则应扩容后再插入。 为了判断哈希表的容量是否充足前人引入了载荷因子的概念 【Tips】载荷因子 vs 冲突发生的概率 vs 空间利用率 载荷因子越大冲突发生的概率越大空间利用率越高 载荷因子越小冲突发生的概率越小空间利用率越低 。 ps哈希表不能等空间全满才扩容也无法等到空间全满才扩容而是载荷因子到一定值就扩容。下取载荷因子为0.7。 //这是两个仿函数
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key; //将const K类型的变量转换成整型变量}
};
template
struct DefaultHashFuncstring //这个仿函数是对专门的类型string的特化
{size_t operator()(const string str){// BKDR字符串哈希函数//Q如何将字符串转化为整型来取模//A将字符串的每个字符的ASCII码值相加//Q每个字符相加的ASCII码值相同怎么办例如bacd、abcd、abbe等//A利用BKDR每个字符相加前将和*131后再加字符的ASCII码值解决冲突size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};
namespace open_address
{//...templateclass K,class V, class HashFunc DefaultHashFuncKclass HashTable{//...bool Insert(const pairK, V kv){//step1.检查扩容//if((double)_n/_table.size()0.7)if (_n * 10 / _table.size() 7) //有效数据个数/表的当前长度载荷因子则需对表扩容{//开辟一个新哈希表size_t newSize _table.size() * 2; //粗略扩容为旧表长度的2倍HashTableK, V newHT;newHT._table.resize(newSize);//遍历旧表将其重新映射到新表for (size_t i 0; i _table.size(); i){if (_table[i].state EXIST){newHT.Insert(_table[i]._kv);}}//然后将新表赋给旧表交换会产生一个随用随弃临时变量以达到新表赋给旧表的效果_table.swap(newHT._table); }//step2.线性探测寻找合适的存放位置HashFunc hf; //仿函数对象size_t hashi hf(kv.first) % _table.size(); //按除留余数法找到一个哈希地址//ps//1.const K类型的变量本身是无法取模的通过仿函数转换为整型后便可取模//2. 模capacity()空间容量会有访问越界的隐患因为_n之后的空间其实是无法访问的。故模.size()有效数据个数while (_table[hashi]._state EXIST) //这个位置存在数据元素说明这是一共冲突位置{//那就继续往后寻找合适的哈希地址hashi; hashi % _table.size();//这里再取模是为了让存放位置始终在哈希表内}//找到后将数据元素放在合适的哈希地址_table[hashi]._kv kv; //放值_table[hashi]._state EXIST; //改状态为存在//放完后增加表的有效数据个数_n;return true;}//...};
};
3-3.查找和删除 //两个仿函数
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key; //将const K类型的变量转换成整型变量}
};
template
struct DefaultHashFuncstring
{size_t operator()(const string str){// BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};
namespace open_address
{//...templateclass K,class V, class HashFunc DefaultHashFuncKclass HashTable{//...//查找HashDataconst K, V* Find(const K kv){//线性探测HashFunc hf; //仿函数对象size_t hashi hf(kv) % _table.size();//const K类型的变量本身是无法取模的通过仿函数转换为整型后便可取模while (_table[hashi]._state ! EMPTY) //找到空的位置为止{if (_table[hashi]._state EXIST //这个位置存在 _table[hashi]._kv.first kv) //数据的值也符合条件{return (HashDataconst K, V*) _table[hashi]; //就说明找到了}//没找到就继续往后找hashi;hashi % _table.size();}return nullptr;}//删除bool Erase(const K key){HashDataconst K, V* ret Find(); //找到要删除的数据if (ret){ret-_state DELETE; //标记位置为“被删除”--_n; //有效数据个数-1return true;}return false;}//...};
};
3-4.完整代码
#includevectortemplateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};
template
struct DefaultHashFuncstring
{size_t operator()(const string str){// BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace open_address
{enum STATE{EXIST,EMPTY,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;STATE _state EMPTY;};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pairK, V kv){if (_n * 10 / _table.size() 7){size_t newSize _table.size() * 2;/*vectorHashData newtable;newtable.resize(newSize);*/HashTableK, V newHT;newHT._table.resize(newSize);for (size_t i 0; i _table.size(); i){if (_table[i].state EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}HashFunc hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._state EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}HashDataconst K, V* Find(const K kv){if (Find(kv.first)){return false;}HashFunc hf;size_t hashi hf(kv) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first kv){return (HashDataconst K, V*) _table[hashi];}hashi;hashi % _table.size();}return nullptr;}bool Erase(const K key){HashDataconst K, V* ret Find();if (ret){ret-_state DELETE;--_n;return true;}return false;}private:vectorHashDataK, V _table;size_t _n;};} 4.开散列 开散列又称为链地址法、拉链法或哈希桶从逻辑结构上看像是将一个个链表挂在了一个线性表上。 数据元素通过哈希函数可能得到相同的存储位置从而引发冲突。闭散列将存储位置相同的数据元素归于一个个称为“桶”的子集每一个“桶”中的数据元素通过一个单链表链接起来然后将“桶”链表的头节点存储在哈希表中。 闭散列处理冲突需要增设链接指针似乎增加了存储的负担。但事实上闭散列要求必须保持大量的空闲空间来确保搜索效率哈希表的每一项所占空间其实比开散列要求的指针大得多所以开散列反而比闭散列节省空间资源。 不过这并不能说明开散列就是完美无缺的。当线性表上挂着的某一条链表太长也就是说线性表的某一个下标位置映射的数据太多也会使搜索效率低下。有一种方案十分巧妙如果某一个下标位置映射的数据太多就把这些数据打包成一棵红黑树挂起来。 5.开散列的模拟实现 5-1.基本结构
#includevector
namespace hash_bucket
{ //“桶”链表节点templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}};//哈希表哈希桶templateclass K, class Vclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_table.resize(10, nullptr);}private:vectorNode* _table; // 为了动态地管理数据哈希表用指针数组来存“桶”链表size_t _n 0; // 有效数据个数};
} 5-2.查找
//这是两个仿函数
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring //特化
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;//...};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, V Node;public://...//查找Node* Find(const K key){HashFunc hf; //仿函数对象//除留余数法寻找数据的哈希地址size_t hashi hf(key) % _table.size();//找到后在相应链表中寻找目标数据Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}//...};
} 5-3.插入 向哈希表插入一个新的数据元素首先要找到合适的插入位置也要留意哈希表的容量是否充足不足则应扩容后再插入而对于哈希桶而言通过头插的方式来链接新的数据元素更为简便。 如果不扩容那么“桶”的个数就是固定的。随着数据元素的不断插入每个桶中的元素个数会不断增多可能会导致某一个桶中的链表偏长从而影响哈希表的搜索性能。因此在一定条件下需要对哈希表进行扩容。 对于是否扩容的判断与闭散列类似引入了载荷因子。但与闭散列不同的是开散列的载荷因子设为了1。不扩容不断插入会使某些“桶”越来越长让哈希表的搜索性能得不到保障因此载荷因子应适当大一些一般控制在1即在元素个数恰好等于表长/“桶”的个数时给哈希表扩容使哈希表在理想情况下平均每一个“桶”中都有一个数据元素。
//这是两个仿函数
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring //特化
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;//...};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, V Node;public://...//插入bool Insert(const pairK, V kv){//待插入数据在表中已经存在就不需要插入了if(Find(kv.first)){return false;}//扩容HashFunc hf; //仿函数对象if (_n _table.size()) //载荷因子到1就扩容{ //开一个新哈希表size_t newSize _table.size()*2;//此处默认扩容2倍vectorNode* newTable; newTable.resize(newSize, nullptr);//遍历旧表将节点指针逐个迁到新表中for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next; //暂存一下cur的下一个节点//除留余数法确定新的哈希地址size_t hashi hf(cur-_kv.first) % newSize; // 将旧表桶中的数据在旧的哈希地址下头插到新表的桶中在新的哈希地址下cur-_next newTable[hashi];//旧表数据的next指针指向新表中桶的头节点newTable[hashi] cur; //将刚头插的节点置为新表中桶的头节点指针cur next; //向后移动处理下一个数据}_table[i] nullptr; //别忘了每次要将旧表的桶置空以防内存泄漏}//然后交换新表和旧表以达到新替旧_table.swap(newTable);}//插入size_t hashi hf(kv.first) % _table.size(); //用除留余数法找哈希地址// 找到后将待插入元素头插在“桶”链表中Node* newnode new Node(kv);newnode-_next _table[hashi];// 然后将头插的新节点置为哈希表中所存的链表的头节点指针_table[hashi] newnode;_n;return true;}//...};
} 5-4.删除
//这是两个仿函数
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring //特化
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;//...};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, V Node;public://...//删除bool Erase(const K key){HashFunc hf; //仿函数对象//除留余数法确定数据在表中的哈希地址size_t hashi hf(key) % _table.size();//确定后在相应链表中寻找要删除的数据Node* prev nullptr; //前驱节点Node* cur _table[hashi];//目标节点while (cur){ //找到了if (cur-_kv.first key){ if (prev nullptr) //是链表的第一个头节点就把第二个节点置为新的头节点{_table[hashi] cur-_next;}else //一般情况就将cur的前后链接以断开cur{prev-_next cur-_next;}delete cur; //维护完链表结构释放cur return true;}//没找到就继续往后找prev cur;cur cur-_next;}return false;//找遍了链表也没找到删除失败}//...};
} 5-5.特别的析构 因为每个插入的新节点都是通过new开辟的所以在HashTable对象析构时它们需在析构函数中手动释放。
//...namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_table.resize(10, nullptr);}//析构~HashTable(){//将桶链表逐个节点地释放释放完将桶置空for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}//...private:vectorNode* _table;size_t _n 0; };
} 5-6.完整代码
#includevector
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};
template
struct DefaultHashFuncstring
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_table.resize(10, nullptr);}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}bool Insert(const pairK, V kv){if(Find(kv.first)){return false;}HashFunc hf;if (_n _table.size()){size_t newSize _table.size()*2;vectorNode* newTable;newTable.resize(newSize, nullptr);for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi hf(cur-_kv.first) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kv.first) % _table.size();Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* Find(const K key){HashFunc hf;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){HashFunc hf;size_t hashi hf(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur; return true;}prev cur;cur cur-_next;}return false;}private:vectorNode* _table; size_t _n 0; };
}
三、哈希的应用 1.哈希表 哈希表是一种能够表示“数据元素-存储位置”这种映射关系的数据结构理论上任何具有这种映射关系的数据结构都可以当作哈希表来使用。而它们除了可以用于快速查找也可以用于统计数目。 常见的例如一个整型数组当中的元素和元素下标具有一定映射关系可以用于统计某一个英文字符的出现次数如上文中直接定址法中的例子在这道算法题判定是否互为字符重排
的题目答案中大小为26的整型数组hash也被用于统计某一个英文字符的出现次数。
//题目答案
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!s2.size())return false;int hash[26]{0};for(auto ch:s1)hash[ch-a];for(auto ch:s2){hash[ch-a]--;if(hash[ch-a]0)return false;}return true;}
};
另外一个整型数组也可以用于实现计数排序详见【数据结构】八种常见排序算法。 又例如容器map其对存储的key,value键值对进行排序和去重使其可以支持类似英汉词典的功能。 又例如以哈希桶作为底层的容器unordered_set该容器详解见【C】Unordered_map Unordered_set在这道算法题存在重复元素的题目答案中被用于统计数字出现的次数。
//题目答案
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_setint hash;for(auto x:nums){if(hash.count(x))return true;else hash.insert(x);}return false;}
}; 2.位图
2-1.原理与应用 快速查找一个数据是十分常见的数据管理操作但当数据量十分庞大例如要在40亿个无序且不重复的无符号整数中快速判断某一个无符号整数是否存在此时又该如何处理保证查找的效率呢 不难想到直接遍历这40亿个数来查找效率是极低的如果考虑使用哈希表将40亿个数存储在一张哈希表中每个数占4个字节的空间40亿个数就占了160亿字节大约16GB的空间对系统内存的消耗是极大的一般的电脑很难承受如果考虑使用搜索树例如红黑树同样的光存储数据就对系统内存就有极大消耗更别提构建搜索树本身又附带消耗而如果将数据全都存在磁盘上进行外排序和二分查找空间问题解决了但时间又很缓慢效率低下。 其实只判断某一个数“在不在”未必先要将这40亿个数全部存起来。“在”或“不在”可以简单地看作“1”或“0”而一个二进制数都是由“1”或“0”组成的由此不难联想到一个二进制数的每一位都与这个二进制数的值有关也相当于是某一个值“在”或“不在”的标识例如二进制数要转化为十进制数它的第一位与2^0有关第二位与2^1有关。我们可以仿照这一点来快速查找一个无符号整数。 无符号整数的数据范围是0到2^32-1。那么我们可以通过2^32个比特位大小的数组大约512MB也就是0.5G然后将40亿个无符号整数通过直接地址法映射到对应的下标位置将无符号整数的值当作下标且第几号下标也与第几个比特位有关以此来判断其中某一个无符号整数在不在。 尽管比特位无法作为数组的类型但我们可以将整型作为数组的类型并将每一个有32个比特位的整型当作一个组来管理比特位。数组的0号下标存放第一组整型管理的是第0个到第31个比特位数组的1号下标存放第二组整型管理的是第32个到第63个比特位......以此类推。要查询某一个数据的“在”或“不在”的状态只需确定它映射在数组中的哪一个比特位上要确定它映射在数组中的哪一个比特位上只需先确定它映射在第几组整型即它对应的数组下标是几号再确定它映射在这组整型的第几个比特位上即可。 像这样的一个数组——涉及位操作数组下标与某一个数据有映射关系一般是直接定址法、与第几个比特位有关数组元素仅为1和0、用于表示这个数据“在”或“不在”的状态——就是位图。 位图常见的应用情景有1)快速查找某个数据是否在一个集合中2)排序 去重3)求两个集合的交集、并集4)操作系统中磁盘块标记......等等。 C库中提供了一个容器bitset它就是位图常见的操作有访问、计数、查询、修改等。 2-2.模拟实现
namespace CVE
{templatesize_t N //指定位图的大小bitset bt;),N是比特位的数量class bitset{public://构造函数为整型数组申请空间bitset(){_a.resize(N / 32 1); //N/32得到整型的数量1多申请一个整型以防越界访问虽然有空间浪费}// 把x映射的比特位标记成1void set(size_t x){size_t i x / 32; //先确定x映射在第几组整型即x对应的数组下标是几号size_t j x % 32; //再确定x映射在这组整型的第几个比特位上_a[i] | (1 j); //把x映射的比特位标记成1}// 把x映射的比特位标记成0void reset(size_t x){size_t i x / 32; //先确定x映射在第几组整型即x对应的数组下标是几号size_t j x % 32; //再确定x在这组整型的第几个比特位上_a[i] (~(1 j)); //把x映射的比特位标记成0}// 检验x是否在位图中bool test(size_t x){size_t i x / 32; //先确定x映射在第几组整型即x对应的数组下标是几号size_t j x % 32; //再确定x映射在这组整型的第几个比特位上return _a[i] (1 j); //检验x是否在位图中} private:vectorint _a; //整型数组};
} 3.布隆过滤器
3-1.原理与应用 1970年Burton Howard Bloom提出了一种紧凑型的、比较巧妙的概率型数据结构它被称为布隆过滤器。它的特点是可以高效地插入和查询可以告知用户 “某样东西一定不存在或者可能存在”。它通过多个哈希函数将一个数据映射到位图中此种方式不仅可以提升查询效率也可以节省大量的内存空间。 面对海量数据尽管位图有十分出色的表现但是它仍然存在局限就是它只能映射整型的数据而无法处理浮点型、字符串。要解决这个问题可以仿照上文中闭散列、开散列处理字符串映射的方式先将浮点型、字符串转换成整型再映射。而这就是布隆过滤器的大致原理。 位图映射的是整型一个值映射一个位置。但字符串的组合无穷之多冲突的几率很大所以布隆过滤器采取了“一个值映射多个位置”的方式以此来降低冲突的几率。 但布隆过滤器仍存在误判的可能。检验一个字符串是否存在于某个集合先要将这个字符串通过多个哈希函数转换成的多个数组下标然后再检验这些下标位置上的值。只有这些下标位置都存的是“1”才说明这个字符串是存在的如果其中一个下标是“0”就说明这个字符串不存在。而万一别的字符串也映射过这些下标那下标位置上存的就可能都是“1”了。 所以布隆过滤器判断“一个字符串存在”是可能失误的但判断“一个字符串不存在”却是始终准确的。 它的应用情景例如在新用户注册时快速判断一个昵称是否被注册过。在不追求精确的时候布隆过滤器可以直接告诉用户昵称可不可以用。 在追求精确的时候布隆过滤器可以过滤掉“不在”的昵称剩下“在”的昵称可以进一步到数据库中查验。 如果一个数据被布隆过滤器判断为是不存在就可以直接告诉用户昵称不可用要重新想一个昵称如果被判断为是存在的再去数据库中查验。这样既保证了判断的准确性又可以节省了部分去数据库查找的开销因为数据库在磁盘上数据读取效率较低频繁调度开销较大。 3-2.模拟实现
关于各种字符串哈希函数的详解见字符串哈希算法关于哈希函数个数、布隆过滤器长度与误判率之间的关系见详解布隆过滤器的原理使用场景和注意事项
#includestring
#includevectornamespace CVE
{//位图templatesize_t Nclass 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:vectorint _a;};//以下是三个仿函数//字符串哈希函数1 - BKDR
struct BKDRHash
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash hash * 131 ch;}return hash;}
};//字符串哈希函数2 - AP
struct APHash
{size_t operator()(const string str){size_t hash 0;for (size_t i 0; i str.size(); i){size_t ch str[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}
};//字符串哈希函数3 - DJB
struct DJBHash
{size_t operator()(const string str){size_t hash 5381;for(auto ch : str){hash (hash 5) ch;}return hash;}
};//布隆过滤器
templatesize_t N, class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash
class BloomFilter
{
public://将key映射的多个比特位标记为1void Set(const K key){//先取映射的下标再调用位图的接口去标记size_t hash1 Hash1()(key) % N; //Hash1()是一个匿名的仿函数对象以下同理_bs.set(hash1);size_t hash2 Hash2()(key) % N;_bs.set(hash2);size_t hash3 Hash3()(key) % N;_bs.set(hash3);}//检验key是否存在bool Test(const K key){//三个映射的比特位但凡有一个存的是0就说明key不存在size_t hash1 Hash1()(key) % N;if (_bs.test(hash1) false)return false;size_t hash2 Hash2()(key) % N;if (_bs.test(hash2) false)return false;size_t hash3 Hash3()(key) % N;if (_bs.test(hash3) false)return false;//三个映射的比特位放的都是1才说明key可能存在return true; }private:bitsetN _bs; //基于位图实现
};} ps因为删除一个值的标记可能影响其他值所以布隆过滤器一般不支持删除。 补、海量数据问题
1.位图相关 问题1给定100亿个整数请设计算法找到只出现一次的整数。 解法1用两个比特位来标记00表示数不存在01表示数出现一次10表示数出现2次。 解法2优化解法1通过两个位图来查找。只出现一次的整数在两个位图中相应比特位上为一个为“0”、另一个为“1”这样只需找到“0”、“1”组合的比特位。 #includevectornamespace CVE
{//位图templatesize_t Nclass 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:vectorint _a;};//双位图templatesize_t Nclass twobitset{public:// 把x映射的比特位标记成1void set(size_t x){// x不存在位图1中为0位图2中也为0即为00改00为01if (!_bs1.test(x) !_bs2.test(x)){_bs2.set(x); //将位图2中的比特位标记为1} // x存在一次位图1中为0位图2中为1即为01改01为10else if (!_bs1.test(x) _bs2.test(x)){_bs1.set(x); //将位图1中的比特位标记为1_bs2.reset(x); //将位图2中的比特位标记为0}}// 检验x是否只出现一次bool is_once(size_t x){return !_bs1.test(x) _bs2.test(x); //x存在一次位图1中为0位图2中为1即为01}private:bitsetN _bs1; //位图1bitsetN _bs2; //位图2};
} 双位图代码的测试结果 问题2给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件的交集 解法将两个文件的数据分别映射到两个位图对应位置都为1那这个位置映射的数据就是交集之一。将两个位图的对应位置与运算一下得出的结果去重后就得到两个文件的交集。 #includevectornamespace CVE
{//位图templatesize_t Nclass 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:vectorint _a;};
} 位图代码的测试结果 问题3某1个文件有100亿个int我们只有1G内存请设计算法找到出现次数不超过2次的所有整数。 解法类似问题1通过两个位图来查找。00表示数不存在01表示数出现一次10表示数出现2次11表示数出现2次以上。 #includevectornamespace CVE
{//位图templatesize_t Nclass 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:vectorint _a;};//双位图templatesize_t Nclass twobitset{public:void set(size_t x){// x原先不存在00-01if (!_bs1.test(x) !_bs2.test(x)){_bs2.set(x); } // x原先存在一次01-10else if (!_bs1.test(x) _bs2.test(x)){_bs1.set(x); _bs2.reset(x); }// x原先存在两次10-11else if (_bs1.test(x) !_bs2.test(x)){_bs2.set(x); }}bool not_more_than_twice(size_t x){return !(_bs1.test(x) _bs2.test(x)); }private:bitsetN _bs1; //位图1bitsetN _bs2; //位图2};
} 双位图代码的测试结果 2.布隆过滤器相关 问题1如何扩展布隆过滤器使得它支持删除元素的操作 解法多个比特位标记一个值并使用引用计数。将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。 问题2给定两个文件分别有100亿个query数据库的查询语句可以理解为字符串我们只有1G内存如何找到两个文件交集分别给出近似算法。 解法通过一个布隆过滤器。将一个文件的数据存入布隆过滤器中再检查相应的数据在另一个文件中在不在在的就是交集。 3.哈希切割 哈希切割把字符串转为整型然后对一个范围取模以此把一个庞大的数据集合分为一个一个小份方便处理。 问题1给定两个文件分别有100亿个query数据库的查询语句可以理解为字符串。100亿个query大约占300G我们只有1G内存如何找到两个文件交集分别给出精确算法。 解法通过哈希切割把两个约300G的大文件分成一个一个小份并给每个小份编号然后把编号相同的两个小份放入1G内存去找交集。因为映射的缘故两个大文件中相同的query一定会分别进入编号相同的小份中。 问题2给定一个超过100G大小的log file, log中存着IP地址, 如何找到出现次数最多的IP地址如何找到topK个IP 解法哈希切割。先将IP地址映射然后切分成一个一个小份并依次处理相同的IP一定进入了同一个小份此时用map去分别统计每个小份中IP地址出现的次数即可。要找到topK个IP只需汇总每个小份中每个IP出现的次数最后用priority_queue即可获取TopK。
