C语言中静态可优化稀疏键值存储的实现方案咨询

针对16位无符号整数作为类别键、编译时筛选子集、内存严格匹配实际使用量的需求，这里给出两种高效的C语言实现方案：

方案一：排序数组+二分查找（最简实用） #

这种方案利用编译时宏定义筛选子集，生成排序后的静态数组，通过二分查找实现查询，内存占用完全等于选中键值对的总大小，无任何冗余。

实现步骤 #

1. 定义全量类别：用宏枚举所有可能的键值对
2. 筛选编译时子集：通过注释/宏开关选择需要包含的类别
3. 生成静态排序数组：编译时直接生成已排序的键值对数组
4. 二分查找查询：实现O(log n)时间复杂度的查询函数

代码示例

#include <stdint.h>
#include <stddef.h>

// 全量类别定义：键为16位无符号整数，值为对应字符串
#define ALL_CATEGORIES \
    X(0x0001, "Apple") \
    X(0x0003, "Banana") \
    X(0x000A, "Cherry") \
    X(0x0100, "Date") \
    X(0x0200, "Elderberry")

// 编译时选中的子集：取消注释即可移除对应类别
#define SELECTED_CATEGORIES \
    X(0x0001, "Apple") \
    // X(0x0003, "Banana") \
    X(0x000A, "Cherry") \
    X(0x0100, "Date")

// 键值对结构体
typedef struct {
    uint16_t key;
    const char* value;
} CategoryKV;

// 生成静态排序数组（必须保证键已按升序排列，GCC可加__attribute__((sorted))做编译检查）
static const CategoryKV category_map[] = {
    #define X(key, val) {key, val},
    SELECTED_CATEGORIES
    #undef X
};
static const size_t category_map_size = sizeof(category_map) / sizeof(CategoryKV);

// 二分查找查询函数
const char* get_category_name(uint16_t key) {
    int low = 0;
    int high = (int)category_map_size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (category_map[mid].key == key) {
            return category_map[mid].value;
        } else if (category_map[mid].key < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return NULL; // 未找到匹配键
}

优势 #

• 内存占用极致精简，完全匹配选中的键值对数量
• 无运行时初始化开销，数组在编译时就已确定
• 实现简单，二分查找的性能对于16位键的子集来说完全够用

方案二：编译时哈希表（O(1)级查询） #

如果需要更高效的查询速度（接近O(1)），可以借助编译时哈希计算，生成静态哈希表，避免运行时的哈希计算开销，同时保证内存占用仅为选中键值对+哈希桶的大小。

实现思路 #

1. 用编译时哈希函数（如FNV-1a）为每个键计算哈希值
2. 生成静态哈希表条目，用链地址法处理编译时可预见的哈希冲突
3. 生成哈希桶数组，指向对应桶的第一个条目
4. 实现直接通过哈希桶定位的查询函数

代码示例（基于简单取模哈希，也可替换为编译时FNV哈希）

#include <stdint.h>
#include <stddef.h>

// 全量类别定义同方案一
#define ALL_CATEGORIES \
    X(0x0001, "Apple") \
    X(0x0003, "Banana") \
    X(0x000A, "Cherry") \
    X(0x0100, "Date") \
    X(0x0200, "Elderberry")

// 选中子集同方案一
#define SELECTED_CATEGORIES \
    X(0x0001, "Apple") \
    X(0x000A, "Cherry") \
    X(0x0100, "Date")

// 哈希表条目结构体：next字段用非0索引表示下一个冲突条目（0为空）
typedef struct {
    uint16_t key;
    const char* value;
    uint16_t next;
} HashTableEntry;

// 编译时生成的哈希表（手动处理冲突，或用脚本自动生成）
static const HashTableEntry hash_table[] = {
    {0x0001, "Apple", 0},
    {0x000A, "Cherry", 0},
    {0x0100, "Date", 0}
};
static const size_t hash_table_size = sizeof(hash_table) / sizeof(HashTableEntry);

// 哈希桶数组：索引为哈希值，值为对应桶的第一个条目索引（+1，避免0作为空值）
#define BUCKET_COUNT 16
static const uint16_t hash_buckets[BUCKET_COUNT] = {
    3,  // 0x0100 % 16 = 0 → 指向索引2
    1,  // 0x0001 % 16 = 1 → 指向索引0
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    2,  // 0x000A %16 =10 → 指向索引1
    0,
    0,
    0,
    0,
    0
};

// 查询函数
const char* get_category_name(uint16_t key) {
    uint16_t hash = key % BUCKET_COUNT;
    uint16_t idx = hash_buckets[hash];
    while (idx != 0) {
        idx--; // 转换为数组实际索引
        if (hash_table[idx].key == key) {
            return hash_table[idx].value;
        }
        idx = hash_table[idx].next;
    }
    return NULL;
}

优势 #

• 查询速度接近O(1)，适合频繁查询的场景
• 内存占用可控，仅比方案一多了哈希桶数组的开销
• 完全静态分配，无运行时内存操作

额外建议 #

• 编译时校验：可以添加宏断言，确保选中的子集都来自全量类别，避免键值拼写错误
• 排序检查：方案一中可给数组添加__attribute__((sorted))属性，让GCC在编译时检查数组是否按键排序，避免逻辑错误
• 脚本辅助：如果类别数量较多，可写Python脚本自动生成排序数组或哈希表代码，减少手动维护成本

内容的提问来源于stack exchange，提问作者sdbbs