题目

1. hash表的实现，包括STL中的哈希桶长度常数。答案
2. hash表如何rehash，怎么处理其中保存的资源。答案
3. 哈希表的桶个数为什么是质数，合数有何不妥？答案
4. map和set有什么区别，怎么实现的。答案
5. 如何判断一个图是否连通。答案
6. 如何用一个1立方米的方块占满这个小教室。
7. 大区间求和。答案
8. 大文本如何排序
9. 最优二叉树、排序二叉树、哈夫曼树。答案
10. map用的是红黑树，和AVL树的区别？答案
11. map插入和删除需要注意什么？答案
12. B+树，存储方式。答案
13. set底层为什么用红黑树实现？答案
14. map底层为什么用红黑树实现？
15. 各种排序空间复杂度和时间复杂度，稳定程度。答案
16. hashtable是什么，重复元素怎么办，字符串当作hash值如何处理
17. hash用在什么地方？
18. vector，手写扩容代码。答案
19. map和unordered_map怎么实现的以及优缺点。答案
20. vector和deque的底层实现有什么区别。答案
21. emplace_back的实现。答案
22. 迭代器什么时候会失效。答案
23. 介绍迭代器失效。push_back会导致迭代器失效吗。答案
24. 快排算法最差情况推导公式。答案
25. 小根堆特点。答案
26. 增量为5的希尔排序
27. 一致性哈希是如何实现的（单调性、平衡性）。答案
28. 单链表和双向链表了解吗，说一下性能的比较？答案
29. 描述怎么初始化堆。答案
30. 描述怎么合并两个堆。答案
31. map和hashmap的区别，查找的时间复杂度分别是多少？答案

参考答案

1. • 哈希表又称散列表，是根据关键码值直接访问的数据结构。即通过把关键码值映射表中一个位置来访问记录，以加快查找的速度。哈希表的实现主要解决两个问题，构造哈希函数和处理哈希冲突。
   • 构造哈希函数：
     • 哈希函数对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）；
     • 构造哈希函数主要包括直接地址法、平方取中法、除留余数法等。
   • 冲突解决：
     • 现实中的哈希函数不是完美的，当两个不同的输入值对应一个输出值时，就会产生碰撞，这个时候需要解决冲突。
     • 常见解决冲突的办法有：开放定址法、链地址法、建立公共溢出区等。
     • STL中使用的链地址法：为每个Hash值建立一个单链表，当发生冲突时，将记录插入到链表中。
     • 虽然链地址法并不要求哈希桶长度必须为质数，但STL仍然以质数来设计哈希桶长度，并且将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用于查询在这28个质数中，“最接近某数并大于某数”的质数。
       返回原题

2. • 负载因子：哈希表的size/初始化时桶的数量；
   • rehash：当hash表中的负载因子达到负载极限的时候，hash表会自动成倍的增加容量（桶的数量），并将原有的对象重新分配并加入新的桶内。
     返回原题

3. • 可以最大程度地减少冲突概率，使得哈希后的分布更加均匀。如果使用合数，可能会造成很多数据分布集中在某些点上，从而影响哈希表效率。
   • 质数在一般情况下可以抵抗比较差的hash函数，但对于较好的hash函数，不必苛求桶的个数一定是质数。
     返回原题

4. • 共同点：
     • map和set的数据结构相同，底层都是使用红黑树实现的；
     • 内部的元素都不可以重复；
     • 都会对其中的键值进行排序；
     • 不能通过迭代器来改变其键值，因为要保证键值的唯一性和元素的顺序。
   • 不同点：
     • 二者其中的iterator格式不一样，map使用的是pair这种键值/实值配对的数据，使用第一个元素来排序，而set直接使用键值作为元素，以键值来排序；
       返回原题

5. • 使用Warshall算法，时间复杂度为O(v^3)；
   • 拓扑排序
   • 使用DFS（Deep First Search），用visit[]来标志数组，观察从一个点出发能否遍历图中所有的点。
     返回原题

7. • 使用线段树：叶子节点存储输入的数组元素，每一个内部节点表示两个叶子节点的合并（即两个子节点的和）
   • 时间复杂度：构建O(n)，查询O(n)，更新O(log n)。
     返回原题

9. • 最优二叉树（哈夫曼树）：带权路径长度最小的树。
     • 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积；
     • 树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和。
     • 特点：叶子上的权值均相同时，完全二叉树一定是最优二叉树；最优二叉树中，权越大的叶子结点离根越近；最优二叉树的形态不唯一，WPL最小；是严格的二叉树，没有度数为1的分支结点。
   • 哈夫曼算法基本思想：
     • 根据给定的n个权值w1，w2…wn构成n棵二叉树的森林F={T1, T2,…,Tn}，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空；
     • 在森林F中选出两棵根结点权值最小的树，将这两棵树合并成一棵新树（增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子），将这两个孩子的权值之和作为新树根的权值；
     • 对新的森林F重复(2)，直到森林F中只剩下一棵树为止。
   • 排序二叉树：又称二叉搜索树，性质如下：
     • 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
     • 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
     • 它的左右子树也分别为二叉排序树。
       返回原题

10. • 红黑树：红黑树是一种二叉查找树，每个节点增加一个存储位表示节点的颜色，非红即黑。通过对任何一条从根节点到叶子节点着色的方式的限制，红黑树确保没有一条路径的长度会大于其它任一路径长度的两倍。因此，红黑树是一种弱平衡二叉树，相对于AVL树来说，它的旋转次数少，所以对于查找、插入、删除操作较多的情况下，通常使用红黑树。
    • 性质：
      • 每个节点非黑即红；
      • 根节点是黑色的；
      • 每个叶子节点（NIL节点）都是黑色的；
      • 每个红节点的两个子节点都是黑色的；
      • 任一节点到所有叶子节点的路径上的黑色节点数目都相同。
    • AVL树：红黑树是在AVL树的基础上提出来的。平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是二叉平衡树，左右子树的高度差绝对值不超过1。
    • 红黑树相对AVL树的优点：
      • AVL树是高度平衡的，其频繁的插入、删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多二次旋转，删除最多三次旋转；
      • 红黑树的查找、删除、插入操作都是O(logn)，且性能稳定，所以STL中很多结构包括map、set的底层实现都是红黑树。
        返回原题

11. • map的插入：
      • insert方法不能覆盖，如果键已经存在，则插入失败。数组方法插入不存在也会直接更新键对应的值；
    • map的删除：
      • map中删除元素时，只是当前迭代器失效。
        返回原题

12. • 参考：平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
    • B树：B树属于多叉树，又名平衡多路查找树，常用于数据库索引技术中。
      • 排序方式：所有节点的关键字是按递增次序排列，并遵循左小右大原则；
      • 子节点数：非叶子节点的子节点数>1，且<=M，且M>=3，空树除外。（M阶代表一个节点最多有多少个查找路径）
      • 关键字数：枝节点的关键字数量大于等于ceil(M/2)-1个且小于等于M-1个；
      • 所有叶子节点均在同一层，叶子结点除了包含关键字和关键字记录的指针外也有指向其子节点的指针，只不过其指针地址都为null。
    • B+树：是B树的一个升级版，更充分地利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分查找法。看图轻松理解数据结构与算法系列(B+树)
      • B+树非叶子结点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子结点所能保存的关键字大大增加；
      • B+树叶子结点保存了父结点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
      • B+树叶子结点的关键字从小到大排列，左边结尾数据都会保存右边结点开始数据的指针；
      • 非叶子结点的子结点数=关键字数，也有非叶子结点的关键字数=子节点数-1。
        返回原题

13. • 红黑树能以O(log n)的时间复杂度进行搜索、插入、删除捉住，旋转复杂度仅为O(1)，时间复杂度和AVL一样，但统计性能比AVL树更高；
      返回原题

15. 各种排序算法的时间、空间复杂度以及稳定性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

else if (max_size() - size() < _Count)
    //可以申请的最大容量也不够用，抛出异常_THROW(length_error, "vector<T> too long");
    _Xlen();
else if (_Capacity < size() + _Count){//空间不足，需要扩容   
    _Capacity = max_size() - _Capacity / 2 < _Capacity
        ? 0 : _Capacity + _Capacity / 2;    // 尝试扩容1.5倍
    if (_Capacity < size() + _Count)//扩容1.5倍后依然不够用，则容量等于当前数据个数加上新增数据个数
        _Capacity = size() + _Count;
    pointer _Newvec = this->_Alval.allocate(_Capacity);//申请新空间
    pointer _Ptr = _Newvec;
    _TRY_BEGIN
        _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
            _Newvec);   //move原先的数据
    _Ptr = _Ucopy(_First, _Last, _Ptr); //copy新增的数据到新内存之后
    _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);  
    _CATCH_ALL
        _Destroy(_Newvec, _Ptr);
    this->_Alval.deallocate(_Newvec, _Capacity);//释放原来申请的内存
    _RERAISE;
    _CATCH_END
...

返回原题

19. • map：底层是用红黑树实现的，对map的查找、插入、删除等操作都是相当于对红黑树进行的操作。
      • 优点：有序性；红黑树的数据结构使得很多操作在O(log n)时间复杂度就能实现，效率很高；
      • 缺点：空间占用率很高。红黑树的每个节点都需要保存父结点、左右子结点以及红黑性质，使得每个节点都占用大量内存。
    • unordered_map：的底层是哈希表，其元素的排列顺序是无序的。
      • 优点：由于底层是哈希表，因此查找速度非常快；
      • 缺点：哈希表的建立比较耗费时间。
        返回原题

20. • vector的底层实现是数组，是单向开口的连续空间，支持随机访问和尾部快速增删；
    • deque的底层实现是一个中央控制器和多个缓冲区，是双向开口的连续空间。支持随机访问和首尾快速增删。
      返回原题

21. • emplace_back：采用就地构造策略，直接将参数传给对象的构造函数，在容器中构造一个对象，从而实现0拷贝。与push_back相比，当传入左值时，省去了复制操作；当传入右值时，省去了移动操作。
      返回原题

22. • vector：
      • push_back：一定会使end返回迭代器失效；当capacity前后有变化时，first返回的迭代器也会失效；
      • erase/pop_back：会使删除元素及之后的所有迭代器均失效；erase会返回一个新的有效的迭代器。
    • deque：
      • 首尾插入元素不会使任何迭代器失效；
      • 在首尾删除元素只会使指向被删除元素的迭代器失效；
      • 在其他任何位置进行插入和删除将会使该容器元素的所有迭代器失效。
    • list/set/map：
      • 删除元素时，指向该删除节点的迭代器失效；
        返回原题

23. • 迭代器失效：向容器内添加或删除元素的操作可能会使指向容器元素的迭代器失效，失效的迭代器将不指向任何元素。
    • push_back：对于vector的push_back操作，end返回的迭代器会失效，first返回的迭代器只有当当前容器size小于容器的capacity时才不会失效，否则会失效。
      返回原题

24. • 快排最差情况：已排好序；所有值相等（排好序的特殊情况）。
    • 在最差情况下，需要执行n-1次递归调用，且第i次划分需要经过n-i次比较才能找到第i个记录。所以比较次数为(n-1) + (n-2) + ... + 1 = n(n-1)/2，即最终时间复杂度为O(n^2)。
      返回原题

25. • 小根堆特点：所有父结点的值比其左右子结点的值都要小；根结点的值最小；
      返回原题

27. • 参考：理解 Consistent Hashing
    • 一致性哈希是一种特殊的哈希算法，哈希表槽位数（大小）的改变平均只需要对K/n个关键字重新映射，其中K是关键字的数量，n是槽位数量。而在传统哈希表中，删除或添加一个槽位几乎要对所有关键字进行重新映射；
    • 原理：
      • 将每个节点映射到数值空间[0, (2^32)-1]，映射的规则可为IP、hostname；
      • 将每个object映射到数值空间[0, (2^32)-1]；
      • 对于某个object，对于所有满足hash(node)<=hash(object)的节点，选择hash(node)最大的节点存放object；如果没有满足上述条件的节点，选择hash(node)最小的节点存放该object。
    • 特点：当插入或删除时，仅有一个节点的部分object需要重哈希。
    • 平衡性：引入虚节点，虚节点实际上是物理节点的复制品，一个物理节点包含多个虚拟节点，我们将这些虚拟节点映射到数值空间[0, (2^32)-1]，对于某个object，计算出存放的虚拟节点，进而得出物理节点。虚节点越多及其位置分布越均匀，相应地，映射到物理节点的object数目也越均匀，从而提高了平衡性。
      返回原题

28. • 与单链表相比，双向链表有如下特点：
      • 从任一节点出发，可以查找链表中的其他任意节点；
      • 既可以前向遍历，也可以后向遍历；
      • 每个指针域中都增加了一个存储指针的空间，降低了存储密度；
      • 可以在当前结点前或后插入、删除；
        返回原题

29. • 参考：堆排序算法之初始堆建立总结
    • 首先根据序列构建一个完全二叉树；
    • 在完全二叉树的基础上，从最后一个非叶子结点开始调整：比较三个元素的大小（自己、左孩子、右孩子），分为三种情况：
      • 自己最大，不用调整；
      • 左孩子最大，交换该非叶子结点与其左孩子的值，并考察以左孩子为根的子树是否满足大顶堆的要求，不满足递归向下处理；
      • 右孩子最大，交换该非叶子结点与其右孩子的值，并考察以右孩子为根的子树是否满足大顶堆的要求，不满足递归向下处理；
        返回原题

30. • 当两个堆元素数量相差较大时，选用启发时合并，即将较小的堆一个个插入较大的堆中，时间复杂度为O(nlog n)；
    • 当两个堆元素数量相关较小时，选用重新建堆法，全部拆散重排，时间复杂度为O(n1+n2)。
      返回原题

31. • 区别：
      • 构造函数：hashmap需要hash函数，而map只需比较函数；
      • 存储结构：hashmap采用hash表存储，map一般采用红黑树实现。
    • 查找时间复杂度：
      • hashmap：常数级别，为O(1)；
      • map：log(n)。
        返回原题