散列算法

我正在尋找一個散列算法，以儘可能接近一個字符串（max len = 255）的唯一散列，從而產生一個長整數（DWORD）。散列算法

我意識到26^255 >> 2^32，但也知道英文單詞的數量遠遠少於2^32。

我需要'散列'的字符串大多是單個單詞或使用兩個或三個單詞的簡單構造。

答案：

其中FNV variants應滿足您的要求。它們速度很快，並且產生相當均勻分佈的輸出。（由Arachnid回答）

來源

2008-09-24 slashmais

對這個問題的前一次迭代（及答案）查看here。

來源

2008-09-24 10:26:38

是，叔帽子是我在找的東西。我做了搜索，但我使用的關鍵字並未出現在您提供的鏈接中。我在那裏添加了一條評論以添加更多相關關鍵字。 – slashmais 2008-09-24 10:32:43

一種技術是使用衆所周知的哈希算法（比如MD5或SHA-1），並且只使用結果的前32位。

請注意散列衝突的風險增加得比您預期的要快。有關這方面的信息，請閱讀Birthday Paradox。

來源

2008-09-24 10:27:39

Ronny Pfannschmidt昨天做了一個普通英語單詞測試，並且沒有遇到任何他在Python字符串散列函數中測試的10000個單詞的衝突。我自己沒有測試過，但是這個算法非常簡單快捷，並且似乎是針對常見詞語進行了優化。

這裏實現：

static long 
string_hash(PyStringObject *a) 
{ 
    register Py_ssize_t len; 
    register unsigned char *p; 
    register long x; 

    if (a->ob_shash != -1) 
     return a->ob_shash; 
    len = Py_SIZE(a); 
    p = (unsigned char *) a->ob_sval; 
    x = *p << 7; 
    while (--len >= 0) 
     x = (1000003*x)^*p++; 
    x ^= Py_SIZE(a); 
    if (x == -1) 
     x = -2; 
    a->ob_shash = x; 
    return x; 
}

來源

2008-09-24 10:28:26

我們可以鏈接到您參考的文章/文章嗎？ – 2008-09-24 10:29:39

H（鍵）= [GetHash（鍵）+ 1 +（（（GetHash（鍵）>> 5）+ 1）％（HASHSIZE - 1））] ％HASHSIZE

MSDN article on HashCodes

來源

2008-09-24 10:32:34 Catch22

Java的String.hash（）可以很容易地觀察here，其算法是

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

來源

2008-09-24 10:33:20

回答

相關問題