在C中实现类似于查表函数的最佳*方法?

如果速度超超必要,那么我会考虑 perfect hashing . 否则,我将使用字符串对的数组/向量,按排序顺序静态创建,并使用二进制搜索。我还编写了一个小测试程序来检查是否满足了速度和内存限制。

制作一个快速计算的密钥,并进行哈希运算

很少的 “key”字符串中选定的字符(带有固定索引)可以获得唯一值(值K)。从中,通过为每个“key”字符串使用预先计算的“K”值,将“value”字符串插入哈希表。

虽然 搞砸 方法很快,仍然存在冲突的可能性(两个输入生成相同的哈希值)。快速方法取决于输入的数据类型。

对于整数类型,最快的表查找方法是数组。使用传入的数据作为数组的索引。这种方法的一个问题是,为了获得最快的速度,数组必须考虑整个值谱。否则,通过将原始索引转换为数组的索引(有点像散列方法),执行会变慢。

对于字符串输入类型,嵌套查找可能最快。一个例子是按长度拆分表格。第一个数组返回指向要根据长度搜索的表的指针,例如char*sub_table=first_array[5]表示长度为5的字符串。这些指针可以配置为专门的输入数据。

另一种方法是使用B-树,这是一个“页面”的二叉树。行为类似于嵌套数组。

如果您告诉我们输入类型,我们可以更好地回答您的问题。