可擴展哈希 - 最高有效位

我想寫可擴展哈希。在wiki我已經在python中找到了很好的實現。但是，這種代碼使用最低有效位，所以當我有散列1101爲d = 1值是1和d = 2值是01。我想用最重要的位。例如：散列1101,d = 1值爲1,d = 2值爲11。有沒有簡單的方法來做到這一點？我嘗試過，但我不能。可擴展哈希 - 最高有效位

你知道爲什麼它使用最不重要的位？

或多或少。當我們使用數組時，它非常高效。好吧，對於散列函數，我想使用4個字節的整數中的4個最小位，但是從左到右。

h = hash(k) 
h = h & 0xf #use mask to get four least bits 
p = self.pp[ h >> (4 - GD)]

它不起作用，我不知道爲什麼。

來源

2013-01-01 user1941524

你說你已經嘗試 - 發佈代碼，以便我們可以看到你出錯的地方。 –

你知道嗎？爲什麼它使用最不重要的位？ –

當你說你想要的最重要的位，你想限制到一個特定的整數大小，或頂部的非零位？例如，8位數字15（又名'00001111'）'0000'或'1111'的最重要的四位？前者很容易計算，後者更少（可能需要「日誌」）。 – Blckknght

使用最低有效位計算哈希是計算哈希的最快方法，因爲它只需要按位運算。這使它非常受歡迎。

這是一個使用最高有效位的哈希實現（在C中）。由於沒有直接的方法可以知道最重要的位，它會重複測試剩餘值是否只有指定的位數。

int significantHash(int value, int bits) { 
    int mask = (1 << bits) - 1; 
    while (value > mask) { 
     value >>= 1; 
    } 
    return value; 
}

我推薦重疊散列，它使用數字的所有位。從本質上講，它會在相同位數的部分中削減數量，並對它們進行異或運算。它比最不重要的散列運行得慢，但比重要的散列快。最重要的是，它提供了比其他兩種方法更好的分散性，使得當必須被散列的數字具有特定的位相關模式時，它成爲更好的候選。

int overlappingHash(int value, int bits) { 
    int mask = (1 << bits) - 1; 
    int answer = 0; 
    do { 
     answer ^= (value & mask); 
     value >>= bits; 
    } while (value > 0); 
    return answer; 
}

來源

2013-02-01 18:38:37 Spatarel

可擴展哈希 - 最高有效位

回答

相關問題