VBA哈希字符串

Question

如何使用Excel VBA获取长字符串的简短哈希

什么是给定的

• 输入字符串不超过80个字符
• 有效输入字符为:[0..9] [A_Z]._/
• 有效输出字符为[0..9] [A_Z] [a_z] (可以使用大小写)
• 输出哈希值不应超过~12个字符(更短更好)
• 不需要是唯一的,因为这将导致太长的哈希

到目前为止我做了什么

我认为这个答案是一个很好的开始,因为它生成一个4位十六进制代码(CRC16).

但是4位数字很少.在我的400字符串测试中,20%在其他地方得到了重复.
产生碰撞的机会太高了.

Sub tester()
    For i = 2 To 433
        Cells(i, 2) = CRC16(Cells(i, 1))
    Next i
End Sub


Function CRC16(txt As String)
Dim x As Long
Dim mask, i, j, nC, Crc As Integer
Dim c As String

Crc = &HFFFF

For nC = 1 To Len(txt)
    j = Val("&H" + Mid(txt, nC, 2))
    Crc = Crc Xor j
    For j = 1 To 8
        mask = 0
        If Crc / 2 <> Int(Crc / 2) Then mask = &HA001
        Crc = Int(Crc / 2) And &H7FFF: Crc = Crc Xor mask
    Next j
Next nC

CRC16 = Hex$(Crc)
End Function

如何重现

您可以从pastebin复制这400个测试字符串.
将它们粘贴到新Excel工作簿中的A列并执行上面的代码.

问:如何获得足够短(12个字符)的字符串哈希,并且足够长以获得一小部分重复项.

Answer 1

也许其他人会觉得这很有用.

我已经收集了一些不同的函数来在VBA中生成字符串的短哈希.
我不赞成代码,所有来源都被引用.

1. CRC16
   • 功能:=CRC16HASH(A1)使用此代码
   • hash是一个4个字符长的HEX字符串
   • 19个代码行
   • 4位长哈希= 6895行中的624次冲突= 9%碰撞率
2. CRC16数字
   • 功能:=CRC16NUMERIC(A1)使用此代码
   • hash是一个5位数的长号
   • 92行代码
   • 5位长哈希= 6895行中的616次冲突= 8.9%的冲突率
3. CRC16两次
   • 功能:=CRC16TWICE(A1)使用此代码
   • hash是一个8个字符长的HEX字符串
   • hash可以扩展到12/16/20等字符,以减少冲突率
   • 39个代码行
   • 8位长哈希= 6895行中的18次冲突= 0.23%碰撞率
4. SHA1
   • 功能:=SHA1TRUNC(A1)使用此代码
   • hash是一个40个字符长的HEX字符串
   • 142个代码行
   • 可以被截断
   • 4位哈希= 6895行中的726次冲突= 10.5%的冲突率
   • 5位数哈希= 6895行中的51次碰撞= 0.73%碰撞率
   • 6位数哈希= 6895行中的0次冲突= 0%碰撞率
5. SHA1 + Base64
   • 功能:=BASE64SHA1(A1)使用此代码
   • hash是一个28个字符长的unicode字符串(区分大小写+特殊字符)
   • 41个代码行
   • 需要.NET,因为它使用库"Microsoft MSXML"
   • 可以被截断
   • 4位数哈希= 6895行中的36次冲突= 0.5%碰撞率
   • 5个数字哈希= 6895行中的0个冲突= 0%冲突率

这是我的测试工作簿,包含所有示例函数和大量测试字符串.

随意添加自己的功能.

Answer 2

将您的字符串拆分为三个较短的字符串(如果不能被三整除,则最后一个字符串将长于其他两个字符串).在每个上运行"短"算法,并连接结果.

我可以编写代码,但根据问题的质量,我认为你可以从这里开始!

编辑:事实证明,这个建议是不够​​的.您的原始CRC16代码存在严重缺陷 - 即表示:

j = Val("&H" + Mid(txt, nC, 2))

这只处理可以解释为十六进制值的文本:小写和大写字母相同,并且忽略字母表中F之后的任何内容(据我所知).任何好的东西都是奇迹.如果你用线替换

j = asc(mid(txt, nC, 1))

事情变得更好 - 每个ASCII代码至少从生命开始作为自己的价值.

将此更改与我之前提出的提案相结合,您将获得以下代码:

Function hash12(s As String)
' create a 12 character hash from string s

Dim l As Integer, l3 As Integer
Dim s1 As String, s2 As String, s3 As String

l = Len(s)
l3 = Int(l / 3)
s1 = Mid(s, 1, l3)      ' first part
s2 = Mid(s, l3 + 1, l3) ' middle part
s3 = Mid(s, 2 * l3 + 1) ' the rest of the string...

hash12 = hash4(s1) + hash4(s2) + hash4(s3)

End Function

Function hash4(txt)
' copied from the example
Dim x As Long
Dim mask, i, j, nC, crc As Integer
Dim c As String

crc = &HFFFF

For nC = 1 To Len(txt)
    j = Asc(Mid(txt, nC)) ' <<<<<<< new line of code - makes all the difference
    ' instead of j = Val("&H" + Mid(txt, nC, 2))
    crc = crc Xor j
    For j = 1 To 8
        mask = 0
        If crc / 2 <> Int(crc / 2) Then mask = &HA001
        crc = Int(crc / 2) And &H7FFF: crc = crc Xor mask
    Next j
Next nC

c = Hex$(crc)

' <<<<< new section: make sure returned string is always 4 characters long >>>>>
' pad to always have length 4:
While Len(c) < 4
  c = "0" & c
Wend

hash4 = c

End Function

您可以将此代码放在电子表格=hash12("A2")中等.为了好玩,您还可以使用"新的,改进的"hash4算法,并查看它们的比较方式.我创建了一个数据透视表来计算碰撞 - hash12算法没有,只有3个hash4.我相信你可以弄明白如何创造hash8...... 你问题中的"无需独一无二"表明,"改进"可能hash4就是你所需要的.

原则上,四字符十六进制应该具有64k唯一值 - 因此具有相同散列的两个随机字符串在64k中的概率为1.当你有400个字符串时,有400 x 399/2"可能的碰撞对"~80k个机会(假设你有高度随机的字符串).因此,在样本数据集中观察三次碰撞不是不合理的分数.随着你的字符串数N上升,碰撞的概率变为N的平方.随着hash12中额外的32位信息,当N> 20 M左右时你会看到碰撞(handwaving,in-my-头数学).

你可以使hash12代码更紧凑一些 - 而且应该很容易看到如何将它扩展到任何长度.

哦,还有最后一件事.如果启用了RC寻址,则使用=CRC16("string")电子表格公式会产生难以跟踪的#REF错误...这就是我重命名它的原因hash4

Answer 3

低级别冲突字符串的 32 位哈希函数：

Public Function StrHash(text As String) As Long
    Dim i As Long
    StrHash = &H65D5BAAA

    For i = 1 To Len(text)
        StrHash = ((StrHash + AscW(Mid$(text, i, 1))) Mod 69208103) * 31&
    Next
End Function

或者作为 64 位哈希函数：

Public Function StrHash64(text As String) As String
    Dim i&, h1&, h2&, c&
    h1 = &H65D5BAAA
    h2 = &H2454A5ED

    For i = 1 To Len(text)
        c = AscW(Mid$(text, i, 1))
        h1 = ((h1 + c) Mod 69208103) * 31&
        h2 = ((h2 + c) Mod 65009701) * 33&
    Next

    StrHash64 = Right("00000000" & Hex(h1), 8) & Right("00000000" & Hex(h2), 8)
End Function

基于FNV哈希算法