代码

#include "router.h"
#include <unordered_map>
#include <cstdint>

// 使用一个全局的哈希表来存储路由表项
// key: (addr << 8) | len  (因为 len 的范围是 0~32，占用 6 个 bit，左移 8 位足够避免冲突)
// value: nexthop
static std::unordered_map<uint64_t, unsigned> routing_map;

void init(int n, int q, const RoutingTableEntry *a) {
    // 清空并预留空间，减少哈希表动态扩容带来的开销
    routing_map.clear();
    routing_map.reserve(n);
    
    for (int i = 0; i < n; ++i) {
        // 构造哈希表的 key
        // addr 是大端序，直接作为整数参与位运算是安全的，
        // 因为大端序的高位在内存低地址，与 IP 前缀从左到右的顺序一致。
        uint64_t key = (static_cast<uint64_t>(a[i].addr) << 8) | a[i].len;
        routing_map[key] = a[i].nexthop;
    }
}

unsigned query(unsigned addr) {
    // 从最长前缀 (32) 开始向下匹配到默认路由 (0)
    for (int len = 32; len >= 0; --len) {
        // 提取前 len 位的前缀
        // 当 len = 0 时，mask = 0，prefix = 0
        // 当 len = 32 时，mask = 0xFFFFFFFF，prefix = addr
        unsigned mask = (len == 0) ? 0 : (0xFFFFFFFFU << (32 - len));
        unsigned prefix = addr & mask;
        
        // 在哈希表中查找
        uint64_t key = (static_cast<uint64_t>(prefix) << 8) | len;
        auto it = routing_map.find(key);
        if (it != routing_map.end()) {
            return it->second;
        }
    }
    
    // 未找到匹配项，返回 0
    return 0;
}

评测结果