三大 Hash 實現來源
| 命名空間/標準 | 頭文件 | 算法 | 適用場景 |
|---|
__gnu_cxx (GNU 擴展) | <ext/hash_fun.h> 或 <backward/hash_fun.h> | h = 5*h + c 簡單多項式 | 舊代碼兼容、GCC 專用 |
std::tr1 (TR1) | <tr1/functional> | FNV-1a (Fowler–Noll–Vo) | GCC 4.3+、VS2008+，通用性強 |
std (C++11) | <functional> | 實現定義（通常同 FNV 或 CityHash） | 現代 C++ 首選，標準化 |
|---|
__gnu_cxx::hash 核心代碼
// 字符串 hash
inline size_t __stl_hash_string(const char* s) {
unsigned long h = 0;
for (; *s; ++s) h = 5 * h + *s;
return static_cast(h);
}
// 偏特化：char*, const char*, char, wchar_t, 整數類型等
template<> struct hash { size_t operator()(char* s) const { return __stl_hash_string(s); } };
// ... 其餘整數類型直接返回值本身
自定義 string 專用 hash (GNU)
namespace __gnu_cxx {
template<> struct hash {
size_t operator()(const string& s) const {
return __stl_hash_string(s.c_str());
}
};
}
std::tr1::hash (FNV-1a) 核心
// 32 位版本
template<> struct Fnv_hash<4> {
static size_t hash(const char* first, size_t len) {
size_t result = 2166136261UL; // FNV_offset_basis
for (; len > 0; --len) {
result ^= static_cast(*first++);
result *= 16777619UL; // FNV_prime
}
return result;
}
};
// 64 位版本類似，常數不同
// 偏特化：string, wstring, 基本類型等
測試代碼 (GCC 4.7 + -std=c++0x)
#include
#include
#include // 或 (C++11)
int main() {
std::string s = "feng feng feng";
std::wstring ws = L"22222";
// 直接調用 FNV 不同位寬
std::cout << std::tr1::_Fnv_hash<1>::hash(s.c_str(), s.size()) << '\n';
std::cout << std::tr1::_Fnv_hash<4>::hash(s.c_str(), s.size()) << '\n';
std::cout << std::tr1::_Fnv_hash<8>::hash(s.c_str(), s.size()) << '\n';
// 標準介面
std::cout << std::tr1::hash()(s) << '\n';
std::cout << std::tr1::hash()(ws) << '\n';
std::cout << std::tr1::hash()(true) << '\n';
std::cout << std::tr1::hash()(24.0f) << '\n';
std::cout << std::tr1::hash()(24.0) << '\n';
std::cout << std::tr1::hash()(24) << '\n';
return 0;
}
C++11 std::hash 使用建議
- 優先用
std::hash<T>() (需 <functional>)，標準化、可移植。
- 自定義類型需偏特化
std::hash<MyType>，實現 size_t operator()(const MyType&) const noexcept。
- 無序容器
unordered_map/set 默認使用 std::hash。
- 若需高性能或特定分佈，可考慮
absl::Hash、xxHash、CityHash 等第三方庫。
總結
從 GNU 擴展到 TR1 再到 C++11 標準，Hash 函數經歷了算法升級（簡單多項式 → FNV-1a → 實現定義優化）。現代項目應直接使用 std::hash，僅在維護舊代碼時接觸 __gnu_cxx 或 tr1。
