構造一個散列表/散列函數

我想構造一個散列表，它查找1到15個字節範圍內的字節序列（字符串）中的鍵。構造一個散列表/散列函數

我想存儲一個整數值，所以我想像一個哈希數組就足夠了。我很難概念化如何構建一個散列函數，因爲給定的關鍵字會給數組一個索引。

任何協助將會很多appreiated。

在散列條目的最大數目爲：4081 * 15 + 4081 * 14 + ... 4081 = 4081（（15 *（16））/ 2）= 489720.

因此，例如：

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
}

什麼是散列函數的一些很好的選擇，或者我將如何去構建一個？

謝謝。

來源

2010-06-02 snap

如果兩個鍵映射到相同的索引，則會發生衝突，在您的示例中未正確處理該衝突。你是否保留你的例子只是爲了說明你的哈希，還是你真的需要關於哈希表本身的額外解釋？（開放哈希，關閉哈希，...） – Patrick 2010-06-03 06:51:26

如果你想要一個完美的散列，那麼你可以閱讀維基百科文章perfect hashing開始。如果遇到困難，你可以在這裏尋求幫助。

來源

2010-06-02 23:02:49 bmargulies

如果表中駐留的字符串的平均數量很低 - 比如10,000條以下的條目 - 關聯數組將是一個合理的方法，即使使用線性搜索，如果它在現代CPU架構上。

否則，構建「理想散列」需要檢查字符串的每個字符並根據可能的範圍計算唯一值。例如，如果只有26個字符A..Z被允許的關鍵，這會工作：

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
}

來源

2010-06-02 23:07:20 wallyk

這將在7個字符後溢出一個32位int，並在14個字符後溢出一個64位int。不是查找表的好索引... – 2010-06-02 23:27:12

您的密鑰空間大（約2 ^（8 * 15）），所以如果你想有一個完美的散列，你需要知道什麼489720實際密鑰會提前顯示出來。即使這樣，即使你允許一張更大的表格（也稱爲非常低的載入因子），爲這些鍵找到一個完美的散列值實際上是不可能的。我知道找到一個完美的散列的唯一方法是通過試驗和錯誤，隨機散列可能會失敗，除非你的表有接近489720^2條目。

我強烈建議您使用regular (non-perfect) hash和deal with collisions appropriately，例如，與鏈接：

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
}

我也建議你不要自己實現這個 - 使用標準庫，如c++ hashmap。

來源

2010-06-02 23:43:07

哈希C字符串，我一直用這個函數（取％的結果你的哈希表的規模）：

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
}

我不記得在那裏我從最初的得到它，但在多年它並沒有讓我失望。

來源

2011-02-22 08:03:23 Enno

對不起，但無法獲得。這裏和4081在這個問題上有什麼意義。 – user3798283 2016-05-07 14:03:56

構造一個散列表/散列函數

回答

相關問題