8

为什么 hash 会将自身作为散列值返回？

我已经并排设置了一个散列和一个散列，字符串的一个按预期工作，而 int 的一个将自己作为散列值产生！

这是它应该如何工作的吗？

hash<int> h;
for( int i=0 ; i<15 ; ++i )
{
    cout << "int hash for " << i << " is " << h(i) << endl; 
}

hash<string> hs;
for( int i=0; i<15; ++i) {
    stringstream ss;
    ss << i;
    cout << "string hash for " << i << " is " << hs(ss.str()) << endl; 
}

结果是

+ g++-4.8 -std=c++11 -O2 -Wall -pedantic -Weffc++ -Wextra main.cpp
+ ./a.out
int hash for 0 is 0
int hash for 1 is 1
int hash for 2 is 2
int hash for 3 is 3
int hash for 4 is 4
int hash for 5 is 5
int hash for 6 is 6
int hash for 7 is 7
int hash for 8 is 8
int hash for 9 is 9
int hash for 10 is 10
int hash for 11 is 11
int hash for 12 is 12
int hash for 13 is 13
int hash for 14 is 14
string hash for 0 is 2297668033614959926
string hash for 1 is 10159970873491820195
string hash for 2 is 4551451650890805270
string hash for 3 is 8248777770799913213
string hash for 4 is 16215888864653804456
string hash for 5 is 7995238595416485409
string hash for 6 is 3835993668518112351
string hash for 7 is 905566266843721762
string hash for 8 is 17899137375351314596
string hash for 9 is 6623666755989985924
string hash for 10 is 2594088158685378223
string hash for 11 is 9717255990760309898
string hash for 12 is 11194622142508650503
string hash for 13 is 15638310844945205280
string hash for 14 is 1116181219906060362

你可以看到它运行在： http ://coliru.stacked-crooked.com/a/0c0e1536d19c533f

4

5 回答 5

11

为什么 hash 会将自身作为散列值返回？

坦率地说，因为它可以。这是最有效的做法，它为您提供了一个完美的整数散列函数。你简直不能做得比这更好！

于 2013-11-01T20:32:35.970 回答
4

不要将对象的散列值与您可能存储它的散列中的槽索引混淆。散列值只是给定输入值的近乎唯一数值的最佳尝试。

您的代码表明，对于您散列的每个整数值，都会返回一个唯一的散列值。

这是一个理想的哈希函数。

std::hash<int, std::string> hashTable;

hashTable[42] = "hello";

42 的哈希值为 42。但这个哈希中可能没有 42 个桶。operator[]在这里超载，并且将hash value通过哈希分布（桶数）来限制，以确定将您放入哪个插槽。

key = 42
hashValue = 42
hashKey = 42 % m_bucket.size() // which bucket to look for this key in
于 2013-11-01T20:42:06.010 回答
2

是的，它应该是这样工作的。散列函数返回一个整数，输入是一个整数，因此仅返回输入值会导致散列类型的最唯一散列。

于 2013-11-01T20:32:05.023 回答
2

哈希函数是从一个值到固定大小值的单射映射。如果源域和目标域相同，则标识似乎是一个合理的选择。

于 2013-11-01T20:32:14.907 回答
1

哈希函数必须为相同的输入产生相同的size_t类型值，并努力为不同的输入返回不同的值。对于最多与 一样宽size_t的整数，整数本身满足这些要求并且计算成本低。

于 2013-11-01T20:35:15.240 回答