从单个char到指针的映射的Plain C实现

Question

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

如果这还不够清楚:我希望将每个可能的SINGLE"映射" char到指向我在其他地方定义的结构的指针上.如果有一种方法可以确保没有2 char秒可以指向相同的struct(char在将新元素插入地图时不检查其他内容)那将是整洁的,但这不是绝对必要的.我还需要能够从地图中删除配对,并重新插入具有相同键但不同指针的配对.

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

尽管如此,我还是没有想到任何替代解决方案(考虑到我是C新手,不是那么令人惊讶).我会很感激任何,甚至模糊的建议,朝着正确的方向前进.

Answer 1

正如您所说(并且作为评论者建议),最简单的方法是只执行一个静态大小等于字符数据类型的最大值的数组:

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

假设64位指针和8位chars,这将占用整个地图的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位计算机上,这可能会使用大约558个字节的mapping数组,但在检测到冲突之前,您不需要进行任何动态分配.

const char key = myChar % MAP_SIZE;我想,这些的散列可能只是第一次近似.