c字符串比较vs散列比较

另一种可行的方法是将你的常量字符串进行排序并对字符串进行二分搜索，这样最多只能比较log2(n)（例如，对于1024个字符串只能进行10次比较，或者只能进行20次比较1000000个字符串）。我不知道它是否适用于您的问题，但是我用这种方法取得了非常好的效果。哈希是非常难以正确处理的，角落的情况会变得非常糟糕，并且密钥的计算通常会非常昂贵。

来源

2010-08-08 20:00:54

非常感谢你给我答案做了许多比较。可以任何人都给我一个好的，快速的，低密度的资源密集算法使用？我知道的唯一散列是MD5，而我有一种超过杀死的感觉。

Murmur hash简单，快速，在统计测试中表现良好。

来源

2010-08-08 20:10:55

很难领先，字符串散列函数是O（n）。字符串比较也是O（n），以较小的喔。如果您可以存储您计算的散列值并重复使用它们，那么您只能在前面。对彼此而言。

简单示例C哈希函数are here。

来源

2010-08-08 20:11:47

如果您将这一个字符串与多个字符串进行比较，如问题所问？我不认为它仍然是O（n），那将是O（n^2）是吧？ – tushar747 2013-11-06 01:29:59

我想如果你有一个静态的字符串列表，我会将它们存储在一个有序的数组中，然后使用bsearch来确定一个字符串是否在该列表中。如果它不存在，则返回NULL;如果该值存在，则返回值的指针可能比线性搜索或散列更快。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

/* 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; 
}

来源

2010-08-08 23:42:04

如果你的常量字符串在编译时已知，那么看看“完美散列”的概念。

维基百科：一个集合S的完美散列函数是一个散列函数，它将S中的不同元素映射到不同的整数，没有冲突。

“没有碰撞”的事情可以节省您的工作。进一步阅读和实现的可能性是：

CMPH - http://cmph.sourceforge.net/
的gperf - http://www.gnu.org/software/gperf/

来源

2010-08-09 01:22:02 Darron

c字符串比较vs散列比较

回答

相关问题