网站建设需求调查表,代理记账公司排名前十强,如何进行简单的网页设计,北京办公室装修目录
常见哈希函数
位图
位图扩展题
位图的应用 常见哈希函数 1. 直接定址法--(常用)
这种方法不存在哈希冲突 取关键字的某个线性函数为散列地址#xff1a;Hash#xff08;Key#xff09; A*Key B 优点#xff1a;简单、均匀 缺点#xff1a;需要事先知道关键字的…
目录
常见哈希函数
位图
位图扩展题
位图的应用 常见哈希函数 1. 直接定址法--(常用)
这种方法不存在哈希冲突 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 面试题字符串中第一个只出现一次字符
只出现一次的字符串 2. 除留余数法--(常用)
存在哈希冲突重点解决哈希冲突 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址 3. 平方取中法--(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况 4. 折叠法--(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这 几部分叠加求和并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 5. 随机数法--(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中 random为随机数函数。 通常应用于关键字长度不等时采用此法 6. 数学分析法--(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定 相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散 列地址。
位图 面试题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】
这里用搜索树和哈希表都不行搜索树还有leftrightcolour有额外空间哈希表有next指针消耗这俩种方式都会消耗空间导致内存中存不下
排序二分查找 同样数据太大只能放在磁盘上磁盘上不好支持二分查找 1. 遍历时间复杂度O(N) 2. 排序(O(NlogN))利用二分查找: logN 3. 位图解决 数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一 个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0 代表不存在。比如 所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用 来判断某个数据存不存在的。 用位图的方式这里大概占用512MB 按位开空间不好开我们按char开空间一个char占一个字节一个字节是8个比特位 标记为1的方法把1进行左移或右移之后进行按位或 reset和set相反reset//计算出来位置后把那个位置标记为0其它位标记为1 test判断x在不在这一位和1相与判断在不在 templatesize_t N//N个比特位,class bitset{public:bitset():{_bits.resize(N / 81, 0);//如果N对8能整除就N/8不能对8整除就1多开一个字节这种浪费比较少可忽略}void set(size_t x)//计算在第几个char的第几个位如2020/82在第二个char20%84第四个比特位{size_t i x / 8;size_t j x % 8;//计算出来位置后把那个位置标记为1_bits[i] | (1 j);}void reset(size_t x)//让这位变为0其它位是1{size_t i x / 8;size_t j x % 8;//计算出来位置后把那个位置标记为0其它位标记为1_bits[i] ~(1 j);}bool test(size_t x)//判断x在不在{size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;}; 走到8的时候第二个char显示16进制的1说明8是第二个char的第一个比特位是全体的第8个比特位 第9位是3说明是第二个char的第二个比特位因为要和前面8所表示的1加起来 上面40亿的数据进行位图计算此时会溢出-1是无符号的-1 改为这种写法就不会报错 大概占用是512MB 当执行完之后内存被释放这是因为这里是vector有自己的析构不需要我们写 位图扩展题 1. 给定100亿个整数设计算法找到只出现一次的整数
kv的统计次数搜索模型我们使用位图俩个比特位表示一个值大概需要一个G 我们依靠上面的代码搞俩个位图俩个位图相对应的位置表示一个值出现次数 templatesize_t N//N个比特位,class bitset{public:bitset():{_bits.resize(N / 81, 0);//如果N对8能整除就N/8不能对8整除就1多开一个字节这种浪费比较少可忽略}void set(size_t x)//计算在第几个char的第几个位如2020/82在第二个char20%84第四个比特位{size_t i x / 8;size_t j x % 8;//计算出来位置后把那个位置标记为1_bits[i] | (1 j);}void reset(size_t x)//让这位变为0其它位是1{size_t i x / 8;size_t j x % 8;//计算出来位置后把那个位置标记为0其它位标记为1_bits[i] ~(1 j);}bool test(size_t x)//判断x在不在{size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;};templatesize_t Nclass twobitset{public:void set(size_t x){bool inSet1 _b1s1.test(x);bool inSet2 _b1s2.test(x);if (inset1 falseinset2false)//如果之前x不存在我们此时传参传的是xset就由00-01{//00-01_bs2.set(x);}else if (inset1 false inset2 true)//如果之前x是01我们此时传参传的是xset就由01-10{//01-10_bs1.set(x);_bs2.reset(x);}//如果之前x是10我们就不用管了}private:bitsetN _bs1;bitsetN _bs2;};
} 测序程序这里只打印了出现一次的数据。
void test_bit_set3()
{int a[] { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };myspace::twobitset100 bs;for (auto e : a){bs.set(e);}bs.print_once_num();
}
} 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 找交集使用俩个位图第一个集合对应第一个位图第二个集合对应第二个位图如果既在位图1又在位图2则是交集或者俩个位图进行与映射位都是1的就是交集 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 这里需要四种状态000次011次102次113次及以上 位图缺点只能处理整数 位图的优点快节省空间
位图的应用 1. 快速查找某个数据是否在一个集合中 2. 排序 去重 3. 求两个集合的交集、并集等 4. 操作系统中磁盘块标记
