c字符串比较与哈希比较
我需要将一个字符串与c中的多个其他常量字符串进行比较。 我很好奇哪个更快，散列我要比较的字符串并将其与所有其他常量字符串哈希进行比较，或者只是将字符串作为字符串进行比较。 先感谢您
谢谢你的答案，我将做很多比较。 任何人都可以给我一个好的，快速的，低资源密集型的算法吗？ 我所知道的唯一哈希是MD5，我有一种过度杀戮的感觉。
我还想补充一点，字符串最大可能是20或30个字符，大多数是7左右。
比较是进行一次还是多次？ 如果比较只进行一次，那么你最好做一个直接比较。 如果你需要将很多字符串与这组常量字符串进行比较，那么从长远来看，你可以通过使用哈希来节省时间。
这是一个足够简单的问题，您可以轻松地以两种方式编写它，并查看哪种方法更适合于一组有代表性的输入。
如果您尝试将主题字符串与一组其他字符串进行匹配，则可以考虑使用Aho-Corasick字符串匹配算法 。 它使用trie在一次传递中将主题与所有目标字符串进行匹配（实现起来也非常简单）。
很难领先，字符串哈希函数是O（n）。 字符串比较也是O（n），较小的哦。 如果您可以存储计算的哈希值并重复使用它们，那么您只会领先一步。 对彼此而言。
这里有简单的样本C哈希函数。
哈希值的相等性并不能保证平等 – 不匹配会保证不平等。 如果你需要将很多字符串与你的集合进行比较，那么哈希就会很棒 – 如果它是一次性的比较（不太可能我猜），那么strcmp会做得很好。
我想如果你有一个静态的字符串列表，我会将它们存储在一个有序数组中，然后使用bsearch来确定字符串是否在该列表中。 如果它不存在，则返回NULL;如果存在，则返回指向值的指针，并且可能比线性搜索或散列更快。
#include #include #include /* cmp function for qsort and bsearch */ static int pstrcmp(const void *a, const void *b) { return strcmp(*(char * const *)a, *(char * const *)b); } /* check an input against the list of known strings */ static char *check_for_match(char *input) { static char *static_list[] = { "one", "two", "three", "four", "five" }; static int nelems; /* this sorts the list, for demonstration purposes, but if the list is static then it could be sorted prior to compiling */ if (! nelems) { nelems = sizeof(static_list) / sizeof(*static_list); qsort(static_list, nelems, sizeof(*static_list), pstrcmp); } return bsearch(&input, static_list, nelems, sizeof(*static_list), pstrcmp); } int main(int argc, char *argv[]) { if (check_for_match("should_not_match")) { printf("Match found.\n"); } else { printf("No match found.\n"); } if (check_for_match("two")) { printf("Match found.\n"); } else { printf("No match found.\n"); } return EXIT_SUCCESS; }
这取决于。 什么是哈希算法？ 琴弦有多长？ 什么是平台？
另请注意，匹配的哈希不保证匹配的字符串。
如果在编译时知道常量字符串，请查看“完美散列”的概念。
维基百科：集合S的完美哈希函数是一个哈希函数，它将S中的不同元素映射到不同的整数，没有冲突。
那种“没有碰撞”的东西可以拯救你的工作。 进一步阅读和实施的可能性是：
- cmph – http://cmph.sourceforge.net/
- gperf – http://www.gnu.org/software/gperf/
它在很大程度上取决于字符串的长度和哈希函数的复杂性。 实施和基准测试自己将是最好的答案……
另一种可行的方法是将常量字符串排序并对字符串进行二分法搜索，这样您最多只能进行log2(n)比较（例如，对于1024个字符串仅进行10次比较，对于1000000只进行20次比较）字符串）。 我不知道它是否适用于你的问题，但我用这种方法取得了很好的效果。 哈希很难做到正确，角落案件可能变得非常讨厌，而密钥的计算通常会非常昂贵。
谢谢你的答案，我将做很多比较。 任何人都可以给我一个好的，快速的，低资源密集型的算法吗？ 我所知道的唯一哈希是MD5，我有一种过度杀戮的感觉。
Murmur哈希简单，快速，在统计测试中表现良好。