c++ - 散列一个无序的小整数序列

Question

背景

我有大量(约数千个)整数序列。每个序列都有以下属性:

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

请注意，属性 2. 和 3. 暗示序列实际上是 sets，但它们存储为 C 数组以最大限度地提高访问速度。

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

问题

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

有什么建议吗？

• 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 作为魔数(Magic Number)，即 64 位版本。)