c字符串比較vs散列比較

Question

我需要比較一個字符串與c中的多個其他常量字符串。我很好奇，哪個更快，散列我要比較的字符串，並將其與所有其他常量字符串散列進行比較，或者將字符串作爲字符串進行比較。提前謝謝你

謝謝你的答案我會做很多比較。任何人都可以給我一個好的，快速的，低資源密集型的算法來使用嗎？我知道的唯一散列是MD5，我有一種超過殺死的感覺。

我也想補充的是，字符串是也許20或30個字符，在絕大多數是最大7左右

Answer 1

將會比較中一次或多次做了什麼？如果只進行一次比較，那麼你最好做一個比較。如果您需要將很多字符串與這組常量字符串進行比較，那麼您可以通過使用散列來節省時間。

這是一個足夠簡單的問題，您可以輕鬆地將其寫入兩種方式，並查看哪種方法對於代表性輸入集更好。

Answer 2

散列值的相等並不保證相等 - 不匹配將保證不等式，但。如果你需要比較大量的字符串與你的集合，散列會很好 - 如果是一次性比較（不太可能我猜），那麼strcmp將會很好地完成。

Answer 3

這取決於。什麼是哈希算法？字符串有多長？什麼是平臺？

另請注意，匹配的散列不保證匹配的字符串。

Answer 4

它很大程度上取決於字符串的長度和散列函數的複雜性。實施和測試自己將是最好的答案...

Answer 5

如果您嘗試將主題字符串與其他字符串進行匹配，則可以考慮使用Aho-Corasick String Matching Algorithm。它使用一個trie來在一次傳遞中將主體與所有目標字符串進行匹配（這也很容易實現）。

Answer 6

另一種可行的方法是將你的常量字符串進行排序並對字符串進行二分搜索，這樣最多隻能比較log2(n)（例如，對於1024個字符串只能進行10次比較，或者只能進行20次比較1000000個字符串）。 我不知道它是否適用於您的問題，但是我用這種方法取得了非常好的效果。哈希是非常難以正確處理的，角落的情況會變得非常糟糕，並且密鑰的計算通常會非常昂貴。

Answer 7

非常感謝你給我答案 做了許多比較。可以 任何人都給我一個好的，快速的，低密度的資源密集算法使用？ 我知道的唯一散列是MD5，而我 有一種超過殺死的感覺。

Murmur hash簡單，快速，在統計測試中表現良好。

Answer 8

很難領先，字符串散列函數是O（n）。字符串比較也是O（n），以較小的喔。如果您可以存儲您計算的散列值並重復使用它們，那麼您只能在前面。對彼此而言。

簡單示例C哈希函數are here。

Answer 9

我想如果你有一個靜態的字符串列表，我會將它們存儲在一個有序的數組中，然後使用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; 
} 

Answer 10

如果你的常量字符串在編譯時已知，那麼看看「完美散列」的概念。

維基百科：一個集合S的完美散列函數是一個散列函數，它將S中的不同元素映射到不同的整數，沒有衝突。

「沒有碰撞」的事情可以節省您的工作。進一步閱讀和實現的可能性是：

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