0

我有如下结构化数据：

struct Leg
{
char type;
char side;
int qty;
int id;
} Legs[5];

在哪里

type is O or E, 
side is B or S;
qty is 1 to 9999 and qty in all Legs is relative prime to each other i.e. 1 2 3 not 2 4 6
id is an integer from 1 to 9999999 and all ids are unique in the group of Legs

为了构建上述数据的唯一签名，目前我正在构建一个如下所示的字符串：首先根据 id 对 Legs 进行排序；然后

signature=""
for i=1 to 5
signature+=id+type+qty+side of leg-i

然后我插入到 unordered_map 中，以便如果有任何匹配的结构化数据出现，我可以通过构建上述签名并进行查找来查找。

字符串上的 unorderd_map 表示键比较，它是字符串比较，也是哈希函数，它需要遍历通常约为 25 个字符的字符串。

为了提高效率，可以为上面的每个结构从上面的数据中构建一个唯一的整数，unorderd_map 中的查找/插入将非常快。

只是想知道是否有任何我可以利用的数学特性。

编辑：地图将包含键值对，如

<unique-signature=key, value=int-value needs to be located on looking up another repeating Leg group by constructing signature like above after sorting Legs based on id>
<123O2B234E3S456O3S567O2S789E2B, 989>

目标是从每个这样独特的重复腿组中建立独特的签名。腿可以有不同的顺序，但它们可以与另一组不同顺序的腿匹配，这就是为什么我根据唯一的 id 进行排序并构建签名。

我的签名是基于字符串的，如果有办法构造一个唯一的数字签名，那么我的查找/插入会更快。

4

3 回答 3

3

您可以从您拥有的字段中创建一个唯一的 40 位数字。为什么是 40 位？我很高兴你问。

您有 9,999,999 个可能的id值，这意味着您可以使用 24 位来表示所有可能性（log2(9999999) = 略高于 23）。

您有 9,999 个可能的qty值，这需要另外 14 位。

type并且side每个需要 1 位，这总共为您提供 40 位信息。将此数字存储为 a long long，您的地图就有了一个不错的快速键。

如果您真的想要一个唯一的int密钥，那么您可能不走运，因为摆脱 8 位信息将非常棘手。您可能能够利用该qty字段的共素性来用少于 14 位来表示它，但是我怀疑您是否可以将其降低到 6 位，因为这只会为您提供 64 个可能的值qty。

这是一种获得您所要求的方法，但@David Schwartz 的答案可能是您真正需要的：哈希冲突通常并不昂贵，除非您有一个非常糟糕的哈希函数 - 请参阅非随机哈希函数导致的应用程序漏洞示例这会如何咬你 - 或者精心设计的数据集恰好遇到最坏的情况。

在你的情况下，你应该对大卫的回答没意见。除非您对您的数据集非常不幸，否则它会足够快。

编辑：刚刚注意到您正在计算您的签名集 5 Legs。同样的数学适用，你只需要 200 位而不是 4 位。所以它不适合 along long除非你有一些可以在所有 5 个Leg对象之间共享的信息；例如，如果每组 5 个共享相同id的 。

坚持大卫的回答。

于 2013-10-22T00:51:41.273 回答
2

它不必是唯一的。我会建议类似：

std::size_t hash_value(const Leg& l)
{
    std::size_t ret = l.type;
    ret << = 8;
    ret |= l.side;
    ret *= 2654435761;
    ret += l.qty;
    ret *= 2654435761;
    ret += l.id;
    return ret * 2654435761;
}
于 2013-10-22T00:38:54.300 回答
1

为了为五个腿的组创建一个与顺序无关的散列函数，首先为单个腿选择一个散列函数——大卫的答案看起来很棒。计算五条腿中每条腿的哈希值。现在选择一个与顺序无关的函数来组合这五个哈希值。例如，您可以对哈希值进行异或运算，或者将它们全部相加，或者将它们全部相乘。

事实上，乘法分布在加法之上，而乘法是最后发生的操作，这让我对使用它有点警惕。我认为 xor 可能是我在这里给出的最佳选择；但是在生产中使用它之前，您绝对应该运行一些测试，看看您是否可以轻松地与它们中的任何一个产生冲突。

可能是多余的，但这是一个简单的实现，hash_value来自大卫的回答：

std::size_t hash_value(const Leg_Array& legs) {
    std::size_t ret = 0;
    for (int i = 0; i < 5; ++i) {
        ret ^= hash_value(legs[i]);
    }
    return ret;
}
于 2013-10-22T17:26:27.947 回答