👉哈希函数👈
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数的设计原则
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
常见哈希函数
直接定址法（常用）
取关键字的某个线性函数为散列地址：Hash(Key) = A * Key + B
优点：简单、均匀且不存在哈希冲突
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
面试题：字符串中第一个只出现一次字符
除留余数法（常用）
设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p <= m)，将关键码转换成哈希地址。除留余数法存在哈希冲突，重点解决哈希冲突。
平方取中法（了解）
假设关键字为 1234，对它平方就是 1522756，抽取中间的 3 位 227 作为哈希地址；再比如关键字为 4321，对它平方就是 18671041，抽取中间的 3 位 671 (或710)作为哈希地址。平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况，只适用于整数。
5. 随机数法（了解）
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key)，其中 random 为随机数函数。通常应用于关键字长度不等时采用此法。
6. 数学分析法（了解）
设有 n 个 d 位数，每一位可能有 r 种不同的符号，这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前 7 位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如 1234 改成 4321 )、右环位移(如 1234 改成 4123 )、左环移位、前两数与后两数叠加(如 1234 改成 12+34=46 )等方法。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
👉位图👈
位图概念
面试题
给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。
遍历，时间复杂度O(N)
排序(O(NlogN))，利用二分查找: logN
位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态。那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为 1，代表存在，为 0代表不存在。比如：
2. 位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。注意：位图所开空间要大于或等于整型的范围，因为有可能有些数字数，有些数字小。
位图的实现
位图最核心的三个节点是set、reset和test，set是将 x 对应的比特位设置为 1，reset是将 x 对应的比特位设置为 0，test是查看 x 在不在。
#pragma once namespace Joy { template<size_t N> class bitset { public: bitset() { _bits.resize(N / 8 + 1, 0); // 多开一个字节,防止越界 } // 将比特位设置为1 void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); } // 将比特位设置为0 void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); } // 查x在不在 bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return (_bits[i] & (1 << j)); } private: vector<char> _bits; }; void BitSetTest() { bitset<100> bs; bs.set(8); bs.set(9); bs.set(20); cout << bs.test(8) << endl; cout << bs.test(9) << endl; cout << bs.test(20) << endl; bs.reset(8); bs.reset(9); bs.reset(20); cout << bs.test(8) << endl; cout << bs.test(9) << endl; cout << bs.test(20) << endl; } void BitSetTest2() { // 开出42亿9千万个比特位 bitset<-1> bs1; bitset<0xffffffff> bs2; } }
位图的应用
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
题目一：给定 100 亿个整数，设计算法找到只出现一次的整数？ 这种题目是 KV 的统计次数搜索模型，一个数字出现次数有三种情况：出现零次、出现一次以及出现两次及以上，这三种情况只需要用两个比特位就可以表示。
template <size_t N> class twobitset { public: void set(size_t x) { bool inset1 = _bs1.test(x); bool inset2 = _bs2.test(x); // 00 if(inset1 == false && inset2 == false) { // -> 01 _bs2.set(x); } else if (inset1 == false && inset2 == true) // 01 { // -> 10 _bs1.set(x); _bs2.reset(x); } else if (inset1 == true && inset2 == false) { // -> 11 _bs2.set(x); } // else是x出现三次及三次以上 } void print_once_num() { for (size_t i = 0; i < N; ++i) { if (_bs1.test(i) == false && _bs2.test(i) == true) cout << i << " "; } cout << endl; } private: bitset<N> _bs1; bitset<N> _bs2; }; void BitSetTest3() { 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 }; twobitset<100> bs; for (auto e : a) { bs.set(e); } bs.print_once_num(); }
