c - 将整数映射到整数的理想数据结构？

Question

我不会详细介绍，但我正在尝试实现类似于 Boyer-Moore-Horspool algorithm 的算法，仅使用十六进制颜色值而不是字符(即范围更大)。

按照维基百科上的例子，我最初是这样的:

size_t jump_table[0xFFFFFF + 1];
memset(jump_table, default_value, sizeof(jump_table);

但是，0xFFFFFF 显然是一个巨大 数字，这很快会导致 C 发生段错误(但不是堆栈溢出，令人失望)。

基本上，我需要的是一个高效的关联数组，将整数映射到整数。我正在考虑使用哈希表，但对每个条目都有一个 malloc'd 结构对我来说似乎太过分了(我也不需要生成哈希，因为每个键都是一个唯一的整数，并且不能有重复的条目)。

有没有人有任何替代建议？我对此是否过于务实？

更新

对于那些感兴趣的人，我最终通过 uthash 使用了一个哈希表图书馆。

Answer 1

0xffffff 太大而不能放在大多数系统的堆栈上，但是您绝对可以 malloc 那个大小的缓冲区(至少在当前的计算机上；不是这样很多在智能手机上)。您是否应该为此任务执行此操作是一个单独的问题。

编辑:根据评论，如果您预计除了“此颜色未出现在输入中”跳过值之外，常见情况的条目数量相对较少，您应该可能只是继续使用 HashMap (显然只存储实际出现在输入中的值)。

(忽略前面对其他数据结构的讨论，这是基于对正在讨论的算法的错误记忆——你想使用哈希表)