C++中现成的hash函数

文章由LinuxBoy分享于2019-04-01 08:04:02热评（281）

C++中现成的hash函数

一、简介

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

二、__gnu_cxx中的hash函数

这个hash函数包含在__gnu_cxx这个命名空间里，实现在backward/hash_fun.h这个头文件里。

inline size_t
__stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5 * __h + *__s;
return size_t(__h);
}

然后基于这个hash算法特化了下面几个版本的hash函数

template<> hash<char*>(const char* __s)
template<> hash<const char*>(const char* __s)
template<> hash<char>(char __x)
template<> hash<unsigned char>(unsigned char __x)
template<> hash<signed char>(unsigned char __x)
template<> hash<short>(short __x)
template<> hash<unsigned short>(unsigned short __x)
template<> hash<int>(int __x)
template<> hash<unsigned int>(unsigned int __x)
template<> hash<long>(long __x)
template<> hash<unsigned long>(unsigned long __x)

上一篇博客中，我也基于这个hash算法实现了一个hash<string>的版本

1
2
3
4
5
6
7
8
9 namespace __gnu_cxx
{
template <>
struct hash<string>
{
size_t operator()(const string &s) const
{ return __stl_hash_string(s.c_str()); }
};
}

三、tr1中hash函数(Fnv_hash)

特点和用途：FNV能快速hash大量数据并保持较小的冲突率，它的高度分散使它适用于hash一些非常相近的字符串，比如URL，hostname，文件名，text，IP地址等。

这个hash函数包含在std::tr1这个命名空间里，包含tr1/functional头文件即可，实现在tr1_impl/functional_hash.h文件中。下面是它的实现

//Dummy generic implementation (for sizeof(size_t) != 4, 8)
template<std::size_t = sizeof(std::size_t)>
struct Fnv_hash
{
static std::size_t
hash(const char* first, std::size_t length)
{
std::size_t result = 0;
for (; length > 0; --length)
result = (result * 131) + *first++;
return result;
}
};

template<>
struct Fnv_hash<4>
{
static std::size_t
hash(const char* first, std::size_t length)
{
std::size_t result = static_cast<std::size_t>(2166136261UL);
for (; length > 0; --length)
{
result ^= (std::size_t)*first++;
result *= 16777619UL;
}
return result;
}
};

template<>
struct Fnv_hash<8>
{
static std::size_t
hash(const char* first, std::size_t length)
{
std::size_t result = static_cast<std::size_t>(14695981039346656037ULL);
for (; length > 0; --length)
{
result ^= (std::size_t)*first++;
result *= 1099511628211ULL;
}
return result;
}
};

然后基于这个Fnv_hash算法实现了各种版本的hash函数，其中包括string和wstring版本的。

四、测试

#include <iostream>
#include <string>
#include <tr1/functional>

int main()
{
std::string name = "feng feng feng";
//直接调用Fnv_hash
std::cout << std::tr1::_Fnv_hash<1>::hash(name.c_str(), name.size()) << std::endl;
std::cout << std::tr1::_Fnv_hash<4>::hash(name.c_str(), name.size()) << std::endl;
std::cout << std::tr1::_Fnv_hash<8>::hash(name.c_str(), name.size()) << std::endl;

//string
std::cout << std::tr1::hash<std::string>()(name) << std::endl;

//wstring
std::wstring age = L"22222";;
std::cout << std::tr1::hash<std::wstring>()(age) << std::endl;

//bool
std::cout << std::tr1::hash<bool>()(true) << std::endl;

//float
std::cout << std::tr1::hash<float>()(24.0f) << std::endl;

//double
std::cout << std::tr1::hash<double>()(24.0) << std::endl;

//short
std::cout << std::tr1::hash<short>()(static_cast<short>(24)) << std::endl;

//int
std::cout << std::tr1::hash<int>()(24) << std::endl;

//long
std::cout << std::tr1::hash<long>()(24L) << std::endl;
return 0;
}

说明：

gcc 4.8以上的版本支持c++11,我用的是4.7的版本。tr1/functional在gcc 4.7的版本里gcc的搜寻路径下直接就有functional这个头文件，可以直接#include <functional>，这样就不需要std::tr1这个明明空间了，直接在std的命名空间下，编译的时候需要加个参数即可。

[bkjia@localhost ~]$g++ -std=c++0x myHash.cpp

本文永久更新链接地址：

推荐文章：

C++中现成的hash函数