求对元素顺序不敏感的哈希函数：无重复整数序列去重

首先明确：存在这类对顺序不敏感的哈希函数，而且有多种高效方案可以替代你提到的排序法和异或法，以下是具体可行的方法：

1. 基于质数映射的乘积哈希 #

利用乘法交换律，为0到数百范围内的每个整数预分配唯一的大质数，遍历序列时将每个元素对应的质数相乘，最后对一个大质数（如10^9+7）取模得到哈希值。

比如预定义映射：prime[123] = 1000003，prime[145] = 1000033，prime[210] = 1000037，prime[77] = 1000039，序列a和b的乘积都是这四个质数的乘积，取模后结果完全一致。

优势：

• 时间复杂度O(N)，仅需一次遍历
• 碰撞概率极低，只要质数和模数选得足够大
• 无需修改原序列

注意：每一步乘积都要取模，避免数值溢出。

2. 基于位掩码的哈希（适合小范围元素） #

由于你的元素范围是0到数百，直接用位掩码表示集合：每个整数x对应掩码的第x位，将该位置为1。最后把这个位掩码转换成整数（或直接用掩码字节数组作为哈希标识）。

比如序列a对应掩码的第77、123、145、210位为1，序列b的掩码完全相同，因此哈希值一致。

优势：

• 绝对无碰撞（元素不重复时，每个唯一集合对应唯一掩码）
• 时间复杂度O(N)，空间占用极小（如0-500的范围仅需63字节）
• 实现简单，无需复杂计算

3. 幂次累加哈希 #

选择大基数（如911382629）和大模数（如10^9+9），遍历序列时计算每个元素x的base^x，将所有结果累加后取模得到哈希值。由于加法交换律，顺序不影响最终结果。

示例：序列a的哈希值为(base^123 + base^145 + base^210 + base^77) % mod，和序列b的计算结果完全相同。

优势：

• 时间复杂度O(N)，可预计算base^x的结果（x范围固定0-数百），进一步提升效率
• 碰撞概率低，基数和模数选得合适时几乎不会出现冲突

对比你提到的现有方法 #

• 排序法：O(NlogN)的时间复杂度和额外空间确实不如上述O(N)方案高效，没必要采用。
• 异或法：元素范围小导致异或结果比特位利用率极低，易出现不同集合哈希值相同的情况，确实不是最优解。

内容的提问来源于stack exchange，提问作者hopeimnotstupid