面试过程中被问懵
高并发内存池中基数数相比哈希表差别，优势在哪
相比传统的哈希表（Hash Table），基数树在内存管理这种特定场景下具有压倒性的优势。
哈希表（哈希表）
逻辑：通过哈希函数将 转换为数组下标。
PageID锁定：在高并发环境下，多个线程同时访问哈希表，为了保证线程安全，通常需要加互斥锁或读写锁。即使是采用分段锁，在极高并发下仍会有锁竞争。
确定性：哈希表存在哈希冲突。最坏情况下，查询时间会从$O(1)$退化到$O(n)$。
基数树（Radix Tree）
逻辑：利用位（bits）作为索引进行层级查找。例如，一个三层基数树会将 64 位地址拆分为几部分，逐层定位。
PageID锁定：这是基数树最大的优势——读操作可以做到完全无锁（Lock-free）。在内存池中，映射关系的修改（写）只在申请/释放大块内存时发生，而查询（读）在每次 内存时都会发生。由于基数树结构在修改时可以通过原子操作保证一致性，读操作不需要加锁，极大地提升了并发性能。
free确定性：查询时间复杂度是固定的$O(k)$，其中$k$是树的层数。对于内存池来说，这通常是 2 层或 3 层，查询极其稳定。
基数树的显著优势
A. 彻底规避锁竞争
在内存池中， 函数需要通过指针地址找到它属于哪个 。如果用哈希表，每释放一次内存都要争抢一次锁。而基数树的读操作是天然线程安全的（假设结构已分配），这让 操作的性能接近极致，不会因为并发量增加而导致线性损耗。free(ptr)Spanfree
B. 更好的缓存友好性（缓存局部性）
内存地址通常是连续的。
基数树的结构反映了地址空间的布局。当你访问连续的页面时，它们在基数树中往往位于同一个叶子节点数组内。这使得 CPU 缓存命中率远高于哈希表（哈希表通过 Hash 后的索引是随机离散的）。
C. 内存利用率与空间预分配
哈希表：需要存储键值对（Key-Value），并预留大量桶（Buckets）来降低冲突率。
基数树：多层基数树（Multi-level Radix Tree）可以按需分配。只有当某个地址段被使用时，才会创建对应的子节点。对于 64 位系统，三层基数树能非常优雅地覆盖广阔的虚拟地址空间，而不会像单层数组那样浪费内存。
场景对比总结
| 特性 | 哈希表（哈希表） | 基数树（Radix Tree） |
| 查询耗时 | 平均$O(1)$，不稳定 | 固定$O(k)$，极其稳定 |
| 并发性能 | 需加锁，存在锁竞争 | 读操作无锁，支持极高并发 |
| 内存连续性 | 破坏连续性，缓存不友好 | 符合地址连续性，缓存命中率高 |
| 适用场景 | 键值分布稀疏、无序的通用场景 | 地址空间映射、页表管理 |
为什么内存池选择它？
在内存池的设计中，性能瓶颈往往在“锁”上。
基数树通过将“页号”这种具有天然序数的 Key 转化为树结构，把原本需要的全局同步变成了对固定层级的偏移量计算。
结论：在高并发内存池中，基数树并非为了节省空间（有时反而比哈希表费空间），而是为了稳定、无锁的$O(1)$查询性能，这直接决定了内存分配器在高核 CPU 环境下的吞吐量。