首页 / C++ / 关于C++中Hash的应用
关于C++中Hash的应用
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了关于C++中Hash的应用,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3558字,纯文字阅读大概需要6分钟。
内容图文
![关于C++中Hash的应用](/upload/InfoBanner/zyjiaocheng/1139/b160bc7f172f4018b075bf84f1a7ff26.jpg)
本文只介绍我们在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; } longlong getPhone() const { return phone; } package(string m_name = 0, longlong m_pNum = 0); booloperator== (const package& p) const { return name == p.name && phone == p.phone; } private: string name; longlong 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> usingnamespace std; class package { public: string getName() const { return name; } longlong getPhone() const { return phone; } package(string m_name = 0, longlong m_pNum = 0); booloperator== (const package& p) const { return name == p.name && phone == p.phone; } private: string name; longlong phone; }; package::package(string m_name, longlong 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; return0; }
原文:https://www.cnblogs.com/xiguas/p/9977933.html
内容总结
以上是互联网集市为您收集整理的关于C++中Hash的应用全部内容,希望文章能够帮你解决关于C++中Hash的应用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。