13

背景

我有大量（约数千个）整数序列。每个序列具有以下属性：

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

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

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

问题

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

有什么建议么？

4

5 回答 5

6

这是一个基本的想法；随意修改它。

  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 位版本。）

于 2012-10-11T13:54:44.310 回答
4

我只想使用 sum 函数作为哈希，看看你能做到多远。这没有利用数据的非重复性，也没有利用它们都 < 300 的事实。另一方面，它的速度非常快。

std::size_t hash(int (&arr)[12]) {
    return std::accumulate(arr, arr + 12, 0);
}

由于该函数需要不知道排序，因此我看不到在不先对输入值进行排序的情况下利用有限范围的输入值的聪明方法。如果这是绝对需要的，碰撞明智的，我会硬编码一个排序网络（即一些if...<code>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);
}
于 2012-10-11T14:02:38.300 回答
4

您可以在大小为 300 的位集中切换对应于 12 个整数中的每一个的位。然后使用 boost::hash_combine 中的公式组合十个 32 位整数，实现此位集。

这提供了可交换散列函数，不使用排序，并利用元素从不重复的事实。

如果我们选择任意位集大小并且如果我们为 12 个整数中的每一个设置或切换任意数量的位（为 300 个值中的每一个设置/切换哪些位由散列函数或使用预先计算的查找表）。这会导致布隆过滤器或相关结构。

我们可以选择 32 位或 64 位的布隆过滤器。在这种情况下，不需要将大比特向量的片段组合成单个散列值。在大小为 32 的 Bloom 过滤器的经典实现的情况下，哈希函数的最佳数量（或查找表的每个值的非零位）为 2。

如果不是经典布隆过滤器的“或”操作，而是选择“异或”并为查找表的每个值使用半个非零位，我们会得到一个解决方案，正如 Jim Balter 所提到的。

如果我们选择“+”而不是“或”操作，并为查找表的每个值使用大约一半的非零位，我们会得到一个类似于 Konrad Rudolph 建议的解决方案。

于 2012-10-11T14:36:49.687 回答
4

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

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

于 2012-10-11T19:03:53.800 回答
2

我接受了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] = {
  // 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);
}

这个算法是迄今为止我尝试过的算法中最快的（this，this with cubes and this with a bitset of size 300）。对于我的“典型”整数序列，碰撞率小于 1E-7，这对于我的目的来说是完全可以接受的。

于 2012-10-15T16:49:30.780 回答