0

文字列をハッシュするために、Excel (32 ビット バージョンなので、LongLong は使用できません) で使用するために、VBA で SuperFastHash のバリエーションを実装しています。

符号付き 32 ビットの Long 値の制限を回避するために、Double 型を使用して加算とビット シフトを行い、31 ビット (正の最大値 - 2 の補数と符号を扱いたくない)。

これまでのところ、回答を得てオーバーフローを回避していますが、ほとんどの実装では uint の 32 ビットすべてを使用し、16 ビット値ではなく配列からの個々のバイトを処理するため、変換でいくつかの間違いを犯している疑いがあります。 AscW() から来ています。

実装の特定の部分 誰かが腸をチェックできることを望んでいます:

  1. 4 バイトのチャンクではなく 16 ビット文字の単語をテストする方法。
  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

double をいじるよりも、32 ビット ワードを 2 つの「16 ビット」部分に分割し、それぞれを符号付き 32 ビット変数に保持することをお勧めします (下位 16 ビットを使用)。次に、ステップ間の値を「正規化」します。

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

左に 16 桁シフトするということは、単に低い部分を高い部分にコピーし、低い部分をゼロにすることを意味します。右に 16 桁シフトするということは、単に高い部分を低い部分にコピーし、高い部分をゼロにすることを意味します。少数の場所を左にシフトするということは、単に両方の部分を別々にシフトしてから正規化することを意味します。正規化された数値を少数の桁数だけ右にシフトすることは、両方の部分を左 (16-N) ビットにシフトし、正規化し、16 ビット右にシフトすることを意味します。

于 2012-10-09T22:29:09.627 に答える