4. 内存数据结构选型：数组 vs 哈希表 vs 跳表 vs 红黑树，针对因子查询的缓存友好设计

在量化因子评分接口中，内存数据结构的选择直接决定了查询延迟的稳定性与上限。因子查询通常具有以下特征：键值对访问（因子ID → 评分）、范围扫描（时间窗口内的因子序列）、高并发读（数千路策略同时查询）。本章从缓存行利用、分支预测、内存随机访问三个维度，对比四种经典数据结构的适用场景。

4.1 四种数据结构核心差异

4.2 缓存友好设计原则

现代CPU的L1缓存行大小为64字节，一次内存加载可连续读取8个64位整数。因子评分接口的缓存友好设计应遵循以下原则：

• 紧凑存储： 将因子ID、时间戳、评分打包为固定长度的结构体，避免指针间接引用。
• 顺序访问： 批量查询时按内存地址递增顺序遍历，最大化硬件预取效果。
• 避免随机指针： 链表、树结构中的next/left/right指针会导致缓存行跳跃，每次访问都可能触发cache miss。
• 结构体对齐： 将热点字段放在结构体前64字节内，确保一次加载即可获取完整查询所需数据。

// 缓存友好型因子评分结构体（64字节对齐）
struct alignas(64) FactorScore {
    uint32_t factor_id;      // 4字节
    uint32_t timestamp_sec;  // 4字节
    double    score;         // 8字节
    uint8_t   quality_flag;  // 1字节
    uint8_t   padding[47];   // 填充至64字节
};
static_assert(sizeof(FactorScore) == 64, "Must be cache line aligned");

4.3 数组：因子查询的默认首选

当因子ID可以映射为连续整数索引（如0~N-1）时，数组是延迟最低的数据结构。原因如下：

• 一次内存加载可获取连续多个因子评分，适合批量评分计算。
• 无哈希计算开销，无指针跳转，无树旋转。
• 编译器可自动向量化（SIMD）数组遍历操作。

4.4 哈希表：动态因子集的折中方案

当因子ID无法映射为连续索引（如字符串ID、UUID），且需要频繁插入/删除时，哈希表是合理选择。但需注意以下性能陷阱：

• 缓存行利用率低： 每个桶存储链表头指针，访问时先跳转到桶位置，再沿链表遍历，每次节点访问都可能触发cache miss。
• 哈希计算开销： 每次查询需计算哈希值，在低延迟场景下可能占总延迟的20%~30%。
• 扩容抖动： 负载因子超过阈值时触发rehash，导致毫秒级延迟尖峰。

// 开放寻址法哈希表（连续内存，缓存友好）
template<typename Key, typename Value, size_t Capacity>
class OpenAddressingHashTable {
    struct Entry {
        Key   key;
        Value value;
        bool  occupied = false;
    };
    Entry entries_[Capacity];  // 连续数组，非链表
    
    size_t probe(const Key& key) const {
        size_t idx = std::hash<Key>{}(key) % Capacity;
        while (entries_[idx].occupied && entries_[idx].key != key) {
            idx = (idx + 1) % Capacity;  // 线性探测
        }
        return idx;
    }
};

4.5 跳表与红黑树：仅当需要有序范围查询时引入

跳表和红黑树都维护了有序序列，支持 lower_bound / upper_bound 范围查询。但在因子评分场景中，它们的缓存性能远不如数组：

• 跳表： 每层索引节点随机分布，高层索引的跨度大，访问时几乎每次都是cache miss。但实现简单，无旋转/重平衡开销。
• 红黑树： 树节点在内存中离散分配，左右子树指针导致遍历路径不可预测。插入/删除时的旋转操作会修改多个节点的指针，进一步污染缓存。

4.6 选型决策流程

1. 因子ID是否可映射为连续索引？
   • 是 → 使用数组（延迟最低，缓存最友好）
   • 否 → 进入下一步
2. 是否需要有序范围查询？
   • 否 → 使用开放寻址哈希表（连续桶数组）
   • 是 → 进入下一步
3. 插入/删除频率如何？
   • 低（初始化后只读） → 使用排序数组 + 二分查找
   • 高（运行时频繁增删） → 使用跳表（实现简单，无旋转开销）

4.7 实战：因子评分缓存行优化示例

以下代码展示如何将因子评分按时间窗口组织为连续内存块，实现批量查询时的缓存友好访问：

// 时间窗口因子评分缓存（连续内存，缓存行对齐）
class FactorScoreCache {
    static constexpr size_t kMaxFactors = 1024;
    static constexpr size_t kTimeWindow = 256;  // 256个时间片
    
    // 内存布局：[time_slice][factor_id] → 连续存储
    alignas(64) double scores_[kTimeWindow][kMaxFactors];
    
public:
    // 批量查询：同一时间片的所有因子评分（顺序访问，硬件预取友好）
    void batch_query(uint32_t time_slice, double* out, size_t count) {
        const double* src = scores_[time_slice];
        for (size_t i = 0; i < count; ++i) {
            out[i] = src[i];  // 连续内存，编译器自动向量化
        }
    }
    
    // 单因子时间序列查询（跨步访问，需手动prefetch）
    void time_series_query(uint32_t factor_id, double* out, size_t window) {
        for (size_t t = 0; t < window; ++t) {
            // 手动预取下一个时间片的同一因子
            __builtin_prefetch(&scores_[t + 4][factor_id], 0, 1);
            out[t] = scores_[t][factor_id];
        }
    }
};