数组与hash表

参考链接：https://blog.csdn.net/qq_46780256/article/details/122398766

1.数组

优点：已知某元素的下标值时，通过下标值的方式获取到数组中对应的元素，这种获取元素的速度是非常快的。

缺点：如果某个元素的下标值未知，查找效率低。

只是知道该元素在数组中，这时我们想要获取该元素就只能对数组进行线性查找，即从头开始遍历，这样的效率是非常低的，如果一个长度为10000的数组，我们需要的元素正好在第10000个，那么我们就要对数组遍历10000次，显然这是不合理的。

2.hash

优点

无论数据有多少，处理起来都特别的快
能够快速地进行插入修改元素、删除元素、查找元素等操作

缺点：

哈希表中的数据是没有顺序的
数据不允许重复

3.C++哈希表unordered_map的使用以及与map和hash_map的对比

参考：https://blog.csdn.net/luolaihua2018/article/details/109412566

（1）

map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

（2）优缺点

map ：
优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间
适用处，对于那些有顺序要求的问题，用map会更高效一些
unordered_map ：

优点：因为内部实现了哈希表，因此其查找速度快，对于查找问题，unordered_map会更加高效.
缺点：哈希表的建立比较耗费时间

注：unordered_map是hash_map的替代名称
最初的 C++ 标准库中没有类似 hash_map 的实现，但不同实现者自己提供了非标准的 hash_map。因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。从 C++ 11 开始，hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。

5.hashmap操作过程

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。

其插入过程是：
1、得到key
2、通过hash函数得到hash值
3、得到桶号(一般都为hash值对桶数求模)
4、存放key和value在桶内。

其取值过程是：
1、得到key
2、通过hash函数得到hash值
3、得到桶号(一般都为hash值对桶数求模)
4、比较桶的内部元素是否与key相等，若都不相等，则没有找到。
5、取出相等的记录的value。