5

我有两个对象，Account 和 Transaction，其中 Transaction 是唯一的一对 Account 和一个递增的 ID 号。我想使用 boost::hash 来获取这些的唯一值，并按照说明重载了 hash_value 方法：http: //www.boost.org/doc/libs/1_53_0/doc/html/hash/custom.html

class Account {
  ...
};

class Transaction
{
    Account account;
    unsigned int id;
};

Account 的 hash_value 方法可以正常工作，并且返回的值对于给定的帐户始终是唯一的，但是要制作唯一的对，Transaction 的方法需要使用 hash _combine （根据 boost 的说明）：

inline std::size_t hash_value( const Account& acct )
{
    boost::hash<int> hasher;
    size_t rval = hasher( acct.id() ); //just an int. guaranteed to be unique
    return rval;
}


inline std::size_t hash_value( const Transaction& t )
{
    std::size_t seed = 0;
    boost::hash_combine( seed, t.account );        
    boost::hash_combine( seed, t.id );

    return seed;
}

这有时会为不同的输入返回相同的值。为什么？？我只有几千个账号，身份证号才上几十万。这似乎不是一个上限问题。

有谁知道这是否是一个错误，或者我是否需要播种 boost hash？

谢谢

4

2 回答 2

5

查找完美散列，生日悖论，以及为了完整起见的鸽巢原则。

归结为哈希函数通常会产生冲突，除非您正在哈希的内容具有您已经利用的非常特定的属性。您看到任何给定键集的哈希冲突的机会将非常高，因为这是我们没有连接的数学现实之一：获得任何特定哈希的机会为 1/365，您的几率仅给定 23 个键，碰撞是 50/50。

于 2013-05-02T21:29:01.007 回答
1

Boost 提供了很好的通用散列函数，因为它对输入没有/很少假设并且试图快速。在大多数情况下，您可以对输入做出特定假设，以创建比从 boost 中获得的更好的哈希函数。例如，您可以通过假设字符串包含英文文本来优化字符串哈希函数。通过使用假设，您可以制作更好的哈希函数（例如：更少的冲突）。例如，如果您需要合并两个哈希值，每个哈希值都是 1 到 1000 之间的整数，很明显不会发生冲突，因为您将其中一个乘以 1000，然后将另一个相加。

编写自定义哈希函数时要非常小心，因为除了出错之外还有一个明显的缺点：代码的健壮性总是会受到影响。

示例 1：您优化了英语语言字符串的 UTF-8 字符串哈希。突然，应用程序获得了中文字符串。

示例 2：您假设 ID 总是很小，因为 ID 从 1 开始，每次分配一个时增加 1，并且分配的数量永远不会超过几千个。现在有人将 id 更改为随机 GUID。

于 2013-05-02T21:45:45.980 回答