金庆的专栏

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  355 随笔 :: 0 文章 :: 454 评论 :: 0 Trackbacks
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 函数,如果输入值相近,则其输出值也相近。
posted on 2017-05-26 12:00 金庆 阅读(167) 评论(0)  编辑 收藏 引用 所属分类: 1. C/C++

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理