stl hash函数,C++ hash map

　　C STL-waytofall-Blog Garden中hash_map的介绍

　　STL中的哈希表hash_map引入了0。为什么需要hash_map？你用过地图吗？Map提供了一个很常见的功能，就是提供了key-value的存储和搜索功能。比如我想记录一个人的名字和对应的存储，随时增加。我想快速找到并修改它：

　　岳不群——华山派掌门人，人称君子剑。

　　武当掌门人、太极拳创始人张三丰。

　　东方不败-第一大师，葵花宝典

　　.这些信息如果保存的话并不复杂，但是查找起来比较麻烦。比如我要找‘张三丰’的资料，最笨的办法就是把所有的记录都找来，按照名字一个一个比对。要想快，需要将这些记录按字母顺序排列，然后按照二分法进行搜索。但是，在添加记录时，需要保持记录的顺序，所以需要插入sort。考虑到效率，这就需要使用二叉树。如果使用STL的map容器，可以非常方便的实现这个功能，不要在意它的细节。关于map的数据结构细节，有兴趣的朋友可以参考STL map的数据结构基础，STL set。看看map的实现：#include map

　　#包含字符串

　　使用命名空间std

　　映射字符串，字符串名称映射。

　　//增加。

　　Namemap[岳不群]=华山派掌门，人称君子剑；

　　Namemap[张三丰]=武当掌门人，太极拳创始人；

　　Namemap[东方不败]=第一高手，葵花宝典；

　　//查找。

　　If(namemap.find(岳不群)！=namemap.end()){

　　}你不觉得很好用吗？而且效率很高，100万条记录。最多只需要string.compare. 20万条记录的20次比较就可以找到你要找的记录，而且只需要21次比较。速度永远满足不了现实的需求。如果有100万条记录，当我需要频繁搜索的时候，20次比较也会成为瓶颈。有没有可能减少到一两次比较？而唱片数到200万的时候，也是一两比较。可能吗？而且要像地图一样好用。

　　答案是肯定的。这时候你就需要has_map了。虽然目前C标准模板库中没有包含hash_map，但是几乎每个版本的STL都提供了相应的实现。并且被广泛使用。在正式使用hash_map之前，先看看hash_map的原理。

　　1数据结构：hash_map原理本节让你深入了解hash_map的介绍。如果你只是想吞下一切，不想了解它的原理，可以跳过这一节，但我还是建议你看一看。多了解一些也无妨。

　　Hash_map基于哈希表。哈希表最大的优点是大大减少了存储和查找数据所消耗的时间，这几乎可以看作是一个常数时间。但是代价只是消耗更多的内存。但是，随着可用内存越来越多，用空间换时间是值得的。此外，易编码也是其特点之一。

　　基本原理是使用下标范围大的数组来存储元素。可以设计一个函数(hash function，也叫hash function)让每个元素的关键字对应一个函数值(即数组下标，hash值)，然后用这个数组单元来存储这个元素；也可以简单理解为将每个元素按照关键字进行“分类”，然后将这个元素存储在对应“类”的对应位置，称为bucket。

　　但是不能保证每个元素的关键字与函数值一一对应，所以很有可能对不同的元素计算同一个函数值，从而导致“冲突”。换句话说，不同的元素被划分到同一个“类”中。一般来说，“直接寻址”和“冲突解决”是哈希表的两个特点。

　　Hash_map，先分配大面积内存，形成很多桶。哈希函数用于将密钥映射到不同的存储区域(存储桶)。插入过程是：

　　通过hash函数获取key得到的hash值得到桶号(一般是hash值对桶号取模)并将key和值存储在桶中。值选择过程如下：

　　通过hash函数得到key得到的hash值得到桶号(一般是hash值对桶号取模)。比较桶的内部元素是否等于键。如果不相等，就找不到。检索到的相等记录的值。hash_map中的直接地址由hash函数生成，冲突消解由比较函数解决。这里可以看到，如果每个桶内部只有一个元素，那么搜索时只有一个比较。当许多桶中没有值时，许多查询会更快。

　　可见，要实现哈希表，与用户相关的有两个东西：哈希函数和比较函数。这两个参数只是我们在使用hash_map时需要指定的参数。

　　2 hash_map用了一个2.1的简单例子。不用担心如何用hash _ map表达‘岳不群’。我们先来看一个简单的例子：随机给你一个身份证号，以及身份证号对应的信息。ID号的范围是1 ~ 2的31次方。如何快速保存查找？

　　#包含哈希映射

　　#包含字符串

　　使用命名空间stdint main(){

　　hash_map int，string mymap

　　Mymap[9527]=唐伯虎点秋香；

　　Mymap[1000000]=百万富翁的生活；

　　Mymap[10000]=白领的工资底线；

　　if(mymap.find(10000)！=mymap.end()){

　　}很简单，和用地图一样。这时候，你可能会问？哈希函数和比较函数呢？你不想详细说明吗？你是对的，但是当你没有指定散列函数和比较函数时，你会有一个默认函数。看看hash_map的语句，就更好理解了。以下是SGI STL的语句：模板class _ key，class _ TP，class _ hash fcn=hash _ key，

　　class _EqualKey=equal_to _Key，

　　class _ Alloc=_ _ STL _ DEFAULT _ ALLOCATOR(_ Tp)

　　类哈希映射

　　}即在上面的例子中，有如下等价关系：

　　hash_map int，string mymap

　　//相当于：

　　hash_map int，string，hash int，equal _ to int mymap让我们不要太在意它。(想进一步了解分配器的，请参考标准库STL:分配器能做什么？)2.2 hash _ map的hash函数hash int长什么样？看看源代码：

　　结构散列int {

　　size _ t operator()(int _ _ x)const { return _ _ x；}

　　};原来是一个函数对象。在SGI STL中，提供了以下哈希函数：struct hash char*

　　结构哈希常量字符*

　　结构哈希字符

　　结构哈希无符号字符

　　结构哈希有符号字符

　　结构哈希短

　　结构哈希无符号短整型

　　结构散列int

　　结构哈希无符号整数

　　长结构哈希

　　Struct hash unsigned long也就是说，如果你的键使用了上述类型之一，你可以使用默认的hash函数。当然，你也可以定义自己的哈希函数。对于自定义变量，您只能这样做。例如，对于字符串，您必须自定义哈希函数。示例：struct hash_string{

　　size_t operator()(常量字符串str)常量

　　无符号long _ _ h=0；

　　for(size _ t I=0；I str . size()；我)

　　_ _ h=5 * _ _ h str[I]；

　　返回size _ t(_ _ h)；

　　//如果您希望使用系统定义的字符串哈希函数，可以这样写：

　　结构哈希字符串{

　　size_t operator()(常量字符串str)常量

　　return _ _ STL _ hash _ string(str . c _ str())；

　　};在Visual Studio下，hash函数和equal函数在一个结构里，但是不要SGI的是分开的。结构哈希字符串

　　静态常量size _ t bucket _ size=4；

　　静态常量size _ t min _ buckets=8；//1.定义哈希函数

　　size_t operator()(常量字符串str)常量

　　无符号long _ _ h=0；

　　for(size _ t I=0；I str . size()；我)

　　_ _ h=5 * _ _ h str[I]；

　　返回size _ t(_ _ h)；

　　} ////1.定义哈希函数

　　//size_t operator()(常量字符串str)常量

　　//return _ _ STL _ hash _ string(str . c _ str())；

　　//} //2.定义相等函数

　　布尔运算符()(常量字符串p1，常量字符串p2)常量{

　　返回p1==p2

　　};在声明自己的哈希函数时要注意以下几点：使用struct，然后重载operator()；有，返回size _ t；参数是要哈希的键的类型；属于const类型。如果这些很难记，最简单的方法就是在猫后面画一只老虎，随便找个函数改一下就行了。

　　现在你可以散列开头的“岳不群”。只需用下面的语句替换它：

　　映射字符串，字符串名称映射。

　　//改为：

　　hash_map string，string，hash_string名称映射。其他用途不使用边缘。当然，别忘了把hash_string的声明和头文件改成hash_map。你可能会问：比较函数呢？别急，这里会介绍hash_map中的比较函数。

　　2.3 map中hash _ map比较函数的比较函数需要提供较少的函数。如果未提供，则默认为less Key。在hash_map中，需要比较桶中的数据和键是否相等，所以需要的是equal函数：equal_to Key。先看equal_to的源代码：

　　//这段代码可以从SGI STL下载

　　//我们先来看看binary_function函数声明。其实只是定义了一些类型。

　　模板class _Arg1，class _Arg2，class _Result

　　struct binary_function {

　　typedef _ arg 1 first _ argument _ type；

　　typedef _ arg 2 sec _ argument _ type；

　　typedef _ Result result _ type

　　//看看equal_to的定义：

　　模板类_Tp

　　struct equal _ to:public binary _ function _Tp，_ Tp，bool

　　bool operator()(const _Tp __x，const _ Tp _ _ y)const { return _ _ x==_ _ y；}

　　};如果使用自定义数据类型，比如struct mystruct，或者const char*的字符串，如何使用比较函数？有两种方法可以使用比较函数。

　　第一种是重载==运算符，使用equal _ to看一下下面的例子：

　　结构mystruct{

　　int iID

　　int len

　　布尔运算符==(const mystruct my) const{

　　return(iID==my . iID)(len==my . len)；

　　};这样就可以用equal_to mystruct作为比较函数。另一种方法是使用函数对象。自定义比较函数体：

　　结构比较_字符串{

　　布尔运算符()(常量字符* p1，常量字符*p2)常量{

　　return strcmp(p1，p2)==0；

　　};通过compare_str，可以使用hash_map。typedef hash_map const char*，string，hash const char*，compare _ str StrIntMap

　　StrIntMap名称映射；

　　Namemap[岳不群]=华山派掌门，人称君子剑；

　　Namemap[张三丰]=武当掌门人，太极拳创始人；

　　Namemap[东方不败]=第一高手，葵花宝典；2.4 hash_map函数hash_map的函数类似于map的函数。函数的具体参数和解释请参考STL编程手册：Hash_map，主要介绍几种常用的函数。

　　Hash_map(size_type n)如果效率很重要，这个参数一定要设置。n主要用于设置hash_map容器中哈希桶的数量。桶越多，哈希函数冲突的概率越小，重新申请内存的概率越小。n越大，效率越高，但内存消耗也越大。const _ iterator find(const key _ type k)。使用搜索，输入作为键值，返回作为迭代器。data _ type operator[](const key _ typek)。这是我最常用的功能之一。因为特别方便，可以像数组一样使用。但是需要注意的是，使用[key]操作符时，如果容器中没有key元素，就相当于自动添加了一个key元素。所以当你只是想知道容器里有没有关键元素的时候，可以用find。如果要插入这个元素，可以直接使用[]运算符。插入函数。当容器不包含键值时，插入函数类似于[]操作符。但是当容器中的元素越来越多时，每个桶中的元素数量就会增加。为了保证效率，hash_map会自动申请更大的内存来生成更多的桶。因此，在插入之后，前面的迭代器可能不可用。擦除功能。在插入过程中，当每个桶中的元素过多时，hash_map可能会自动扩展容器的内存。但是，在sgi stl中，erase不会自动回收内存。因此，在您调用erase之后，其他元素的迭代器仍然可用。3相关哈希容器除了hash_map，哈希容器还包括hash _ set、hash _ multimap和has _ multiset。这些容器与set、multimap、multiset之间的区别与hash_map和map之间的区别相同。我想我不需要一一阐述。

　　4这里列出的其他常见问题应该有助于你理解和使用hash_map。

　　hash _ map和map的区别？构造函数。Hash_map需要Hash函数，等于function；地图只需要比较函数(小于函数)。存储结构。Hash_map用哈希表存储，map一般用RB树实现。所以它的内存数据结构是不一样的。4.2什么时候需要使用hash_map，什么时候需要使用map？一般来说hash_map的搜索速度比map快，搜索速度基本，数据量不变。map的查找速度是log(n)级。常数不必小于log(n)。hash也是hash函数需要时间的。看到了吧，如果考虑效率，尤其是元素达到一定数量级的时候，考虑hash_map。但是，如果您对内存使用特别严格，并且希望您的程序消耗尽可能少的内存，那么您必须小心。hash_map可能会让你为难，尤其是当你有大量hash_map对象的时候，你控制不了，hash_map的构造速度慢。

　　现在知道怎么选了吗？权衡三个因素：搜索速度、数据量和内存使用量。

　　下面是另一个关于hash_map和map的故事。看看这个：http://dev.csdn.net/Develop/article/14/14019.shtm

　　4.3如何将自己定义的类型添加到hash_map中？你只需要做两件事，定义散列函数，和定义比较函数。以下代码是一个示例：

　　-bash-2.05 b $ cat my . CPP #包含字符串

　　#包括iostream

　　使用命名空间std//只是针对linux中的 #include hash_map

　　#如果__GNUC__ 2

　　#包含外部/哈希映射

　　使用_ _ GNU _ cxx:hash _ map；

　　#否则

　　#包含哈希映射

　　#endif//0定义类

　　class ClassA{public:

　　ClassA(int a):c_a(a){}

　　int getvalue()const { return c _ a；}

　　void setvalue(int a){ c _ a=a；}私人：

　　int c _ a；

　　//1定义哈希函数

　　结构哈希_A{

　　size _ t operator()(const class A class A)const {

　　//返回hash int(class a . getvalue())；

　　返回a . getvalue()；

　　//2定义等号函数

　　struct equal_A{

　　布尔运算符()(常量类a1，常量类a2)常量{

　　return a1 . getvalue()==a2 . getvalue()；

　　int main()

　　hash_map ClassA，string，hash_A，equal _ A hmap

　　a1类(12)；

　　hmap[a1]=我12 ；

　　a2类(198877)；

　　hmap[a2]=我是198877 ；

　　cout hmap[a1]endl；

　　cout hmap[a2]endl；返回0；

　　}-bash-2.05b$ make my

　　c-O-pipe-March=Pentium pro my . CPP-O my

　　-bash-2.05亿美元。/我的

　　我12岁

　　Visual Studio下的I 198877，hash函数和equal函数在一个结构里，不要SGI的是分开的。自己定义的类名

　　.

　　结构化my_hash

　　静态常量size _ t bucket _ size=4；

　　静态常量size _ t min _ buckets=8；

　　size_t运算符()(const MyClass键)const

　　size _ t hash=999

　　for(size _ t I=0；我100000；我)

　　hash=“哈希函数”；

　　返回哈希；

　　布尔运算符()(常量MyClass c1，常量MyClass c2)常量

　　返回“相等函数”；

　　int main()

　　hash_map MyClass，int，my _ hash my

　　.

　　4.4如何用hash_map替换程序中已有的map容器？这很容易，但是需要你有良好的编程风格。建议您尝试使用typedef来定义类型：

　　typedef映射键，值键映射。当你想用hash_map代替时，只需要修改：typedef hash_map Key，Value KeyMap其他基本不变。当然，你需要注意是否有Key类型的哈希函数和比较函数。4.5为什么hash_map不标准？不知道为什么不标准。有一种解释是，STL加入标准C的时候，hash_map系列当时还没有完全实现，以后应该会成为标准。如果有人知道更合理的解释，也想告诉我。但我想表达的是，正因为hash_map不是标准的，很多平台都安装了G编译器，并不一定有hash_map的实现。我碰到过这样一个例子。所以在使用这些非标准库的时候，一定要提前测试。另外，如果考虑平台迁移，还是省着用比较好。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。