這是SuperFashHash實現計算字符串的正確31位散列嗎？

Question

我在Excel中使用VBA中的SuperFastHash變體（32位版本，因此沒有LongLong可用）來實現散列字符串。

爲了解決已簽名的32位Long值的侷限性，我使用Double類型進行加法和位移，然後以一種將它截斷爲31位（最大值積極的價值 - 不想處理兩個補碼和標誌）。

我得到的答案和避免溢出到目前爲止，但我有一個懷疑，我在翻譯中犯了一些錯誤，因爲大多數實現使用一個uint的所有32位，也處理單個字節從數組而不是來自AscW（）的16位值。

我希望有人能腸道檢查落實的具體部分：

1. 我如何測試16位字符的話，而不是4個字節的塊。
2. 無論我的位移操作在技術上是否正確，考慮到我需要以31位截斷Long值的警告。
3. 鑑於哈希僅使用31位，最終的雪崩件是否仍然合適。

下面是當前的代碼：

Public Function shr(ByVal Value As Long, ByVal Shift As Byte) As Long 
    shr = Value 
    If Shift > 0 Then shr = shr \ (2^Shift) 
End Function 

Public Function shl(ByVal Value As Long, ByVal Shift As Byte) As Long 
    If Shift > 0 Then 
     shl = LimitDouble(CDbl(Value) * (2&^Shift)) 
    Else 
     shl = Value 
    End If 
End Function 

Public Function LimitDouble(ByVal d As Double) As Long 
    '' Prevent overflow by lopping off anything beyond 31 bits 
    Const MaxNumber As Double = 2^31 
    LimitDouble = CLng(d - (Fix(d/MaxNumber) * MaxNumber)) 
End Function 

Public Function SuperFastHash(ByVal dataToHash As String) As Long 
    Dim dataLength As Long 
    dataLength = Len(dataToHash) 
    If (dataLength = 0) Then 
     SuperFastHash = 0 
     Exit Function 
    End If 
    Dim hash As Long 
    hash = dataLength 
    Dim remainingBytes As Integer 
    remainingBytes = dataLength Mod 2 
    Dim numberOfLoops As Integer 
    numberOfLoops = dataLength \ 2 
    Dim currentIndex As Integer 
    currentIndex = 0 
    Dim tmp As Double 
    Do While (numberOfLoops > 0) 
     hash = LimitDouble(CDbl(hash) + AscW(Mid$(dataToHash, currentIndex + 1, 1))) 
     tmp = shl(AscW(Mid$(dataToHash, currentIndex + 2, 1)), 11) Xor hash 
     hash = shl(hash, 16) Xor tmp 
     hash = LimitDouble(CDbl(hash) + shr(hash, 11)) 
     currentIndex = currentIndex + 2 
     numberOfLoops = numberOfLoops - 1 
    Loop 
    If remainingBytes = 1 Then 
     hash = LimitDouble(CDbl(hash) + AscW(Mid$(dataToHash, currentIndex + 1, 1))) 
     hash = hash Xor shl(hash, 10) 
     hash = LimitDouble(CDbl(hash) + shr(hash, 1)) 
    End If 
    '' Final avalanche 
    hash = hash Xor shl(hash, 3) 
    hash = LimitDouble(CDbl(hash) + shr(hash, 5)) 
    hash = hash Xor shl(hash, 4) 
    hash = LimitDouble(CDbl(hash) + shr(hash, 17)) 
    hash = hash Xor shl(hash, 25) 
    hash = LimitDouble(CDbl(hash) + shr(hash, 6)) 
    SuperFastHash = hash 
End Function 

Answer 1

我會建議，而不是雙打亂搞，你可能會更好過分裂32位字爲兩個「16位」部分，其中的每一個在一個符號的32位變量所保持（使用低16位的每個變量的，然後在「正常化」步驟之間的值：

highPart = (highPart + (lowPart \ 65536)) and 65535 
lowPart = lowPart and 65535 

左移16個地方僅僅意味着複製低部分高部分和調零低部分。右移16位意味着將高位部分複製到低位部分並將高位部分調零。向左移動較少的位置就意味着分別移動兩個部分然後正常化。將標準化數字向右移動較少數量的位置意味着將兩個部分左移（16-N），正常化並右移16位。