• 1、C++ vector是如何实现扩容的？
• 2、priority_queue底层是怎么实现的？（堆）
• include 和queue不同的地方在于能自定义数据的优先级，默认是大顶堆。
  • 3、priority_queue插入一个元素，底层怎么做的？
  • 4、Vector和List的区别
  • 5、队列和栈的区别和用途
  • 6、哈希表，哈希冲突怎么解决
  • 7、map和unordered_map区别及其优缺点
  • 8、HashMap的负载因子为什么是0.75
  • 9、map和set的区别

1、C++ vector是如何实现扩容的？

为什么以两倍进行扩容？

倍数方式空间拷贝数据次数

假设总共有n个元素，以m倍的形式增长。（比如现在举例n=100， m=2），所以，vector的push_back的操作次数可以是logmN，也就是log2(100)，换算下来大概是需要进行7次扩容。这样的话，相当于旧空间数据到原空间数据的拷贝有7次。

个数方式空间拷贝数据次数

和倍数方式假设相同，n=100；这次m代表的是每次新空间的大小位n+m；m为新空间新增大小，比如这次m为10（每次新增10个空间）。所以这次的扩容次数为 100/10 = 10次，也就是说，插入100白个元素，需要扩容10次。

但是，如果n=1000的情况下， 以个数形式进行扩容就不能在为10了，否则拷贝空间次数将会太多

有的小伙伴要问：但是可以取100呀，想想，如果n=10的情况下，取100又不太合适，所以，以个数的形式来进行扩容显然不符合所用n的取值。

所以在STL中vector以倍数的形式进行扩容

2、priority_queue底层是怎么实现的？（堆）

//升序队列 
priority_queue <int,vector<int>,greater<int> > q; //小顶堆
//降序队列 
priority_queue <int,vector<int>,less<int> >q; //大顶堆

include 和queue不同的地方在于能自定义数据的优先级，默认是大顶堆。

3、priority_queue插入一个元素，底层怎么做的？

优先队列

堆实际上是一棵完全二叉树，底层元素从左到右填入，所以堆的高度为logN，因为完全二叉树的规律性，堆其实可以看作是一个数组，在这个数组中，父节点位于 i /2 位置，则左子节点则在 2i位置，右子节点在 2i + 1上

让堆操作快速执行的性质是堆序性，最小元位于根上，在一个堆中，对于每一个节点X，X的父亲小于或者等于X，根节点除外。

void insert(AnyType x) 
{
    //判断当前堆（数组）是否已满，满则扩容，防止数组越界
    if(currentSize == array.length -1)
        enlargeArray(array.length * 2 + 1);

    //将要插入的元素放在最后一个叶子节点，即数组最后一个元素的位置
    int hole = ++currentSize;

    //父节点 ：hole / 2 
    //左子节点：2*hole
    //右子节点：2*hole+1
    //x和父节点比较，比父节点大则上滤，原父节点下滤
    for(array[0] = x ;x.compareTo(array[hole/2]) < 0 ; hole/=2)     
    {
        array[hole] = array[hole / 2];
    }
    //最后再将要插入的值赋值过去符合的节点处
    array[hole] = x;
}

4、Vector和List的区别

数组插入和删除操作的时间复杂度是O(n)。而数组是有序的，可以直接通过下标访问元素，十分高效，访问时间复杂度是O(1)（常数时间复杂度）。

如果某些场景需要频繁插入和删除元素时，这时候不宜选用数组作为数据结构。

• 频繁访问的场景下，可以使用数组。

• 频繁插入或删除的场景用链表

5、队列和栈的区别和用途

队列是先进先出，栈是后进先出，都是线性存储结构。

6、哈希表，哈希冲突怎么解决

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希冲突：

1. 开放地址方法

一旦发生了冲突，就去寻找下一个空的散列地址。

线性探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。　

再平方探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

伪随机探测

按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

1. 链式地址法（HashMap的哈希冲突解决方法）

对于相同的值，使用链表进行连接，使用数组存储每一个链表。

1. 建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

1. 再哈希法

再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

7、map和unordered_map区别及其优缺点

map和unordered_map这两种字典结构都是通过键值对（key-value）存储数据的，键（key）和值（value）的数据类型可以不同。但是字典中的key只能存在一个，即必须唯一（如果不唯一，则被称为multimap）。上述这点保证了值（value）可以直接通过键（key）来访问，这便是字典结构最为便捷之处。

底层实现的数据结构不同

数据结构其实是两种类型最为根本的区别，其他的不同都是这种区别产生的结果。

• map是基于红黑树结构实现的。红黑树是一种平衡二叉查找树的变体结构，它的左右子树的高度差有可能会大于 1。所以红黑树不是严格意义上的平衡二叉树AVL，但对之进行平衡的代价相对于AVL较低， 其平均统计性能要强于AVL。红黑树具有自动排序的功能，因此它使得map也具有按键（key）排序的功能，因此在map中的元素排列都是有序的。在map中，红黑树的每个节点就代表一个元素，因此实现对map的增删改查，也就是相当于对红黑树的操作。对于这些操作的复杂度都为O(logn)，复杂度即为红黑树的高度。
• unordered_map是基于哈希表（也叫散列表）实现的。散列表是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。散列表使得unordered_map的插入和查询速度接近于O(1)（在没有冲突的情况下），但是其内部元素的排列顺序是无序的。

插入和查询的时间复杂度不同

• map：基于红黑树，复杂度与树高相同，即O(logn)。
• unordered_map：基于散列表，复杂度依赖于散列函数产生的冲突多少，但大多数情况下其复杂度接近于O(1)。

效率及其稳定性不同

这点实际上也是由底层的数据结构决定的。

1. 存储空间：unordered_map的散列空间会存在部分未被使用的位置，所以其内存效率不是100%的。而map的红黑树的内存效率接近于100%。
2. 查找性能的稳定性：map的查找类似于平衡二叉树的查找，其性能十分稳定。例如在1M数据中查找一个元素，需要多少次比较呢？20次。map的查找次数几乎与存储数据的分布与大小无关。而unordered_map依赖于散列表，如果哈希函数映射的关键码出现的冲突过多，则最坏时间复杂度可以达到是O(n)。因此unordered_map的查找次数是与存储数据的分布与大小有密切关系的，它的效率是不稳定的。

优缺点及适用场景

1. map：
2. 优点：
   • map元素有序（这是map最大的优点，其元素的有序性在很多应用中都会简化很多的操作）
   • 其红黑树的结构使得map的很多操作都可在O(logn)下完成
   • map的各项性能较为稳定，与元素插入顺序无关
   • map支持范围查找
3. 缺点：
   • 占用的空间大：红黑树的每一个节点需要保存其父节点位置、孩子节点位置及红/黑性质，因此每一个节点占用空间大
   • 查询平均时间不如unordered_map
4. 适用场景：
   • 元素需要有序
   • 对于单次查询时间较为敏感，必须保持查询性能的稳定性，比如实时应用等等
5. unordered_map
6. 优点：
   • 查询速度快，平均性能接近于常数时间O(1)
7. 缺点：
   • 元素无序
   • unordered_map相对于map空间占用更大，且其利用率不高
   • 查询性能不太稳定，最坏时间复杂度可达到O(n)
8. 适用场景：
   • 要求查找速率快，且对单次查询性能要求不敏感

8、HashMap的负载因子为什么是0.75

1、负载因子是1.0

当负载因子是1.0的时候，也就意味着，只有当数组的8个值（这个图表示了8个）全部填充了，才会发生扩容。这就带来了很大的问题，因为Hash冲突时避免不了的。当负载因子是1.0的时候，意味着会出现大量的Hash的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。

2、负载因子是0.5

负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。

但是，这时候空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。

一句话总结就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。

3、负载因子0.75

经过前面的分析，基本上为什么是0.75的答案也就出来了，这是时间和空间的权衡。当然这个答案不是我自己想出来的。答案就在源码上.

大致意思就是说负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

9、map和set的区别

​ map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。

map和set区别在于：

（1）map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；

​ Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

（2）set的迭代器是const的，不允许修改元素的值

     **map允许修改value，但不允许修改key**

​ 其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

（3）map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。