【C++ STL】停下你到处找 hash_map 使用教程的手，看我的就好了

看、未来

发布于 2020-08-25 23:21:43

3K1

发布于 2020-08-25 23:21:43

文章被收录于专栏：CSDN搜“看，未来”

这是我耗时最长的文章，因为资料少，水货又多，我又傻。没事，前人栽树。我要把这篇写全面，省的你们到处去找。

① 你是windows系统还是Linux系统？

这个问题很重要啊，要区分清楚。如果是Linux，那可以认真看一下，毕竟博主写的也不容易嘛。如果是windows系统，那我建议可以去搜一下unordermap，我接下来也会去写那篇。因为如果在windows系统上跑hash_map/hashtable等一系列非STL标准库的话，它会提示你不让用，直接报错。理由如下：

error C2338: <hash_map> is deprecated and will be REMOVED. Please use <unordered_map>. You can define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS to acknowledge that you have received this warning.
#ifndef _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS
static_assert(false, "<hash_map> is deprecated and will be REMOVED. "
    "Please use <unordered_map>. You can define "
    "_SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS "
    "to acknowledge that you have received this warning.");
 #endif /* _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS */
hash_map是C++非标准STL，因为标准化的推进，hash_map属于非标准容器，未来将要用unordered_map替代之。建议我们使用unorder_map替代hash_map

这个代码在文件hashmap中，如果有兴趣可以自己去找。（故意写错一下就找到了）

如果是在Linux下运行的话，使用的名空间不一样。

using namespace __gnu_cxx;

还是上面那段代码，不过报错变警告了。

当然，如果你非要在windows下使用的话，也是可以的，改一下上面那一块，可以直接把报错删掉，也可以把报错变警告，只要你能把修改保存进去就行，反正我改完是存不回去了。

② 为什么要使用hash_map

那当然是因为它快啊 hash_map的底层实现是哈希表，通过哈希函数，它的查找效率可以达到常数O(1)。最好的情况是这样的，最坏的情况也是O(n)，这个情况的好坏就取决于哈希函数的优劣了，所以好的哈希函数对于hash_map来说至关重要。

③ 使用代码示例

看你要在什么系统上用咯，如果是windows，命名空间是：using namespace stdext; Linux的命名空间上面有。

后面的内容难度就要拔高了，所以先把代码放这里了，如果不想拔高，可以拿码去测试了。

#include <hash_map>
#include <string>
#include <iostream>

using namespace std;
//define the class
class ClassA{
        public:
        ClassA(int a):c_a(a){}
        int getvalue()const { return c_a;}
        void setvalue(int a){c_a;}
        private:
        int c_a;
};

//1 define the hash function
struct hash_A{
        size_t operator()(const class ClassA & A)const{
                //  return  hash<int>(classA.getvalue());
                return A.getvalue();
        }
};


//2 define the equal function
struct equal_A{
        bool operator()(const class ClassA & a1, const class ClassA & a2)const{
                return  a1.getvalue() == a2.getvalue();
        }
};

int main()
{
        hash_map<ClassA, string, hash_A, equal_A> hmap;
        ClassA a1(12);
        hmap[a1]="I am 12";
        ClassA a2(198877);
        hmap[a2]="I am 198877";
        
        cout<<hmap[a1]<<endl;
        cout<<hmap[a2]<<endl;
        return 0;
}

以下内容属于拔高部分

④hash_map原理

hash_map基于hash table（哈希表）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：得到key 通过hash函数得到hash值得到桶号(一般都为hash值对桶数求模) 存放key和value在桶内。

其取值过程是:

得到key 通过hash函数得到hash值得到桶号(一般都为hash值对桶数求模) 比较桶的内部元素是否与key相等，若都不相等，则没有找到。取出相等的记录的value。 hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候). 由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

⑤ hash_map数据结构扼要

hash_map类声明

template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
class _EqualKey = equal_to<_Key>,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map
{
        ...
}

也就是说，在上例中，有以下等同关系：

…

hash_map<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;

alloc 不用过份关注，是STL的空间配置器，很精华的一部分。如果有兴趣，可以去我主页找，置顶了，大概一万字。

hash_map是一个聚合类，它继承自_Hash类，包括一个vector，一个list和一个pair，其中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构，简要地伪码如下：

class hash_map<class _Tkey, class _Tval>
{
	private:
           typedef pair<_Tkey, _Tval> hash_pair;
           typedef list<hash_pair>    hash_list;
           typedef vector<hash_list>  hash_table;
};

当然，这只是一个简单模型。

下面是一张开链的哈西散列表：

⑥ 哈希函数：hash< int> (第三个参数)

struct hash<int> {
        size_t operator()(int __x) const { return __x; }
};

是个函数对象。

在SGI STL中，提供了以下hash函数：

struct hash<char*>
struct hash<const char*>
struct hash<char> 
struct hash<unsigned char> 
struct hash<signed char>
struct hash<short>
struct hash<unsigned short> 
struct hash<int> 
struct hash<unsigned int>
struct hash<long> 
struct hash<unsigned long>

也就是说，如果你的key使用的是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，你只能如此，例如对于string，就必须自定义hash函数。

第六点到此为止，太难了，以我现在的水平也写不出案例，要对底层进行调用。

以下属于hash_map类方法分析

⑧ 构造函数

简单变量作为索引。

这个，意会啊。比方说这样：

	hash_map<int, int> IntHash;
    IntHash[1] = 123;
    IntHash[2] = 456;

    int val = IntHash[1];
    int val = IntHash[2];

再比方说这样：

	hash_map<const char*, int> CharHash;
	CharHash["a"] = 123;
	CharHash["b"] = 456;

对这个栗子要避免这样用：

char szInput[64] = "";
scanf("%s", szInput);

int val = CharHash[szInput];

最终的结果就是无论输入任何字符串，都无法找到对应的整数值。因为输入的字符串指针是szInput指针，和"a"或"b"字符串常量指针的大小是绝对不会相同。

当然如果是会写仿函数的大佬另当别论。

⑨ 设置大小

hash_map(size_type n) 如果讲究效率，这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。

⑩ 查找

const_iterator find(const key_type& k) const 用查找，输入为键值，返回为迭代器。

⑪ 下标定位

data_type& operator[](const key_type& k) 特别方便，可像使用数组一样使用。不过需要注意的是，当你使用[key ]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你希望插入该元素时，你可以直接使用[]操作符。