unordered_map性能被吊打！我用基数树让内存池性能暴涨几十倍的秘密

哈喽，大家好，我是小康！
今天要和大家聊一个特别有意思的话题——基数树。
说实话，我第一次听到这个名词的时候，内心是懵逼的。基数？树？这玩意儿到底是啥？
直到有一天，我在研究TCMalloc内存池源码的时候，发现了一个神奇的现象：为什么Google的工程师不用std::unordered_map来做页号映射，而要自己实现一个看起来很复杂的数据结构？
带着这个疑问，我深入研究了一下，结果发现了一个宝藏——基数树！
一个让我震惊的性能对比

先来看个数据，直接震撼你的小心脏：

1. 测试场景：100万次查找操作
2. std::unordered_map：    40878微秒
3. 基数树：               714微秒
4. 性能提升：             57.2521倍！

复制代码

这还只是中等规模的测试，在大规模场景下，差距会更加夸张。
基数树到底是个啥玩意儿？

好，现在我用最通俗的话给大家解释一下基数树。
简单粗暴地说，基数树就是一个超级大数组！
没错，就这么简单。
比如你要存储键值对，传统的做法是：

• std::map：用红黑树，需要比较、旋转，O(log n)时间
  
• std::unordered_map：用哈希表，需要计算哈希、处理冲突，平均O(1)但有常数开销
  

而基数树呢？直接把键当作数组的下标！

1. // 传统方式
2. unordered_map[123] = ptr;  // 需要计算hash(123)，可能还要处理冲突
4. // 基数树方式
5. array[123] = ptr;          // 直接访问！O(1)且常数极小

复制代码

是不是超级简单？
动手实现一个基数树（一级）

talk is cheap，show me the code！
[code]const uint32_t MAX_KEY = (1