二進制散列函數系列

我正在尋找散列函數F1，.. Fn的系列，其中每個Fi映射[0,1]中的任何鍵。我的第一個實現是Fi（k）= F（k，i）= hash（i，hash（k，0））。這裏hash是這裏提供的hashlittle函數（http://burtleburtle.net/bob/c/lookup3.c）。我還沒有仔細研究過究竟做了什麼。二進制散列函數系列

由於尖銳的讀者會注意到，這將失敗。我的問題是如何有效實現這一點。我的目標是平均最小化對於任何給定k1，k2對的最大i，其中Fi（k1）== Fi（k2）。當然它應該也是很快..

來源

2010-07-01 Sandeep

那麼，我已經看了一下引擎蓋。

uint32_t hashlittle(const void *key, size_t length, uint32_t initval) 
{ 
    union { const void *ptr; size_t i; } u;  /* needed for Mac Powerbook G4 */ 

    u.ptr = key; 
    if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {

寫入u.ptr然後閱讀u.i是未定義的行爲。

編輯

我想我現在明白了。你基本上需要使用兩個參數作爲輸入的散列函數。你幾乎可以使用任何散列函數。

散列函數接受一個任意比特大小的一個數據包，並將其轉換成一個固定的比特大小的一個數據包：

hashval = Hash(data, len);

需要，其中一個附加的參數，並給出內的使用的功能的轉型吧？

hashval = Hash(data, len, addval);

最簡單的方法是將額外的值連接到數據包：

memcpy((char *)data + len, &addval, sizeof(addval)); 
hashval = Hash(data, len + sizeof(addval));

如果有可用的源代碼，另一種方法是修改它使用新的參數作爲初始化爲內部散列計算。這完全是在做什麼。

Before: 
uint32_t Hash (const void *data, size_t len) 
{ 
    uint32_t hashval = 0; 
    .... 
    return (hashval); 
} 

After: 
uint32_t Hash (const void *data, size_t len, uint32_t init) 
{ 
    uint32_t hashval = init; 
    .... 
    return (hashval); 
}

，此選項可能有點難做，因爲內部狀態可以比單hashval得多，並且初始化可以說是相當複雜的，而不是簡單地用0。hashlittle的是：

/* Set up the internal state */ 
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;

來源

2010-07-01 06:56:01 Secure

恐怕我不太明白。你是說在lookup3.c中的函數沒有正確實現。我的問題並不是關於lookup3.c的用法，而是關於這種情況下散列函數的適當選擇。我在這裏記錄的是我目前的做法。 -Sandeep – Sandeep 2010-07-01 13:38:53

「沒有正確實施」......你可以這麼說，是的。我認爲這是一個不成熟優化惡習的完美例子。他試圖通過以32位爲單位讀取數據而不是逐字節讀取數據（如果數據未以此方式初始化，這本身又是未定義的行爲），並且必須跳過這麼多的循環，包括單獨的函數小型和大型機器，這簡直荒謬。自從你提到它之後，它似乎對你來說已經足夠重要了，而且我總是對這樣的事情感興趣，所以我看了一下。 – Secure 2010-07-01 21:53:12

對於你的問題，對不起，我不明白。 – Secure 2010-07-01 22:00:56

二進制散列函數系列

回答

相關問題