c - 从单个字符到指针的映射的纯 C 实现

Question

我有高级语言的编程经验，几周前开始使用纯 C 编写代码(出于学术原因)。我想实现一个类似 map<char,myStruct*> 的数据结构.

如果这还不够清楚:我想要每个可能的 SINGLE char 的“映射”指向我在其他地方定义的结构的指针。如果有办法确保没有 2 char s 可以指向相同的 struct (在将新元素插入 map 时不检查所有其他 char)这很整洁，但这不是绝对必要的。我还需要能够从 map 中删除配对，并重新插入具有相同键但不同指针的配对。

我仔细考虑了这一点，并认为我可以创建一个所有可能字符长度的指针数组，并使用该字符作为数组索引存储相应的指针(因为它只是一个数字常量)。这可能非常有效，但如果我最终在我的应用程序中只使用几个字符，那么为地址分配那么多空间似乎效率很低。

不过，我还是想不出任何替代解决方案(考虑到我是 C 新手，这并不奇怪)。我将不胜感激任何正确方向的建议，即使是模糊的建议。

Answer 1

正如您所说(以及一位评论者所建议的)，最简单的方法就是创建一个静态大小等于字符数据类型最大值的数组:

#include <limits.h>
void * mapping[1u << CHAR_BIT];

假设 64 位指针和 8 位 char，这将占用整个映射的 8 * 256 = 2,048 字节内存(当然不包括“用户数据”，这是你店铺)。对于在 64 位系统上运行的程序，2 KB 的内存是微不足道的，在我看来，实现的简便性和由此获得的速度应该可以很好地平衡浪费的内存。

如果您仍想限制数组的“物理”大小，最简单的做法是对单个字符进行哈希处理，但随后您需要开始处理哈希冲突，这会立即使事情变得更加复杂。

你可以这样做:

struct ValueChain
{
  struct ValueChain *next;
  void *value;
  char key;
}

#define MAP_SIZE 127 /* This should be prime. */
struct ValueChain* mapping[MAP_SIZE];

这里我们将指针数组的大小减半，但每个值的成本都增加了。此外，在插入冲突值时，您将需要动态分配。

您可以通过执行以下操作进一步压缩它

#define MAP_SIZE 31
struct ValueChain mapping[MAP_SIZE];

此处数组中的每个值都是一个完整的 ValueChain“列表标题”，​​而不仅仅是指向一个的指针。在 64 位机器上，这可能会为 mapping 数组使用大约 558 个字节，但是在检测到冲突之前您不需要进行任何动态分配。

我猜，这些散列可能只是 const char key = myChar % MAP_SIZE; 的第一个近似值。