C++中的Hashmap_c++ hashmap

C++中的Hashmap

Hashmap 结构

HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

HashMap是非线程安全的，只是用于单线程环境下,但是Hash Table是线程安全的（https://www.cnblogs.com/williamjie/p/9099141.html）

哈希表(key，value) 是把key值通过一个固定的算法即哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。

哈希冲突： 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一 个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。(https://www.jianshu.com/p/b468abd86f61)

Hashmap库（头文件）

C++中Hashmap的库为unordered_map#include <unordered_map>
如果C++的版本低于C++11,则会报错：[Error] ‘unordered_map’ was not declared in this scope
则需要将头文件改为
#include<tr1/unordered_map>
using namespace std::tr1;

Hashmap操作

建立Hashmap

unordered_map<int,int> Hashmap;

建立迭代器

unordered_map<int,int>::iterator it;

插入键值对

insert函数
Hashmap.insert(make_pair<int,int>(1,3));
Hashmap.insert(make_pair(1,3));
以上两种皆可
通过键添加
Hashmap[3]=1;

其他函数

it = Hashmap.begin() //指向哈希表的第一个容器
it = Hashmap.end() //指向哈希表的最后一个容器，实则超出了哈希表的范围，为空
Hashmap.size() //返回哈希表的大小
Hashmap.empty() //判断哈希表是否为空，返回值为true/false
Hashmap.clear() //清空哈希表

通过key值查找键值对
it = Hashmap.find(2) //查找key为2的键值对是否存在 ,若没找到则返回Hashmap.end()
if(Hashmap.find(2)!=Hashmap.end()) //判断找到了key为2的键值对

通过key值查找该key值下的键值对对数
Hashmap.count(1) //返回 1

swap交换两个Hashmap的键值对
Hashmap1.swap(Hashmap2);
swap(Hashmap1,Hashmap2);

Hashmap的遍历

//第一种
unordered_map<int, int> Hashmap;
for (auto p : Hashmap) {
	int front = p.first;   //key
    int end = p.second;   //value
}

//第二种
unordered_map<int, int> Hashmap;
for(auto it=Hashmap.begin();it!=Hashmap.end();it++)
{
    int front = it->first;   //key
    int end = it->second;   //value
}

//第三种
unordered_map<int,int> hash;
unordered_map<int,int>::iterator it;
it = hash.begin();
while(it != hash.end())
{
	int front= it->first;   //key
	int end = it->second;   //value
	it++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25