什么是在C ++ std :: unordered_map中使用的默认哈希函数? [英] What is the default hash function used in C++ std::unordered_map?
问题描述
我使用
unordered_map<string, int>
和
unordered_map<int, int>
在每种情况下使用什么哈希函数,在每种情况下什么是碰撞的可能性?
我将在每种情况下分别插入唯一的字符串和唯一的int作为键。
What hash function is used in each case and what is chance of collision in each case? I will be inserting unique string and unique int as keys in each case respectively.
我有兴趣知道hash函数的算法, int键及其冲突状态。
I am interested in knowing the algorithm of hash function in case of string and int keys and their collision stats.
推荐答案
函数对象 std :: hash<>
。
对于所有内置类型和一些其他标准库类型
,如 std :: string
和 std ::线程
。请参阅完整列表的链接。
Standard specializations exist for all built-in types, and some other standard library types
such as std::string
and std::thread
. See the link for the full list.
对于在 std :: unordered_map
中使用的其他类型,必须专门化 std :: hash<>
或创建自己的函数对象。
For other types to be used in a std::unordered_map
, you will have to specialize std::hash<>
or create your own function object.
碰撞的机会是完全依赖于实现的,但是考虑到整数限定在一个定义的范围之间,而字符串在理论上是无限长,我想说有一个更好的机会与字符串碰撞。
The chance of collision is completely implementation-dependent, but considering the fact that integers are limited between a defined range, while strings are theoretically infinitely long, I'd say there is a much better chance for collision with strings.
对于GCC中的实现,builtin-types的特殊化只返回位模式。以下是 bits / functional_hash.h
中定义的方法:
As for the implementation in GCC, the specialization for builtin-types just returns the bit pattern. Here's how they are defined in bits/functional_hash.h
:
/// Partial specializations for pointer types.
template<typename _Tp>
struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
{
size_t
operator()(_Tp* __p) const noexcept
{ return reinterpret_cast<size_t>(__p); }
};
// Explicit specializations for integer types.
#define _Cxx_hashtable_define_trivial_hash(_Tp) \
template<> \
struct hash<_Tp> : public __hash_base<size_t, _Tp> \
{ \
size_t \
operator()(_Tp __val) const noexcept \
{ return static_cast<size_t>(__val); } \
};
/// Explicit specialization for bool.
_Cxx_hashtable_define_trivial_hash(bool)
/// Explicit specialization for char.
_Cxx_hashtable_define_trivial_hash(char)
/// ...
std :: string
的专业化定义为:
#ifndef _GLIBCXX_COMPATIBILITY_CXX0X
/// std::hash specialization for string.
template<>
struct hash<string>
: public __hash_base<size_t, string>
{
size_t
operator()(const string& __s) const noexcept
{ return std::_Hash_impl::hash(__s.data(), __s.length()); }
};
进一步的搜索引导我们:
Some further search leads us to:
struct _Hash_impl
{
static size_t
hash(const void* __ptr, size_t __clength,
size_t __seed = static_cast<size_t>(0xc70f6907UL))
{ return _Hash_bytes(__ptr, __clength, __seed); }
...
};
...
// Hash function implementation for the nontrivial specialization.
// All of them are based on a primitive that hashes a pointer to a
// byte array. The actual hash algorithm is not guaranteed to stay
// the same from release to release -- it may be updated or tuned to
// improve hash quality or speed.
size_t
_Hash_bytes(const void* __ptr, size_t __len, size_t __seed);
_Hash_bytes
是 libstdc ++
。更多搜索引导我访问此文件,其中说明:
_Hash_bytes
is an external function from libstdc++
. A bit more searching led me to this file, which states:
// This file defines Hash_bytes, a primitive used for defining hash
// functions. Based on public domain MurmurHashUnaligned2, by Austin
// Appleby. http://murmurhash.googlepages.com/
因此,GCC对字符串使用的默认散列算法是MurmurHashUnaligned2 。
So the default hashing algorithm GCC uses for strings is MurmurHashUnaligned2.
这篇关于什么是在C ++ std :: unordered_map中使用的默认哈希函数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!