《hash_map详解》由会员分享，可在线阅读，更多相关《hash_map详解（8页珍藏版）》请在金锄头文库上搜索。
1、具体讲解 STL hash_map 系列 来源于 :/ stlchina.org/0 为什么需要 hash_map用过 map 吧？map 供给一个很常用的功能，那就是供给 key-value 的存储和查找功能。例如，我要记录一个人名和相应的存储，而且随时增加，要快速查找和修改：岳不群华山派掌门人，人称君子剑张三丰武当掌门人，太极拳创始人东方不败第一高手，葵花宝典.这些信息假设保存下来并不简单，但是找起来比较麻烦。例如我要找“张三丰“的信息，最傻的方法就是取得全部的记录，然后依据名字一个一个比较。假设要速度快，就需要把这些记录依据字母挨次排列，然后依据二分法查找。但是增加记录的时候同时需要保持
2、记录有序，因此需要插入排序。考虑到效率，这就需要用到二叉树。讲下去会没完没了，假设你使用 STL 的 map 容器，你可以格外便利的实现这个功能，而不用关心其细节。关于 map 的数据构造细节，感爱好的朋友可以参看学习 STL map, STL set 之数据构造根底。看看 map 的实现: #include #include using namespace std;.map namemap;/增加。namemap“岳不群“=“华山派掌门人，人称君子剑“; namemap“张三丰“=“武当掌门人，太极拳创始人“; namemap“东方不败“=“第一高手，葵花宝典“;./查找。if(namema
3、p.find(“岳不群“) != namemap.end().不觉得用起来很 easy 吗？而且效率很高，100 万条记录，最多也只要 20 次的string pare 的比较，就能找到你要找的记录;200 万条记录事，也只要用 21 次的比较。速度永久都满足不了现实的需求。假设有 100 万条记录，我需要频繁进展搜寻时，20 次比较也会成为瓶颈，要是能降到一次或者两次比较是否有可能？而且当记录数到 200 万的时候也是一次或者两次的比较，是否有可能？而且还需要和 map 一样的便利使用。答案是确定的。这时你需要 has_map. 虽然 hash_map 目前并没有纳入 C+ 标准模板库中，但
4、几乎每个版本的 STL 都供给了相应的实现。而且应用格外广泛。在正式使用 hash_map 之前，先看看 hash_map 的原理。1 数据构造：hash_map 原理这是一节让你深化理解 hash_map 的介绍，假设你只是想整个吞枣，不想理解其原理，你倒是可以略过这一节，但我还是建议你看看，多了解一些没有害处。hash_map 基于 hash table哈希表。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的状况下，用空间换时间的做法是值得的。另外，编码比较简洁也是它的特点之一。其根本原理是：
5、使用一个下标范围比较大的数组来存储元素。可以设计一个函数哈希函数，也叫做散列函数，使得每个元素的关键字都与一个函数值即数组下标，hash 值相对应，于是用这个数组单元来存储这个元素；也可以简洁的理解为，依据关键字为每一个元素“分类”，然后将这个元素存储在相应 “类”所对应的地方，称为桶。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能消灭对于不同的元素，却计算出了一样的函数值，这样就产生了“冲突”，换句话说， 就是把不同的元素分在了一样的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。hash_map，首先安排一大片内存，形成很多桶。是利用 hash 函
6、数，对 key 进展映射到不同区域桶进展保存。其插入过程是： 得到 key通过 hash 函数得到 hash 值得到桶号(一般都为 hash 值对桶数求模) 存放 key 和 value 在桶内。其取值过程是:得到 key通过 hash 函数得到 hash 值得到桶号(一般都为 hash 值对桶数求模)比较桶的内部元素是否与 key 相等，假设都不相等，那么没有找到。取出相等的记录的 value。hash_map 中直接地址用 hash 函数生成，解决冲突，用比较函数解决。这里可以看出，假设每个桶内部只有一个元素，那么查找的时候只有一次比较。当很多桶内没有值时，很多查询就会更快了(指查不到的时
7、候).由此可见，要实现哈希表, 和用户相关的是：hash 函数和比较函数。这两个参数刚好是我们在使用 hash_map 时需要指定的参数。2 hash_map 使用2.1 一个简洁实例不要焦急如何把“岳不群“用 hash_map 表示，我们先看一个简洁的例子：随机给你一个 ID 号和 ID 号相应的信息，ID 号的范围是 12 的 31 次方。如何快速保存查找。#include #include using namespace std; int main()hash_map mymap;mymap9527=“唐伯虎点秋香“; mymap1000000=“百万富翁的生活“; mymap10000
8、=“白领的工资底线“;.if(mymap.find(10000) != mymap.end().够简洁，和map 使用方法一样。这时你或许会问？hash 函数和比较函数呢？不是要指定么？你说对了，但是在你没有指定 hash 函数和比较函数的时候，你会有一个缺省的函数，看看 hash_map 的声明，你会更加明白。下面是 SGI STL 的声明：template class _Key, class _Tp, class _HashFcn = hash, class _EqualKey = equal_to,class _Alloc =STL_DEFAULT_ALLOCATOR(_Tp) clas
9、s hash_map.也就是说，在上例中，有以下等同关系：.hash_map mymap;/等同于:hash_mapint, string, hash, equal_to mymap;Alloc 我们就不要取关注太多了(期望深化了解 Allocator 的朋友可以参看标准库 STL ：Allocator 能做什么)2.2 hash_map 的 hash 函数hash到底是什么样子？看看源码:struct hash size_t operator()(intx) const returnx; ;原来是个函数对象。在 SGI STL 中，供给了以下 hash 函数：struct hash stru
10、ct hash struct hashstruct hash struct hash struct hashstruct hash struct hashstruct hash struct hashstruct hash 也就是说，假设你的 key 使用的是以上类型中的一种，你都可以使用缺省的 hash 函数。固然你自己也可以定义自己的 hash 函数。对于自定义变量，你只能如此，例如对于string，就必需自定义 hash 函数。例 如：struct str_hashsize_t operator()(const string& str) constunsigned longh = 0;f
11、or (size_t i = 0 ; i str.size() ; i +) h = 5*h + stri; return size_t(h);/假设你期望利用系统定义的字符串 hash 函数，你可以这样写：struct str_hashsize_t operator()(const string& str) constreturn returnstl_hash_string(str.c_str();在声明自己的哈希函数时要留意以下几点： 使用 struct，然后重载 operator().返回是 size_t参数是你要 hash 的 key 的类型。函数是 const 类型的。假设这些比较难
12、记，最简洁的方法就是照猫画虎，找一个函数改改就是了。现在可以对开头的“岳不群“进展哈希化了. 直接替换成下面的声明即可：map namemap;/改为：hash_map namemap;其他用法都不用边。固然不要忘了吧 str_hash 的声明以及头文件改为 hash_map。你或许会问：比较函数呢？别焦急，这里就开头介绍 hash_map 中的比较函数。2.3 hash_map 的比较函数在 map 中的比较函数，需要供给 less 函数。假设没有供给，缺省的也是 less 。在 hash_map 中，要比较桶内的数据和 key 是否相等，因此需要的是是否等于的函数:equal_to 。先看
13、看 equal_to 的源码：/本代码可以从 SGI STL/先看看 binary_function 函数声明，其实只是定义一些类型而已。template struct binary_function typedef _Arg1 first_argument_type; typedef _Arg2 second_argument_type; typedef _Result result_type;/看看 equal_to 的定义：template struct equal_to : public binary_functionbool operator()(const _Tp& x, cons
14、t _Tp& y) const return x = y; ;假设你使用一个自定义的数据类型，如 struct mystruct, 或者 const char* 的字符串，如何使用比较函数？使用比较函数，有两种方法. 第一种是：重载= 操作符，利用 equal_to;看看下面的例子：struct mystructint iID; int len;bool operator=(const mystruct & my) const return (iID=my.iID) & (len=my.len) ; 这样，就可以使用equal_to作为比较函数了。另一种方法就是使用函数对象。自定义一个比较函数体：struct compare_strbool operator()(const char* p1, con
