用C語言遞歸hashcode

Question

我在嘗試做一個hashcode函數。

不過，我得到一個隨機數不等於例子，我也不能確定爲什麼（5是最大長度，所以不需要動態內存分配）

Answer 1

從strncpydocumentation：

如果 源長於num，則不會在目標結束時隱式添加空字符。因此，在這種情況下，目標不應該被認爲是一個空終止的C字符串（因爲它將會溢出 ）。

所以你想做的事：

strncpy(new, str, l - 1); 
new[l - 1] = 0; 

但你也可以創建避免使用輔助功能，新的字符串：

unsigned long hash_helper(const char* str, int len){ 
    if (len == 0) return 0; 
    return hash_helper(str, len - 1) * 65599 + str[len - 1]; 
} 

unsigned long hash(const char* str){ 
    return hash_helper(str, strlen(str)); 
} 

Answer 2

我不禁感到遞歸是一個奇怪的方式來編碼它（在C - 在LISP中，它會很好）。在此代碼中，hash1()是散列函數的簡單迭代版本; hash2()如下遞歸說明書中，使用hash3()作爲輔助功能（它需要的長度）：

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

static unsigned long hash1(const char *str) 
{ 
    unsigned long h = 0; 
    while (*str != '\0') 
     h = h * 65599 + *str++; 
    return h; 
} 

static unsigned long hash3(const char *str, size_t len) 
{ 
    unsigned long h = 0; 
    if (len > 0) 
     h = hash3(str, len - 1) * 65599 + str[len-1]; 
    return h; 
} 

static unsigned long hash2(const char *str) 
{ 
    size_t len = strlen(str); 
    return hash3(str, len); 
} 

static int test_hash(const char *str) 
{ 
    unsigned long h1 = hash1(str); 
    unsigned long h2 = hash2(str); 
    int rc = 0; 
    const char *pass_fail = "PASS"; 
    if (h1 != h2) 
    { 
     rc = 1; 
     pass_fail = "FAIL"; 
    } 
    printf("h1 = %lu, h2 = %lu: %s (%s)\n", h1, h2, pass_fail, str); 
    return rc; 
} 

int main(void) 
{ 
    static const char *data[] = 
    { 
     "ice", "man", "cometh", "the iceman cometh", 
    }; 
    int failures = 0; 
    for (size_t i = 0; i < sizeof(data)/sizeof(data[0]); i++) 
     failures += test_hash(data[i]); 
    printf("%s\n", (failures == 0) ? "== PASS ==" : "!! FAIL !!"); 
    return !(failures == 0); 
} 

樣本輸出（64位的平臺上，GCC 4.9.1在Mac OS X 10.9.5）：

h1 = 451845518507, h2 = 451845518507: PASS (ice) 
h1 = 469058302522, h2 = 469058302522: PASS (man) 
h1 = 8177059914254772472, h2 = 8177059914254772472: PASS (cometh) 
h1 = 2988038870251942490, h2 = 2988038870251942490: PASS (the iceman cometh) 
== PASS == 

請注意，ice的代碼與示例匹配。當編譯爲32位程序時，輸出爲：

h1 = 873952427, h2 = 873952427: PASS (ice) 
h1 = 906867258, h2 = 906867258: PASS (man) 
h1 = 138275064, h2 = 138275064: PASS (cometh) 
h1 = 1819095642, h2 = 1819095642: PASS (the iceman cometh) 
== PASS ==