我接受了
Jim Balter的答案,因为他最接近我最终编写的代码,但所有答案都因其有用而获得了我的+1。
这是我最终采用的算法。我编写了一个小型Python脚本,生成300个64位整数,使它们的二进制表示恰好包含32个真和32个假位。真位的位置是随机分布的。
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 + ' };'
脚本生成的C++数组用法如下:
typedef int_least64_t HashType;
const int maxTableSize = 300;
HashType mask[maxTableSize] = {
};
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