为什么std :: Hash对于不同的字符串是相等的？

为什么std :: Hash对于不同的字符串有相同的结果？我用msvc2010sp1，看到这个结果时，我很惊讶：为什么std :: Hash对于不同的字符串是相等的？

int _tmain(int argc, _TCHAR* argv[]) 
    { 
    std::string sUniqId ("IndexBuf"); 
    std::stringstream sStream; 

    sStream << 10; 
    std::string sUniqId10 (sUniqId); 
    sUniqId10.append (sStream.str()); 
    size_t uHashStr = std::hash<std::string>()(sUniqId10); 

    sStream.str(""); 
    sStream << 11; 
    std::string sUniqId11 (sUniqId); 
    sUniqId11.append(sStream.str()); 
    size_t uHashStr1 = std::hash<std::string>()(sUniqId11); 

    sStream.str(""); 
    sStream << 12; 
    std::string sUniqId12 (sUniqId); 
    sUniqId12.append(sStream.str()); 
    size_t uHashStr2 = std::hash<std::string>()(sUniqId12); 

    cout <<"str: " << sUniqId10.c_str() << "\t" << "Hash1: " << uHashStr << endl; 
    cout <<"str2: " << sUniqId11.c_str() << "\t" << "Hash2: " << uHashStr1 << endl; 
    cout <<"str3: " << sUniqId12.c_str() << "\t" << "Hash3: " << uHashStr2 << endl; 

    return 0; 
    }

输出：

str: IndexBuf10  Hash1: 1286096800 
str2: IndexBuf11  Hash2: 1286096800 
str3: IndexBuf12  Hash3: 1286096800

有人知道为什么发生这种情况？

p.s.这个例子正确地为msvc2013更新1

来源

2014-03-18 angevad

重复？ http://stackoverflow.com/q/7968674/420683 – dyp

@dyp不，他们解决了这个问题，VS2013实现遍历整个字符串。 angevad：我无法使用VS2013更新1重现您的结果。32位和64位编译器为3个字符串生成不同的哈希值。 – Praetorian

@Praetorian OP：“这个例子**对于msvc2013 update1工作正常**” – dyp

哈希不需要是唯一的。例如，许多算法首先散列以选择作为实际项目的链接列表的“桶”。最有可能的是哈希算法在版本之间改变。

来源

2014-03-18 17:54:20 jschroedl

哈希函数不一定是bijective（一对一的对应关系，其中域中的每个元素唯一地映射到codomain中的元素）。他们应该是surjective（codomain中的每个元素都有一个相应的元素在域中），但它不是必要的，他们是injective，因为它似乎你是暗示。

来源

2014-03-18 18:03:55

也不需要是完全的。哈希函数没有什么特别的错误，因为某些原因，从不输出“SIZE_MAX”，它只是对可用哈希空间略微浪费。 –

@SteveJessop：我无法想象哈希函数的用法，但我想你是对的。我已经更新了我的回答，说“应该”是完全的。 –

那么，你可能需要一个散列函数，它避免了用于指示空插槽的幻数，但如果这是你需要的，你总是可以自己修改散列的结果。所以并不是任何人都需要使用该属性的散列，而是使用该属性的散列不会因此发生故障。 64位散列的MSB始终为0，甚至没有什么特别的错误，尽管这当然更加浪费。真的，这是一个63位哈希戴着一顶看似高大的帽子;-) –

为什么std :: Hash对于不同的字符串是相等的？

回答

相关问题