20

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

给出了什么

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

到目前为止我做了什么

我认为这个 SO 答案是一个好的开始,因为它会生成一个 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 个字符)和足够长的字符串散列,以获取一小部分重复项。

4

4 回答 4

39

也许其他人会发现这很有用。

我收集了一些不同的函数来在 VBA 中生成一个简短的字符串散列。
我不相信代码,并且引用了所有来源。

在此处输入图像描述

  1. CRC16
    • 功能:=CRC16HASH(A1)使用此代码
    • hash 是一个 4 个字符长的 HEX 字符串
    • 19 行代码
    • 4 位长哈希 = 6895 行中的 624 次冲突 = 9% 的冲突率
  2. CRC16 数字
    • 功能:=CRC16NUMERIC(A1)使用此代码
    • 哈希是一个 5 位长的数字
    • 92 行代码
    • 5 位长哈希 = 6895 行中的 616 次冲突 = 8.9 % 冲突率
  3. CRC16 两次
    • 功能:=CRC16TWICE(A1)使用此代码
    • hash 是一个 8 个字符长的 HEX 字符串
    • 哈希可以扩展到 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 % 冲突率

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

随意添加自己的功能。

于 2013-02-07T11:18:49.327 回答
16

将你的字符串分成三个较短的字符串(如果不能被三整除,最后一个将比其他两个长)。在每个上运行你的“短”算法,并连接结果。

我可以编写代码,但根据问题的质量,我认为您可以从这里获取它!

编辑:事实证明,这个建议是不够​​的。您的原始 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

于 2013-02-06T17:25:41.983 回答
5

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哈希算法

于 2015-02-06T09:04:05.610 回答
0

虽然下面不是哈希函数,但我已将其用作生成数字 id 的快速方法,该方法在小列表中具有低冲突率(小到足以通过检查进行验证)。

工作原理:A 列保存第 2 行以后的字符串。在第 1 行中,A1 和 B1 在字符串中间保持任意开始和结束位置。该公式使用字符串的第一个字母和取自字符串中间的固定字母,并使用 LEN() 作为“扇形函数”来减少冲突的机会。

 =CODE(A2)*LEN(A2) + CODE(MID(A2,$A$1,$B$1))*LEN(MID(A2,$A$1,$B$1))

如果从具有固定宽度字段的数据库表中提取字符串,您可能需要修剪长度:

 =CODE(TRIM(C8))*LEN(TRIM(C8))
       +CODE(MID(TRIM(C8),$A$1,1))*LEN(MID(TRIM(C8),$A$1,$B$1))
于 2013-06-13T14:49:54.487 回答