unordered_map性能被吊打！我用基数树让内存池性能暴涨几十倍的秘密
哈喽，大家好，我是小康！今天要和大家聊一个特别有意思的话题——基数树。
说实话，我第一次听到这个名词的时候，内心是懵逼的。基数？树？这玩意儿到底是啥？
直到有一天，我在研究TCMalloc内存池源码的时候，发现了一个神奇的现象：为什么Google的工程师不用std::unordered_map来做页号映射，而要自己实现一个看起来很复杂的数据结构？
带着这个疑问，我深入研究了一下，结果发现了一个宝藏——基数树！
一个让我震惊的性能对比
先来看个数据，直接震撼你的小心脏：
测试场景：100万次查找操作
std::unordered_map： 40878微秒
基数树： 714微秒
性能提升： 57.2521倍！这还只是中等规模的测试，在大规模场景下，差距会更加夸张。
基数树到底是个啥玩意儿？
好，现在我用最通俗的话给大家解释一下基数树。
简单粗暴地说，基数树就是一个超级大数组！
没错，就这么简单。
比如你要存储键值对，传统的做法是：
[*]std::map：用红黑树，需要比较、旋转，O(log n)时间
[*]std::unordered_map：用哈希表，需要计算哈希、处理冲突，平均O(1)但有常数开销
而基数树呢？直接把键当作数组的下标！
// 传统方式
unordered_map = ptr;// 需要计算hash(123)，可能还要处理冲突
// 基数树方式
array = ptr; // 直接访问！O(1)且常数极小是不是超级简单？
动手实现一个基数树（一级）
talk is cheap，show me the code！
const uint32_t MAX_KEY = (1
页:
[1]