0

我正在 VBA 中实现 SuperFastHash 的变体，用于 Excel（32 位版本，因此没有可用的 LongLong）来散列字符串。

为了绕过带符号的 32 位 Long 值的限制，我正在使用 Double 类型进行加法和位移，然后从 Double 转换为 Long 以将其截断为 31 位（最大正值 -不想处理二进制补码和符号）。

到目前为止，我得到了答案并避免了溢出，但我怀疑我在翻译中犯了一些错误，因为大多数实现都使用 uint 的所有 32 位，并且还处理数组中的单个字节而不是 16 位值来自 AscW()。

我希望有人可以检查一下实现的特定部分：

  1. 我如何测试 16 位字符而不是 4 字节块。
  2. 考虑到我需要将 Long 值截断为 31 位，我的位移操作在技术上是否正确。
  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
4

1 回答 1

1

我建议不要乱用双打，最好将 32 位字分成两个“16 位”部分，每个部分都保存在有符号的 32 位变量中（使用低 16 位每个变量的值，然后“标准化”步骤之间的值：

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

左移 16 位只是意味着将低部分复制到高部分并将低部分归零。右移 16 位只是意味着将高部分复制到低部分并将高部分归零。向左移动较少的位置仅意味着分别移动两个部分，然后进行归一化。将归一化的数字右移较少的位数意味着将两个部分都左移 (16-N) 位、归一化和右移 16 位。

于 2012-10-09T22:29:09.627 回答