这篇文章上次修改于 483 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(5): 异或哈希

简介

异或哈希主要利用了异或操作的特殊性，再从特殊性出发，解决阻挡特殊性的问题。

异或操作的特殊性

异或操作是对数字的二进制表示按位相加并对2取余，它的运算十分高效，利于计算机的运算。异或运算符合交换律等等。同时有个特性A ^ A = 0.

推论可得当一个数进行偶数次异或运算后，其值为0，当一个数进行奇数次操作后，其结果为自身

问题1：

一个数组中除了一个元素外其他元素都出现了两次(偶数次)，找出这个元素。

题解：

我们就可以采用异或操作的特殊性，一旦异或两次就会变成0，故剩余的数就是所有值异或的结果。同样很好理解，类似于一个bitmap，每个数都占据一个位的空间，如果出现一次就变成1，再出现一次就变成0。最后的运算结果值剩下的位就是只出现1次的数了。

但是反思一下，对于不同的数，我都要将它们映射到不同的位上，而且一旦有n个数，我的bitmap相当于使用了2^n的空间，那如果我们不采用这种方式，直接使用这个值呢

修改尝试

对于序列，如果直接使用这个值，就会产生不同的数直接互相干扰，例如数列 3 5 7,他的运算结果是0，因为3和5异或恰好就是7。为了避免这种互相干扰带来的冲突，我们选择哈希随机数。

哈希随机数

此时就需要请出我们的哈希产生作用，我们希望将原本的序列中的数字映射到一个不互相干扰的数字上，对此我们通常采用mt19937_64 rnd(time(0))，产生一个随机数，再将普通数字映射到上面。

代入该随机数的目的就是为了减少冲突。

mt19937_64 是 c++ 自带的梅森旋转（Mersenne Twister）伪随机数，可以随机生成 64 位整数。同时它输出的数字也是64位无符号整数。

此时代入它，让我们解决更加复杂的题目。

问题2：

给一个长度为 n 的数组 A，找到所有的连续子序列 S ，其长度为L，满足：S包含A中前L个的所有数字。求这样的区间个数。

题解：

就是在询问对于区间[L, R] 和区间[1, R - L + 1], 元素是否相同，对此可以理解为

判断一个序列是否是另一个序列的排列组合问题

以下便是题解代码

#include<bits/stdc++.h>
using namespace std;

mt19937_64 random(time(0)); // 创建随机数引擎
using hash_t = uint64_t;    // 随机数和运算后的数都是64无符号整数

int solve(int n)
{
    vector<hash_t> preXorValue(n + 1);
    vector<hash_t> hashValue(n + 1);
    vector<bool> hasSet(n + 1);

    for (int i = 1; i <= n; i++)
    {   
        int temp;
        cin >> temp;
        if(not hasSet[temp]){
            hashValue[temp] = random();
            hasSet[temp] = true;
        }
        preXorValue[i] = preXorValue[i - 1] ^ hashValue[temp]; // 计算前缀和
    }

    int result = 0;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            if ((preXorValue[r] ^ preXorValue[l - 1]) == preXorValue[r - l + 1]) // 注意异或运算的优先级，加括号
                result++;
        
    return result;
}

问题3：

判断一个序列的乘积是否是完全平方数

题解：

对序列的数进行因数分解，然后改序列所有因数出现的个数都是偶数个，即为平方数

Mai Icy