我有一个包含数千个整数序列的大集合。每个序列都具有以下属性：
请注意，属性2和3意味着这些序列实际上是一个集合，但为了最大化访问速度，它们以C数组的形式存储。
我正在寻找一个优秀的C++算法来检查新序列是否已经存在于集合中。如果不存在，则将新序列添加到集合中。我考虑使用哈希表（请注意，我不能使用任何C++11构造或外部库，例如Boost）。将序列进行哈希处理并将其存储在std::set中也是一种选择，因为只要冲突足够稀少，就可以忽略它们。欢迎提出任何其他建议。
我需要一个可交换的哈希函数，即不依赖于序列中元素的顺序。我考虑首先将序列约简为某个规范形式（例如排序），然后使用标准哈希函数（参见下面的参考资料），但我宁愿避免与复制相关的开销（我无法修改原始序列）和排序。就我所知，下面引用的函数都不是可交换的。理想情况下，哈希函数还应利用元素从不重复的事实。速度至关重要。
有什么建议吗？
以下是一些基本的想法，可以根据需要进行修改。
对一个整数进行哈希只是将其转化为原样。
我们使用boost::hash_combine中的公式来组合哈希值。
我们对数组进行排序以得到唯一的代表。
代码:
#include <algorithm>
std::size_t array_hash(int (&array)[12])
{
int a[12];
std::copy(array, array + 12, a);
std::sort(a, a + 12);
std::size_t result = 0;
for (int * p = a; p != a + 12; ++p)
{
std::size_t const h = *p; // the "identity hash"
result ^= h + 0x9e3779b9 + (result << 6) + (result >> 2);
}
return result;
}
uint64_t hash = lower_part + 0x9e3779b9 + (upper_part << 6) + (upper_part >> 2);
0x9E3779B97F4A7C15，这是64位版本。）我建议使用sum函数作为哈希值，看看能得到什么结果。虽然这种方法没有利用数据的不重复属性以及它们都小于300的事实，但是速度非常快。
std::size_t hash(int (&arr)[12]) {
return std::accumulate(arr, arr + 12, 0);
}
由于该函数需要无序的操作，我认为在不排序的情况下利用输入值的有限范围没有明智的方法。如果绝对需要，针对碰撞问题，我会硬编码一个排序网络（即一些if…else语句）来原地排序这12个值（但我不知道12个值的排序网络会是什么样子，甚至是否实用）。
编辑 在评论讨论后，这里有一个非常好的减少碰撞的方法：在求和前将数组中的每个值提高到某个整数幂。最简单的方法是通过 transform 实现。这确实会生成一个副本，但可能仍然非常快：
struct pow2 {
int operator ()(int n) const { return n * n; }
};
std::size_t hash(int (&arr)[12]) {
int raised[12];
std::transform(arr, arr + 12, raised, pow2());
return std::accumulate(raised, raised + 12, 0);
}
0是一个允许的值（即这种方法会导致大量的0冲突）。 - Konrad Rudolph我们可以选择大小为32位或64位的布隆过滤器。在这种情况下，无需将大位向量的片段组合成单个哈希值。对于大小为32的经典布隆过滤器的情况，最优的哈希函数数量（或每个查找表值的非零位）为2。
如果我们选择经典布隆过滤器的“或”操作而不是“xor”，并且为查找表的每个值使用一半的非零位，那么我们就得到了Jim Balter提到的解决方案。
如果我们选择“+”而不是“或”操作，并为查找表的每个值使用大约一半的非零位，那么我们就得到了与Konrad Rudolph建议的类似的解决方案。
将你的序列元素按数字顺序排序，然后将序列存储在 Trie 中。Trie 的每一层都是一种数据结构，在该层中搜索该元素...您可以根据其中的元素数量使用不同的数据结构...例如：链接列表、二叉搜索树或排序向量。
如果你想使用哈希表而不是 Trie，则仍然需要按数字顺序对元素进行排序，然后应用其中一个非交换哈希函数。你需要对元素进行排序以比较序列，因为你将会遇到哈希表碰撞。如果你不需要排序，则可以将每个元素乘以一个常数因子，将它们涂抹在 int 的位上（有理论可找到这样的因子，但你可以通过实验找到），然后对结果进行异或运算。或者你可以在表格中查找你的 ~300 个值，将它们映射到混合均匀的唯一值上，通过 XOR 操作（每个值都可以选择一个随机值，使其具有相等数量的 0 和 1 位 —— 每个异或操作都会翻转随机的一半位，这是最优的）。
import itertools
import random
import sys
def random_combination(iterable, r):
"Random selection from itertools.combinations(iterable, r)"
pool = tuple(iterable)
n = len(pool)
indices = sorted(random.sample(xrange(n), r))
return tuple(pool[i] for i in indices)
mask_size = 64
mask_size_over_2 = mask_size/2
nmasks = 300
suffix='UL'
print 'HashType mask[' + str(nmasks) + '] = {'
for i in range(nmasks):
combo = random_combination(xrange(mask_size),mask_size_over_2)
mask = 0;
for j in combo:
mask |= (1<<j);
if(i<nmasks-1):
print '\t' + str(mask) + suffix + ','
else:
print '\t' + str(mask) + suffix + ' };'
typedef int_least64_t HashType;
const int maxTableSize = 300;
HashType mask[maxTableSize] = {
// generated array goes here
};
inline HashType xorrer(HashType const &l, HashType const &r) {
return l^mask[r];
}
HashType hashConfig(HashType *sequence, int n) {
return std::accumulate(sequence, sequence+n, (HashType)0, xorrer);
}
这个算法是我试过的算法中最快的（这里，这里使用立方体和这里使用大小为300的位集）。对于我的“典型”整数序列，碰撞率小于1E-7，这完全符合我的目的。
boost::hash_combine。 - Kerrek SBboost::hash_combine有五行。直接复制即可。 - Kerrek SBstd::set中。我使用std::memcmp定义了序列之间的弱排序关系。 - Arek' Fu