0.自定義類型需要滿足的條件
我們需要為自定義類型Key實現(xiàn)一個Function Object，他需要遵守以下條件：
- 返回類型為
std::size_t - 接受單個參數(shù)，參數(shù)類型為
Key抱婉，一般我會習(xí)慣使用const Key& key - 他是一個常量成員函數(shù)
- 他不會拋出異常
- 對于相同的
Key屈梁，我們需要返回相同的值;對于不同的Key董饰，我們需要盡量減小collision的發(fā)生
聽上去很多要求，其實很簡單，我們有兩種方法來實現(xiàn)以上要求，下面一一闡述暇屋。
1.std::hash的template specialization
我們選擇std::pair<std::string,int>作為哈希表的Key
namespace std{
template <>
struct hash<std::pair<std::string,int >>{
std::size_t operator()(const std::pair<std::string, int>& p)const noexcept {
return std::hash<std::string>()(p.first)^std::hash<int>()(p.second);
}
};
}
接下來我們就可以直接使用了
class UserDefinedHash{
public:
UserDefinedHash(){
}
void addData(const std::pair<std::string,int>& key,int val){
templateSpecilization[key]=val;
}
int showData(const std::pair<std::string,int>& key){
auto re=templateSpecilization.find(key);
if(re != templateSpecilization.end())
return templateSpecilization.at(key);
return -1;
}
private:
std::unordered_map<std::pair<std::string,int>,int> templateSpecilization;
};
2.使用自定義Function Object
struct MyHash{
std::size_t operator()(const std::pair<int,int>& p) const noexcept {
return std::hash<int>()(p.first)^std::hash<int>()(p.second);
}
};
在使用時，制定std::unordered_map的第三個參數(shù)為MyHash即可
class UserDefinedHash{
public:
UserDefinedHash(){
}
void addData(const std::pair<int,int>& key,int val){
functor[key]=val;
}
private:
std::unordered_map<std::pair<int,int>,int,MyHash> functor;
};
3.其他的思考
在選擇哈希函數(shù)時洞辣，上面第二個例子其實并不好咐刨，因為當(dāng)Key為{1,1}～{n,n}時，返回的哈希經(jīng)過XOR運算扬霜，結(jié)果都是一樣的定鸟，所以我們在選擇哈希函數(shù)時最好慎重考慮，避免一些明顯的錯誤畜挥，如果有條件可以使用boost::hash_combine.
