各语言标准库实现简记

sort

Golang

大体思路是：

• 先算出 maxDepth = logN，在递归次数不超过 maxDepth 的情况下：
  • 数据量>12 使用快排。
    • 快排本身取 Pivot 哨兵时不采用随机取，而是用 Tukey’s ninther 算法取数组中位数。
  • 否则数据量小一点先使用希尔排序，再插入排序。
• 当递归次数超过 maxDepth 时，这时对当前数组进行堆排序。因为这种数据分布一般就是基本有序的。比如Leetcode 912.排序数组最后的几个测试用例，全 2 或者倒序，快排会达到$O(N^2)$的时间复杂度。

以上参考自
https://boilingfrog.github.io/2022/03/06/go中的sort包/

C++

STL 的 sort 算法与 Golang 基本一致，同样是：

• 快排递归分段。
• 一旦分段后的数据量<16，为避免 QuickSort 快排的递归调用带来过大的额外负荷，就改用插入排序。
• 如果递归层次过深，改用堆排序。
  

hashmap

rehash 方法

• 渐进式 Rehash：这是一种常用的技术，旨在通过将 rehash 的过程分散到多个操作中来减轻单次操作的负担。在这种方式下，不是一次性完成整个哈希表的 rehash，而是在数据结构的每次访问（包括插入、删除、查找等）时逐步进行。这可以有效地平摊 rehash 的成本，避免任何单一操作成为性能瓶颈。举例有 redis。
• 分段锁：对于线程安全的哈希表实现，采用分段锁而不是对整个表加锁可以提高并发性能。这种方法允许多个线程同时对不同的段进行读写操作，减少了锁竞争带来的开销。