数据结构与算法

7大排序

选择排序：时间复杂度O(n^2) 空间O(1) 不稳定
冒泡排序：时间复杂度：O(n^2)
空间复杂度：O(1) 稳定
插入排序：时间 O(n^2) 空间 O(1) 稳定
桶排序：n是原始数据的规模，m是n个数据中的最大值
时间复杂度：o（n+m）/ o（n）
空间复杂度：o（m）稳定
归并排序：时间 O(nlogn) 空间 O(n) 稳定
堆排序：时间 O(nlogn) 空间 O(1) 不稳定
快排：时间O(nlogn) 最坏O(n)空间 O(1) 不稳定

堆

完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。
每次插入都是将先将新数据放在数组最后，由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中——这就类似于直接插入排序中将一个数据并入到有序区间中。

哈希表

哈希表是一个存储键值对的数据结构。
哈希表是通过key通过一个散列函数加工处理之后得到的一个值，这个值就是数据存放的位置，
哈希冲突
就是其他的key经过哈希函数得到的值，和之前某个key重复了

哈希函数的特征

哈希函数最常用的方法是除留余数法f（key）%m m为表长
int f(string) 输入域无穷大，输出域是有限的
有可能不同的输入，对应相同的输出
如果输入的参数是一样的，输出是一定相同的
均匀性 类似的输入，通过打乱，然后得到均匀

解决方法：

线性探测再散列，先存直到发现冲突的时候，f（key）+1或者+2直到找到不冲突的地方
再哈希法，换一个哈希函数
链地址法
哈希扩容
负载因子
公式为=填入表中的元素个数/哈希表的长度
当负载因子达到0.75时或0.8会触发扩容机制
创建一个两倍大小新的哈希表，
遍历原哈希表中所有元素，并重新计算它们在新表中的位置
将每个元素从旧的哈希表移动到新的哈希表对应位置
动态扩容
将扩容的操作穿插在插入操作中，先申请两倍空间，然后不迁移
插入新数据时，把老的也插入
查找数据的时，现在新的hash表中进行查找，没有在去旧的查找

怎么才算一个好的哈希函数

尽量避免冲突，
只要改动一个字节，其哈希值也会有很大不同
高效性

vector是如何扩容的？

GCC是二倍进行扩容 vs中是1.5倍 扩容需要先新申请一块内存空间，然后把旧内存拷贝过去，并且释放旧内存空间 不仅仅使用pushback容量不够时会扩容，resize时也会扩容。resize传入的参数不仅仅大于size的大小如果也大于容量大小时就会进行扩容

数组和链表

从内存角度来讲的话 数组内存比链表内存所占的空间少 地址连续 链表地址不连续
由上可知 数组的查询数据比链表快 但是链表对于数组来说 删除和添加更快
大小扩展的话 链表比数组更优秀 内存利用率比数组更好 因为数组地址连续 但链表不一样

红黑树和hashmap适用于什么情况

红黑树通常用于需要排序的键值对数据存储，它能够保持数据的有序性以及在插入和删除操作时能够保持对数据结构的平衡，从而保证最坏情况下的时间复杂度为O(log n)。红黑树适用于需要进行范围查询的场景，例如数据库索引、2-3-4树的JVM实现等。
Hashmap是一种以散列为基础的数据结构，适用于快速的查找和访问操作。当不需要数据的排序时，Hashmap是一个很好的选择，因为它的平均时间复杂度为O(1)。然而，当需要排序或者需要保持数据的有序性时，Hashmap就不适用了。
红黑树和Hashmap各自的适用情况是互补的，它们各自在特定的场景下有着优秀的表现。例如，可以使用Hashmap来快速访问，然后当发生冲突时，使用红黑树来维护一个有序的子列表。或者，可以将整个数据集合分割成多个小的子集，每个子集用Hasap管理，同时保留一个索引结构使用红黑树来快速定位子集。

vector list map的区别

vector:

优点 支持随机访问 查询效率快 缺点 往头部或中部插入或删除元素时，为了保持原本的相对次序，插入或删除之后的所有元素都必须移动，所以插入效率比较低
适用场景：适用于对象简单，变化较小，并且频繁随机访问的场景

list

优点：不使用连续的内存进行存储，存储空间无限（只要内存够）。可以在任意位置插入或删除且效率高。
在内部插入、删除很快（不需要进行内存拷贝或者移动，只需要进行指针的更改）
缺点. 随机查找太慢
相比vector 占用内存比较大

map：

优点：使用平衡二叉树实现，便于元素查找，且能把一个值映射成另一个值。
缺点：每次插入都需要调整红黑树，效率有一定影响。
map比vector查找更快（map的内部数据结构用rb-tree实现，而用vector你只能用线性查找，效率很低,也有一种说法，关联式容器拥有自动排序能力，并不意味它们在排序方面的执行效率更高。事实上由于关联式容器每安插一个新元素，都要进行一次排序，所以速度反而不及系列容器经常采用的手

map 和 unordered_map的区别

map：

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

unordered_map：

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

push_back和emplace_back的区别？

首先push_back是先创建一个元素，然后将这个元素拷贝或移动到容器的尾部，整个过程涉及元素的创建，拷贝或移动，以及可能的析构操作。
emplace_back是直接在容器尾部创建元素，省去了拷贝或移动元素的过程。它接受构造函数的参数，并在容器内存中直接构造对象，从而避免了额外的拷贝和移动操作。

红黑树和平衡二叉树

AVL是严格的平衡二叉树，所有节点必须满足左右子树的差绝对值不超过1，AVL树时候用于插入与删除的次数较少，查找多
红黑树是一个弱平衡二叉树，它确保没有一条路径会比其他路径长出两倍，对于搜索，插入删除等操作我们用红黑树