哈希表的实现(注:计算对应变量的哈希值需要重载hashTable::hash_val函数),参考实现如下
#include
#include
using namespace std;
/*注:functional里面定义了求哈希值的函数,这里的函数可以不用了*/
namespace hash_val
{
const size_t _FNV_prime = 16777619U;
const size_t _FNV_offset_basis = 2166136261U;
inline size_t _Fnv1a_append_bytes(size_t _Val,
const unsigned char * const _First, const size_t _Count) noexcept
{
for (size_t _Idx = 0; _Idx < _Count; ++_Idx)
{
_Val ^= static_cast(_First[_Idx]);
_Val *= ::_FNV_prime;
}
return (_Val);
}
template
inline size_t _Hash_array_representation(
const _Kty * const _First, const size_t _Count) noexcept
{ // bitwise hashes the representation of an array
return (::_Fnv1a_append_bytes(::_FNV_offset_basis,
reinterpret_cast(_First), _Count * sizeof(_Kty)));
}
/*hash_val(string)*/
template inline
size_t hash_val(const basic_string<_Elem, _Traits, _Alloc>& _Str)
{ // hash string to size_t value
return (::_Hash_array_representation(_Str.c_str(), _Str.size()));
}
/*hash_val(const char*)*/
inline size_t hash_val(const char *_Str)
{ // hash NTBS to size_t value
return (::_Hash_array_representation(_Str, strlen(_Str)));
}
/*hash_val int*/
template inline
size_t hash_val(const _Kty& _Keyval)
{ // hash _Keyval to size_t value one-to-one
return ((size_t)_Keyval ^ (size_t)0xdeadbeef);
}
}
1