柚子快报邀请码778899分享：散列表 学习 个人哈希表笔记
前言：
因为本人正在学习C++,所以这个笔记只涉及哈希表的简单介绍，以及C++中unordered_map的使用方面，后续学习的更多，笔记会做的更完善。
哈希表简介
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
进一步解释
散列函数
因为哈希表的底层逻辑仍然是数组，那么仍然保留有数组的相关特点：连续的，有固定下标。查找元素的时间复杂度小。而哈希表的结构表面上就是键-值两个元素，打眼一看与数组好像没什么关系，但哈希表具有查找元素的高效性的原因，就是因为散列函数。
具体可以理解为，对表中key 的离散化，将其离散到固定的数组下标，再映射到value从而找到它。
从这几张图就可以很清楚的看到哈希表的存储方式了。
键值对
哈希表存放的就是键值对，可以通过key快速的访问value的值。
键值对就是 key-value的组合
unordered_map
介绍
c++的容器——unordered_map，它是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。
特性：
关联性：unordered_map是一个将key和value关联起来的容器，通过key去检索value，而不是通过绝对地址（和顺序容器不同），它可以通过键直接访问值，查找数据更为高效。 无序性：unordered_map存储元素是没有顺序的，只是根据key的哈希值， 将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。key值应该是唯一的，key和value的数据类型可以不相同。unordered_map查询单个key的时候效率比map高，但是要查询某一范围内的key值时比map效率低。
使用
构造unordered_map
#include
/*构造哈希表*/
unordered_map
unordered_map
unordered_map
unordered_map
unordered_map
容量操作
/*容量操作*/
cout << hashmap_2.size() << endl; //返回该容器中的元素数量
cout << hashmap_2.max_size() << endl; //返回该容器可以容纳的元素最大数量
cout << hashmap_2.bucket_count() << endl; //返回容器中桶bucket的数量，一个桶可以存储多个键值对，可以通过这个值查看哈希表的结构和性能情况
cout << hashmap_2.empty() << endl; //检查容器是否为空，如果为空则返回true,反之返回false
//load.factor()
cout << hashmap_2.load_factor() << endl; //返回容器当前的负载因子，负载因子是一个用来衡量哈希表空间利用程度的指标，计算公式为：负载因子 = 元素个数 / 桶的数量。当负载因子超过某个阈值时，通常会触发哈希表的再散列操作（rehashing），以保持哈希表的性能
负载因子：负载因子是一个用来衡量哈希表空间利用程度的指标，计算公式为：负载因子 = 元素个数 / 桶的数量。当负载因子超过某个阈值时，通常会触发哈希表的再散列操作（rehashing），以保持哈希表的性能。
元素操作
find()-查找元素
/*元素操作*/
//find-查找元素
unordered_map
if (got == hashmap.end())
cout << "not found. " << endl;
else
cout << got->first << " is " << got->second << endl;
哈希表的迭代器：和大多数容器一样，find()函数向后遍历，直到找到待查找元素返回指向它的迭代器，如果没找到返回hashmap_2.end()，迭代器和指针一样可以通过->first,来访问键，->second来访问值
insert()-插入元素
/*insert-插入元素*/
//insert()函数将新的元素加入到表头
unordered_map
pair
mymap.insert(PII); //insert()函数没有将map对象插入unordered_map对象的重载形式，但是可以将pair组合成的元素插入其中，因为map中也是键值对的映射关系，而pair组合的两个元素没有直接的关系。
mymap.insert(make_pair
mymap.insert(hashmap_2.begin(), hashmap_2.end()); //范围插入
mymap.insert({"peach", 7}); //初始化数组形式插入
//遍历
for (auto item = mymap.begin(); item != mymap.end(); item ++ )
cout << item->first << " is " << item->second << endl;
insert()函数的实参：insert()函数没有将map对象插入unordered_map对象的重载形式，但是可以将pair组合成的元素插入其中，因为map中也是键值对的映射关系，而pair组合的两个元素没有直接的关系。
erase()-擦除元素
mymap.erase(mymap.begin()); //擦除第一个元素,erase()函数的实参可以是指向需删除元素的迭代器
mymap.erase("apple"); //擦除键为"apple"的元素，erase()函数的实参可以是键
mymap.erase(mymap.find("grape"), mymap.end()); //删除"grape"及之后的所有元素，erase()函数的实参可以是一个范围.注意这个范围是一个左闭右开的区间，如果是(mymap.find("apple"), mymap.find("grape"));那么键为grape的元素还存在，如果是(mymap.find("apple"), mymap.end()); 那么最后一个也会删除,因为end()函数返回的是表内元素的下一个迭代器
erase()范围擦除：注意这个范围是一个左闭右开的区间，如果是(mymap.find("apple"), mymap.find("grape"));那么键为grape的元素还存在，如果是(mymap.find("apple"), mymap.end()); 那么最后一个也会删除,因为end()函数返回的是表内元素的下一个迭代器。
at()-查找元素
cout << mymap.at("apple") << endl; //如果存在则返回key映射的value值，如果不存在，抛出out_of_range异常。
at()函数：比使用find()函数定位key-value省略了创建迭代器的过程，所以每个函数有其特定的作用。
clear()-清空元素
mymap.clear(); //清空表中的所有元素
cout << mymap.size() << endl;
swap()-交换
mymap.swap(hashmap_2);
swap()：交换两个unordered_map，注意不是交换特定元素，是交换两个表中的所有元素，并且注意交换的两个表类型要相同。
count()-元素计数
mymap.count("apple");
count()：在容器中寻找键key，注意寻找的key的数据类型要符合map的定义。该函数返回表中key所映射的value的数量，而因为unordered_map不允许多映射的情况，所以实际这个函数只能返回0或1。
所以查看元素是否存在就可以这样写：
//查看mymap中x是否存在
mymap.find(x) != mymap.end();
//或
mymap.count(x) != 0;
使用unordered_map时的其他注意：
/*使用auto 进行循环，修改的值的作用域仅仅在循环之内，循环结束后循环中修改的值会变回原来的值。*/
cout << "分割线--------------" << endl;
for (auto x : mymap)
{
x.second = 0;
cout << x.second << endl; //输出全是0
}
for (auto x : mymap)
{
cout << x.second << endl; //输出原本的值
}
cout << "分割线--------------" << endl;
for (unordered_map
{
item->second = 0;
cout << (*item).second << endl; //输出全是0
}
for (unordered_map
{
cout << (*item).second << endl; //输出全是0
}
出现这种情况是因为，使用auto会复制一个map类型的元素，而修改的只是复制的x原本表中的元素并没有修改，而使用迭代器进行遍历并修改,类似于指针实在原本的表上面进行数据的修改。
C++中map与unordered_map的区别
运行效率方面：unordered_map最高，而map效率较低但 提供了稳定效率和有序的序列。占用内存方面：map内存占用略低，unordered_map内存占用略高,而且是线性成比例的。
3.1头文件
map：#include
unordered_map：#include
3.2内部实现机理
map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的
3.3各自的优缺点及使用场景
map优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高。缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间 适用处：对于那些有顺序要求的问题，用map会更高效一些。
unordered_map优点：内部实现了哈希表，因此其查找速度是常量级别的。缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map
参考文章
C++中的unordered_map用法详解-CSDN博客
C++ 哈希表_c++哈希表-CSDN博客
哈希表的基础知识（含代码实现，及使用用例）_哈希表 key-CSDN博客
哈希表使用总结_哈希表的用法-CSDN博客
笔记到这里就结束了，在之后的学习中笔者会不断补充增加自己的见解，努力做的更好。
柚子快报邀请码778899分享：散列表 学习 个人哈希表笔记
相关文章
发表评论