散乱无序的小整数序列

Question

背景

我有一个大的集合(〜数千)整数序列.每个序列都具有以下属性:

1. 它的长度为12;
2. 序列元素的顺序无关紧要;
3. 没有元素在同一序列中出现两次;
4. 所有元素都小于约300.

请注意,属性2.和3.意味着序列实际上是集合,但它们存储为C阵列以最大化访问速度.

我正在寻找一个好的C++算法来检查集合中是否已经存在新序列.如果不是,则将新序列添加到集合中.我考虑过使用哈希表(但请注意,我不能使用任何C++ 11构造或外部库,例如Boost).散列序列并将值存储在a std::set中也是一种选择,因为如果碰撞很少见,就可以忽略它们.任何其他建议也欢迎.

题

我需要一个可交换的哈希函数,即一个不依赖于序列中元素顺序的函数.我想首先将序列缩减为某些规范形式(例如排序),然后使用标准散列函数(参见下面的参考文献),但我宁愿避免与复制相关的开销(我无法修改原始序列)和排序.据我所知,下面引用的函数都不是可交换的.理想情况下,散列函数还应该利用元素永不重复的事实.速度至关重要.

有什么建议？

• http://partow.net/programming/hashfunctions/index.html
• http://code.google.com/p/smhasher/

Answer 1

这是一个基本的想法; 随意修改它.

1. 散列整数只是身份.

2. 我们使用公式boost::hash_combine来得到组合哈希.

3. 我们对数组进行排序以获得唯一的代表.

码:

#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;
}

更新:从头开始.您刚刚将问题编辑为完全不同的问题.

如果每个数字最多为300,那么您可以将排序后的数组分别压缩为9位,即108位."无序"属性只能为您节省额外的12 !,大约29位,所以它并没有真正有所作为.

您可以查找128位无符号整数类型,并直接在其中存储已排序的打包整数集.或者,您可以将该范围拆分为两个64位整数,并按上述方式计算哈希值:

uint64_t hash = lower_part + 0x9e3779b9 + (upper_part << 6) + (upper_part >> 2);

(或者可以0x9E3779B97F4A7C15用作幻数,即64位版本.)

Answer 2

对序列的元素进行数字排序，然后将序列存储在trie中。trie 的每个级别都是一个数据结构，您可以在其中搜索该级别的元素...您可以根据其中有多少元素使用不同的数据结构...例如，链表、二叉搜索树、或排序向量。

如果您想使用哈希表而不是 trie，那么您仍然可以对元素进行数字排序，然后应用这些非交换哈希函数之一。您需要对元素进行排序才能比较序列，您必须这样做，因为会发生哈希表冲突。如果不需要排序，那么您可以将每个元素乘以一个常数因子，该常数因子会将它们涂抹在 int 的位上（有找到这样一个因子的理论，但您可以通过实验找到它），然后对结果。或者，您可以在表中查找大约 300 个值，将它们映射到通过 XOR 混合良好的唯一值（每个值都可以是选择的随机值，以便它具有相同数量的 0 和 1 位 - 每个 XOR 翻转一个位的随机一半，这是最佳的）。