C中的字符串/整数关联

Question

我想用c语言提出以下问题的建议:

我需要这样的字符串和整数之间的关联:

"foo" => 45,
"bar" => 1023,
 etc...

，并且能够使用关联的整数找到字符串，使用关联的字符串找到整数。对于字符串到整数，我可以使用哈希表，但我将失去返回的方式。

一个简单的解决方案，我正在使用，但这是非常慢的是创建一个表:静态param_t参数[]= {{"foo"， 45}，{"bar"， 1023}，…}；并使用两个函数比较每个条目(字符串或整数)以获得字符串或整数。这是非常慢的线性搜索。我可以用什么来让一个搜索算法在0(1)中找到一个字符串，在0(字符串的大小)中找到一个整数?什么好主意吗?

Answer 1

最简单的方法是实现查找表，最好按整数值("主键")排序。

typedef enum
{
  FOO_INDEX,
  BAR_INDEX,
  ...  
  N
} some_t;
const int int_array [] =  // values sorted in ascending order, smallest first
{
  45,
  1023,
  ...
};
const char* str_array [] =
{
  "foo",
  "bar",
  ...
};

现在您可以使用int_array[FOO_INDEX]和str_array[FOO_INDEX]来获得所需的数据。

由于这些是在编译时设置的常量表，因此可以对数据进行排序。所有的查找都可以用二进制搜索来完成，O(log n)。如果你有整数值，但需要知道索引，在int_array上执行二进制搜索。一旦找到了索引，就可以从那里进行即时查找。

要使其工作，两个数组必须具有确切的大小N。要确保数组大小和这些数组中的数据完整性，请使用编译时断言:

static_assert(sizeof(int_array)/sizeof(*int_array) == N, "Bad int_array");
static_assert(sizeof(str_array)/sizeof(*str_array) == N, "Bad str_array");

Answer 2

首先用qsort排序您的列表，然后使用bsearch查找项目。它不是O(1)但至少是O(log(n))

Answer 3

使用两个哈希映射。一个用于从整数到字符串的关联，另一个用于从字符串到整数的关联

Answer 4

一种低效的方法是将其转换为256进制。第一个字母ascii乘以256的0(1)次方加上第二个字母ascii乘以256的1次方，以此类推。非常低效(因为long是不够的，所以要么在另一个字符串中包含数字，要么使用数学C库。我知道Ruby和Perl中有散列它基本上是一个数组，你可以用一个特定的键(可以是字符串)但我不知道它是如何工作的