广州网站建设建设,企业宣传片文案高级,一键急速安装wordpress,作文网课题目描述 餐前小菜#xff1a;
在讨论本题目之前先看一个简单的问题#xff1a;给出 NNN 个正整数 (a1,a2,...,an)(a_1,a_2,...,a_n)(a1,a2,...,an)#xff0c;再给出 MMM 个正整数 (x1,x2,...,xm)(x_1,x_2,...,x_m)(x1,x2,...,xm)#xff0c;问这 MMM 个数中…题目描述 餐前小菜
在讨论本题目之前先看一个简单的问题给出 NNN 个正整数 (a1,a2,...,an)(a_1,a_2,...,a_n)(a1,a2,...,an)再给出 MMM 个正整数 (x1,x2,...,xm)(x_1,x_2,...,x_m)(x1,x2,...,xm)问这 MMM 个数中的每个数是否在 NNN 个数中出现过其中 N,M≤105N,M ≤ 10^5N,M≤105且所有正整数均不超过 10510^5105。比较容易想到的思路是对每个欲查询的数 xix_ixi遍历 NNN 看看是否存在。该算法时间复杂度为 O(NM)O(NM)O(NM)是有很多的优化空间的。 经典思想为用空间换时间设有一个 hashTable[N]其中 hashTable[xix_ixi] true 表示正整数 xix_ixi 在 NNN 个正整数 (a1,a2,...,an)(a_1,a_2,...,a_n)(a1,a2,...,an) 中找到了与之相等的数若为 false 表示没有出现过。我们该怎么做呢初始时 hashTable 全为 false对读入的 NNN 个数 (a1,a2,...,an)(a_1,a_2,...,a_n)(a1,a2,...,an)进行预处理将 hashTable[aia_iai] 设置为 true接着对 MMM 个欲查正整数直接查看 hashTable[xix_ixi] 为 true/false 来判断出现/没出现过。在许多算法里都用到了这样一种方案把输入的数作为数组下标来进行查询。将查询的时间复杂度降低至 O(1)O(1)O(1)。 分析
但注意本题中我们每个数的范围是 [−109,109][-10^9,10^9][−109,109] 这是没有办法作为数组下标进行查询的因此我们希望能将一些不合适的下标负数或过大转换为我们期望的一个范围内。 因此我们引入哈希散列、hash的思想将元素(element, e)通过一个函数转换为整数使得该整数可以尽量地代表这个元素。该函数称为哈希函数 h()h()h()。即对 eee求 h(e)h(e)h(e)。 看看这道题 −109≤e≤109-10^9≤e≤10^9−109≤e≤109 为整数可以使用哪些常用的哈希函数呢
直接定址法简单常用于映射要求不高的题目 h(e)eh(e)eh(e)e。餐前小菜中对于需要查找的 xix_ixi其实就是使用了该方案有一个隐式的h(xi)xih(x_i)x_ih(xi)xi将要查询的数作为数组下标。平方取中法基本不使用该方法可忽略将 eee 的平方的中间若干位作为 hash 值。除留余数法重要常用h(e)eh(e)eh(e)e modmodmod kkk。通过该哈希函数可以把很大的数转换为一个不超过 kkk 的数这样就可以作为可行的数组下标。这里 TableSize即可 hash 映射的总长度必须大于等于 kkk不然会产生越界当 kkk 是一个素数时h(e)h(e)h(e) 能尽可能覆盖 [0,k)[0,k)[0,k) 范围内的每一个数。这里将 TableSize与 kkk 都设置为相同的素数。但本题远没有这么简单有两点需要注意 ① e 的取值可能为负在人类世界里负数的模有各种各样的计算方法但总归会得到一个在现有规则下“正确的”一个非负数解同理根据高级程序语言的不同计算的方式也不同但结果却不尽相同在C/C中若对负数求模运算会得到一个负的解这显然是与模运算的定义所违背的因此需要对运算结果进行加工ans (e % TableSize TableSize) % TableSize这样不论是正数还是负数都能得到正确的解具体的细节不多做解释可以将它看作是与加减乘除相类似的算法。 ② TableSize 该如何选取呢这是很重要的一点同时也决定了哈希函数与 k 有关的设计。按照上文分析 TableSize 又应该大于等于输入总数 NNN 的质数且根据上文需要大于等于 kkk而 k 应为一个质数我们得到一下关系TableSizek≥NTableSizek≥NTableSizek≥N而 NNN 不是质数因此不使用它我们可以使用比 NNN 大的第一个质数。// 求比 N 大的第一个质数
N 100000
for (int i N; ; i )
{bool flag false;for (int j 2; j * j i; j ){if (i % j 0){flag true;break;}}if (flag){cout i endl;break;}
}_: 100003以我们对求余运算的了解对于两不同的数 e1,e2e_1,e_2e1,e2他们的 hash值可能是相同的当 e1e_1e1 将表中下标为 h(e1)h(e_1)h(e1) 的单元占据时e2e_2e2 便不能再使用这个位置了此时发生了冲突。
为解决冲突将介绍一下三种方法其中第一、二种都计算了新的 hash 值又称为开放寻址法
线性探测法(Linear Probing)当得到 eee 的 hash值h(e)hash值 h(e)hash值h(e) 后观察到 hashTable 中下标为 h(e)h(e)h(e) 的位置已经被其他元素占用那么就检查下个位置 h(e)1h(e)1h(e)1 是否被占用如果没有就使用这个位置如果还是被占用就继续向后检查当检查长度超出 TableSize 时就回到表头继续向后查找知道找到能使用的位置或表中所有位置均被使用过为止。这种做法容易扎堆。同时由于线性探测法有向后检查的特征因此 hashTable 的设置至少要为 N 的 2 倍又根据我们在除留余数法中的分析TableSize 为 200003。而具体实现中用一个极大值(0x3f3f3f3f)(0x3f3f3f3f)(0x3f3f3f3f)来标识一个位置是否被占用如被占用则 hashTable[h(e)]ehashTable[h(e)] ehashTable[h(e)]e否则 hashTable[h(e)]0x3f3f3f3fhashTable[h(e)]0x3f3f3f3fhashTable[h(e)]0x3f3f3f3f。平方探测法(Quadratic probing)在平方探测法中为了尽可能避免扎堆现象当表中 h(e)h(e)h(e) 的位置被占用时将按下面的顺序检查表中的位置h(e)12、h(e)−12、h(e)22、h(e)−22、h(e)32...h(e)1^2、h(e)-1^2、h(e)2^2、h(e)-2^2、h(e)3^2...h(e)12、h(e)−12、h(e)22、h(e)−22、h(e)32...。①如果检查过程中 h(e)i2TableSizeh(e)i^2TableSizeh(e)i2TableSize 时下个位置超出表尾就把 h(e)i2h(e)i^2h(e)i2 对 TableSize 取模②如果检查过程中 h(e)−i20h(e)-i^20h(e)−i20时下个位置超出表头就将((h(e)−i2)modTableSizeTableSize)modTableSize((h(e)-i^2)modTableSizeTableSize)modTableSize((h(e)−i2)modTableSizeTableSize)modTableSize 作为结果如果为避免出现负数的麻烦可以只进行正方向的平方探测。有结论证明如果 eee 在 [0,TableSize][0,TableSize][0,TableSize] 范围内都无法找到位置当 i≥TableSizei≥TableSizei≥TableSize 时也一定无法找到位置。链地址法(拉链法)拉链法不计算新的 hash值而是把所有 h(e)h(e)h(e) 相同的 eee 连接成一条单链表。若 e1,e2e_1,e_2e1,e2 有相同 hash值则可以形成这样一个单链表 可以看到线性探测法比较直观而拉链法操作比较多因此对其进行模拟一下请结合代码理解 代码(C)
线性探测法
#include iostreamusing namespace std;// TS: TableSize
const int TS 200003, null 0x3f3f3f3f;
int hashtable[TS];// 哈希函数输入元素返回哈希值用于初步定位 hashtable
// h(e) 返回的是未经线性探测的位置
int h(int e)
{return (e % TS TS) % TS;
}// find(e) 返回经过线性探测的位置
int find(int e)
{int he h(e);while (hashtable[he] ! null hashtable[he] ! e){he ;if (he TS) he 0;}return he;
}int main()
{int n;cin n;// 初始化时每一位都没有被占用即没有出现过for (int i 0; i TS; i ) hashtable[i] null;while (n --){char op;int e;cin op e;// 找到最终位置后进行插入if (op I) hashtable[find(e)] e;else{// 通过经过线性探测的位置来判断 e 的性质//而不能通过计算一次哈希函数就去hashtable看if (hashtable[find(e)] null) cout No endl;else cout Yes endl;}}
}拉链法
#include iostreamusing namespace std;const int TS 100003;
// TS: TableSize, no: node, ne: next
int hashtable[TS], no[TS], ne[TS], idx;int h(int e)
{// 哈希函数输入元素返回哈希值用于初步定位 hashtablereturn (e % TS TS) % TS;
}void insert(int e)
{int he h(e);no[idx] e;ne[idx] hashtable[he];hashtable[he] idx ;
}int find(int e)
{int he h(e);// 通过 hashtable[he] 可以查询到最后一个被连接到 h(e) 位置的元素// 再顺着该元素往前查看看 e 是否在此链中出现过for (int i hashtable[he]; i ! -1; i ne[i]){// i 实际上为 idxif (no[i] e) return true;}return false;
}int main()
{int n;cin n;// 每个位置的链没有连接元素for (int i 0; i TS; i ) hashtable[i] -1;while (n --){char op;int e;cin op e;if (op I) insert(e);else{if (find(e)) cout Yes endl;else cout No endl;}}
}
