c - C 中小型数据集 HashMap 的替代方案

Question

我目前正在为 particle simulator 开发命令行界面.它的解析器采用以下格式读取输入:

[命令] [参数]*(-[标志] [标志参数])

目前，命令是通过条件 block 发送的，对比各种已知命令及其对应的数据包，发送给匹配函数。然而，这看起来笨拙、低效且不优雅。

我正在考虑改用散列图，将命令的字符串表示形式作为键，将函数指针作为值。然后，引用的函数将被发送一个包含参数、标志等的数据包。

在这种情况下，散列映射是否过大？实现一项所需的额外基础设施是否超过了潜在的好处？我的目标是速度、优雅、功能，而且，因为这是一个开源项目，还有可扩展性。

感谢您的帮助。

Answer 1

您可能需要考虑 Ternary Search Tree .它具有良好的性能，有效地利用存储；而且您不需要哈希函数或冲突策略。

链接的 Bentley/Sedgwick 文章是对随附的 C 源代码的非常详尽且可读的解释。

在我的 postscript 解释器的过去 3 个版本中，我一直在使用 TST 进行名称查找。唯一需要的更改是由于内存管理的更改。 Here's a version我(轻轻地)修改为使用显式指针。我在 postscript interpreter 中使用了另一个版本，任何 xpost2*.zip 版本，在文件 core.c 中，它使用字节偏移量作为指针(必须添加到用户内存字节指针以产生一个真正的指针) .