关于C++中Hash的应用
关于C++中Hash的应用
本文只介绍我们在C++中如何使用Hash这种数据结构达到我们编程的目的，有关Hash的概念和实现不做详谈。
C++11新增了一类散列容器包括unordered_set, unordered_map, unordered_multiset, unordered_multimap， 即之前熟悉的hash_set, hash_map等。
这类容器底层以哈希表实现之，通过unordered_map介绍下这类容器的使用。
unordered_map 是一个模板类，需要我们提供5个魔板参数。依次为：key值的类型， value值的类型，hash函数， 等价函数， 容器分配器。其中后三个有默认参数，那我们是不是只需要提供前2个模板参数就可以使用了呢？ 不一定。当我们使用的key为内置类型时（如int, double, float, string等），后面三个默认模板参数在STL内有其特化版本，故可以直接进行使用。可一旦你的类为自定义类型， 其中的hash和equal就得由你自己提供。其实也不难理解， 假设你的对象是一块石头，石头怎么进行hash, 石头怎么怎么比大小呢？编译器当然不知道，这就需要你告诉编译器。下面我们对这2种情况分别举例说明。
（一）、当key为内置类型：
unordered_map<string, int> m_map;当key为内置类型， 仅需提供key与value的类型便可运用。 其中hash<string> 与 equal <int> 均有特化版本，分配器对整个容器进行内存管理，这三个参数均为默认参数。
（二）、当key为自定义类型：
比如我们简单定义一个package类，里面仅有名字，电话2项数据。
class package
{
public:
string getName() const { return name; }
long long getPhone() const { return phone; }
package(string m_name = 0, long long m_pNum = 0);
bool operator== (const package& p) const
{ return name == p.name &&
phone == p.phone;
}
private:
string name;
long long phone;
};然后将原生hash包装使用下：
namespace std
{
template<>
struct hash<package>
{
size_t operator() (const package& s) const noexcept
{
return hash<decltype(s.getName())>()(s.getName()) +
hash<decltype(s.getPhone())>()(s.getPhone());
}
}; // 间接调用原生Hash.
}或者可以借助借助boost库的hash_value:
namespace std
{
template<>
struct hash<package>
{
size_t operator() (const package& s) const noexcept
{
auto t = make_tuple(s.getName(), s.getPhone());
size_t value = boost::hash_value(t);
return value; // make_tuple(s.getName(), s.getPhone()) 等价于 tuple<string, long long>()(s.getName(), s.getPhone())
}
}; // 间接调用原生Hash.
}当我们把Hash函数（package的特化版本）和 等价函数 （操作符==重载）提供后， 便可使用自定义版本的unordered_map了:
unordered_map<package, int> m_map;下面给出测试代码：
（测试环境： VS2017）
#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
//#include <boost/functional/hash.hpp> // 根据安装路径选择hash.hpp
#include <tuple>
using namespace std;
class package
{
public:
string getName() const { return name; }
long long getPhone() const { return phone; }
package(string m_name = 0, long long m_pNum = 0);
bool operator== (const package& p) const
{ return name == p.name &&
phone == p.phone;
}
private:
string name;
long long phone;
};
package::package(string m_name, long long m_pNum)
: name(m_name), phone(m_pNum) { }
namespace std
{
template<>
struct hash<package>
{
size_t operator() (const package& s) const noexcept
{
return hash<decltype(s.getName())>()(s.getName()) +
hash<decltype(s.getPhone())>()(s.getPhone());
//auto t = make_tuple(s.getName(), s.getPhone());
//size_t value = boost::hash_value(t);
//return value; // make_tuple(s.getName(), s.getPhone()) 等价于 tuple<string, long long>()(s.getName(), s.getPhone())
}
}; // 间接调用原生Hash.
}
int main()
{
unordered_map<package, int> m_map;
package p1{ "Wang", 13399996666};
package p2{ "Li", 13399993333};
package p3{ "Zhang", 13399992222};
package p4{ "Zhou", 13399991111 };
package p5{ "Wang", 13399996666};
package p6{ "Wang", 13366669999 };
m_map[p1]++;
m_map[p2]++;
m_map[p3]++;
m_map[p4]++;
m_map[p5]++;
m_map[p6]++;
cout << m_map.bucket(p1) << " ";
cout << m_map.bucket(p2) << " ";
cout << m_map.bucket(p3) << " ";
cout << m_map.bucket(p4) << " ";
cout << m_map.bucket(p5) << " ";
cout << m_map.bucket(p6) << " " << endl;
return 0;
}