用C語言遞歸hashcode

我在嘗試做一個hashcode函數。用C語言遞歸hashcode

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

2014-10-06 Mark

只是fyi，不管長度是5還是不需要動態分配。對遞歸轉發函數的設置將對任意長度執行此操作，而不需要字符串分配和副本。 [**見它現場**]（http://coliru.stacked-crooked.com/a/8072c4f996eabb16） – WhozCraig 2014-10-06 04:55:47

你爲什麼決定在這裏使用遞歸？你會更好地使用一個簡單的循環。 – StilesCrisis 2014-10-06 04:56:50

@StilesCrisis不確定你是問我還是OP，但是如果我，因爲它顯然是OP任務的要求（我只是假設它是一個學術練習）。如果我（和顯然你）一個簡單的循環將是一天的順序。 – WhozCraig 2014-10-06 05:11:21

從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)); 
}

來源

2014-10-06 04:46:47 perreal

這些實際上並沒有給我正確的代碼，它正在生產8739 ... – Mark 2014-10-06 05:11:13

@Dad你確定*你正在編譯一個64位無符號long的機器？我問，因爲......好。 [** ideone.com樣本**]（http://ideone.com/4LVRLT）顯然有32位'無符號長'，而這[** coliru樣本**]（http：//coliru.stacked-crooked。 com/a/8072c4f996eabb16）使用相同的代碼使用64位實現。如果你得到的是前者而不是後者，那麼可能要檢查你的編譯器目標。 – WhozCraig 2014-10-06 05:14:00

@爸，如果你的'長'不夠寬，請嘗試'uint64_t'或'unsigned long long'。 – perreal 2014-10-06 05:15:03

我不禁感到遞歸是一個奇怪的方式來編碼它（在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 ==

來源

2014-10-06 05:57:26

用C語言遞歸hashcode

回答

相關問題