c++中std::hash的以及万能hash使用方法
·
首先是标准库中的std::hash函数,对于内置的类型,标准库中是已经提供了的(包括std::string),但是若是自己自定义的类型想要求其哈希值的话,就需要自己定义其哈希值的求值方式。下面是简单示范
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using std::cout;
using std::endl;
class MyClass
{
public:
MyClass():str("hello"), data(0) {}
bool operator==(const MyClass& rhs) const{return (data == rhs.data) && (str == rhs.str); } //注意要重载这个==,
//因为unordered_set或者unordered_map
//中需要对元素是否相同进行判断
public: //
int data;
std::string str;
};
//注意这里是将自己写的偏特化也同样加入到std中,因为他的模板是在std里面的,
//具体形式可以自己简单查看一下源码中的实现形式
//然后照着写一个自己的版本就行了。
namespace std
{
template<>
struct hash<MyClass>: public __hash_base<size_t, MyClass> //标准库中有这个继承,查看一下其实只是继承两个typedef而已,
//所以不写这个继承在这个例子中也是可以运行的
//但为了更好的使用这个hash,写上去会比较好
{
size_t operator()(const MyClass& rhs) const noexcept //这个const noexpect一定要写上去
{
return (std::hash<int>()(rhs.data)) ^ (std::hash<std::string>()(rhs.str) << 1); //当然,可以使用其他的方式来组合这个哈希值,
//这里是cppreference里面的例子,产生的数够乱就行。
}
};
}
int main()
{
MyClass c;
std::hash<MyClass> myHash; //创建一个函数对象
std::cout << myHash(c) << std::endl;
//注意这第三个参数是typename _Hash = hash < _Value >, 是可写可不写的,因为他是有默认形式的,写出来就是这样
std::unordered_map<MyClass, char, std::hash<MyClass>> m; //这第三个参数
std::unordered_set<MyClass> s; //和上面的是一个意思,第二个参数是typename _Hash = hash < _Value >,可写可不写, 这里我是没写的。
s.insert(c);
s.insert(c);
std::cin.get();
}
另外一种方式是使用侯捷老师在讲的“万能哈希函数”原理只要明白可变模板参数的使用方法就不会太难,下面是他课上使用的代码
#include <string>
using std::string;
class Customer
{
public:
string mFirstName;
string mLastName;
string mAge;
Customer(string firstName, string lastName, string age):mFirstName(firstName),mLastName(lastName),mAge(age){}
bool operator ==(const Customer& c) const
{
return (mFirstName == c.mFirstName && mLastName == c.mLastName && mAge == c.mAge);
}
};
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const
{
return hash_val(c.mFirstName, c.mLastName, c.mAge);
}
template <typename... Types>
size_t hash_val(const Types&... args)const
{
size_t seed = 0;
hash_value(seed, args...);
return seed;
}
template <typename T, typename... Types>
void hash_value(size_t& seed,
const T& firstArg,
const Types&... args) const
{
hash_combine(seed, firstArg);
hash_value(seed, args...);
}
template <typename T>
void hash_value(size_t& seed,
const T& val) const
{
hash_combine(seed, val);
}
template<typename T>
void hash_combine(size_t& seed,
const T& val) const
{
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
};
int main()
{
std::unordered_multiset<Customer, CustomerHash> set;
}
更多推荐


所有评论(0)