一、簡介
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的命名空間下，編譯的時候需要加個參數即可。
[linuxidc@localhost ~]$g++ -std=c++0x myHash.cpp
