boost hash为不同的输入返回相同的值

Question

我有两个对象,帐户和交易,其中交易是唯一的帐户对和递增的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;
}

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

有谁知道这是一个错误,还是我需要种子提升哈希？

谢谢

Answer 1

查找完美的哈希,以及生日悖论,并且为了完整起见,还要考虑鸽子原则.

它归结为散列函数通常会产生冲突,除非你正在散列的东西具有你已经利用的非常具体的属性.你看到任何给定键集的哈希冲突的可能性都会非常高,因为这是我们没有用过的数学现实之一:获得任何特定哈希值的概率为1/365,你的几率是只有23个键,碰撞是50/50.