std::hash实现太简单分布不匀
(金庆的专栏 2017.5)
#include <iostream>
#include <functional>
using namespace std;
int main()
{
std::hash<int> hasher;
cout << hasher(2) << endl;
cout << hasher(3) << endl;
cout << hasher(4) << endl;
return 0;
}
输出为
jinqing@server:~/test$ g++ main.cpp -std=c++11
jinqing@server:~/test$ ./a.out
2
3
4
查看实现，/usr/include/c++/5/bits/functional_hash.h
operator()(_Tp __val) const noexcept \
{ return static_cast<size_t>(__val); } \
所以对分布有要求的，应该使用自己的hash, 不要使用 std::hash.
boost::hash 的实现也是简单取值，
boost_1_60_0/boost/functional/hash/hash.hpp
template <typename T>
typename boost::hash_detail::basic_numbers<T>::type hash_value(T v)
{
return static_cast<std::size_t>(v);
}
Boost说明了hash用于STL容器，而不是其它。
This hash function is designed to be used in containers based on the STL and is not suitable as a general purpose hash function.
VS2015会使用 FNV-1a
size_t operator()(const argument_type& _Keyval) const
{ // hash _Keyval to size_t value by pseudorandomizing transform
return (_Hash_seq((const unsigned char *)_Keyval.c_str(),
_Keyval.size() * sizeof (_Elem)));
}
inline size_t _Hash_seq(const unsigned char *_First, size_t _Count)
{ // FNV-1a hash function for bytes in [_First, _First + _Count)
...
但 FNV-1a 也不是通用的 hash 函数，如果输入值相近，则其输出值也相近。