VBA哈希字符串

21

如何使用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个字符),并且足够长以获得少量重复。


你看过这个答案吗? - chris neilsen
我有一个计算出的哈希值,长度为40个字符。这对我的需求来说太长了。而且这个实现需要146行代码,是我其余代码的两倍;D - nixda
2
过去的粘贴链接已经失效。 - Taylor Alex Raine
5个回答

43

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

我收集了一些在VBA中生成字符串短哈希的不同函数。
我不对代码做出贡献,所有来源都已标注。

enter image description here

  1. CRC16
    • 函数:=CRC16HASH(A1),使用这个代码
    • 哈希是4个字符长的十六进制字符串
    • 19行代码
    • 4个数字的哈希 = 6895行中的624次冲突 = 9%的冲突率
  2. CRC16 numeric
    • 函数:=CRC16NUMERIC(A1),使用这个代码
    • 哈希是5个数字长的数字
    • 92行代码
    • 5个数字的哈希 = 6895行中的616次冲突 = 8.9%冲突率
  3. CRC16 twice
    • 函数:=CRC16TWICE(A1),使用这个代码
    • 哈希是8个字符长的十六进制字符串
    • 哈希可以扩展到12/16/20等字符以进一步减少冲突率
    • 39行代码
    • 8个数字的哈希 = 6895行中的18次冲突 = 0.23%的冲突率
  • SHA1
    • 功能:使用此代码=SHA1TRUNC(A1)函数
    • 哈希是一个40个字符长的十六进制字符串
    • 142行代码
    • 可截断
    • 4位哈希值= 6895行中的726个冲突 = 10.5%的冲突率
    • 5位哈希值= 6895行中的51个冲突 = 0.73%的冲突率
    • 6位哈希值= 6895行中的0个冲突 = 0%的冲突率
  • SHA1 + Base64
    • 功能:使用此代码=BASE64SHA1(A1)函数
    • 哈希是一个28个字符长的unicode字符串(区分大小写+特殊字符)
    • 41行代码
    • 需要.NET,因为它使用“Microsoft MSXML”库
    • 可截断
    • 4位哈希值= 6895行中的36个冲突 = 0.5%的冲突率
    • 5位哈希值= 6895行中的0个冲突 = 0%的冲突率
  • 这里是我的测试工作簿,其中包含所有示例函数和大量测试字符串。

    欢迎添加自己的函数。


    2
    感谢您提供的测试工作表 - 做得非常好!(对于那些可能担心宏感染的人来说,值得一提的是,我已经下载了测试工作表,扫描过它,使用过它,没有任何问题。) - Assad Ebrahim
    1
    您的工作簿不可用。点击链接会显示“这些文件不再可用,因为它们的所有者违反了我们的服务条款。” - Thomas Cox
    @ThomasCox已解决,链接已恢复。 - nixda
    2
    你的链接缩短器似乎出了问题。使用该链接找不到测试工作簿。 - ftrotter
    2
    @nixda 你能再修复一下链接吗? - Karls

    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 算法没有冲突,而hash4只有3个冲突。我相信你可以从中想出如何创建 hash8 等等。你问题中的“不需要唯一”意味着也许“改进”的hash4就是你所需要的。
    原则上,四个字符的十六进制应该有64k个唯一值 - 因此两个随机字符串具有相同哈希的概率将是64k中的1个。当您有400个字符串时,有400 x 399/2个“可能的冲突对”~80k个机会(假设您拥有高度随机的字符串)。因此,在样本数据集中观察到三次冲突并不是不合理的分数。随着字符串数量N的增加,碰撞的概率会随着N的平方而增加。通过哈希12中的额外32位信息,您期望在N>大约20M时(插科打诨,头脑中的数学)看到碰撞。
    您可以使哈希12代码更加紧凑,显然 - 并且应该很容易看出如何将其扩展到任意长度。
    哦 - 最后一件事。如果您启用RC寻址,则使用=CRC16(“string”)作为电子表格公式会产生难以跟踪的#REF错误...这就是为什么我将其重命名为hash4的原因。

    1
    小伙伴,为你全面的努力和详细的解释点个赞!我很喜欢这篇文章并收藏了它,以备将来参考。 - Peter L.
    +1 很有帮助。我整天都在尝试不同的VBA实现(MD5、SHA1和Base64)。我将发布所有独立函数,并包含您的新代码,如果您不介意的话。也许您对其他解决方案感兴趣,因为您似乎像我一样付出了很多努力 :) - nixda
    1
    重新阅读这篇文章,我意识到当你允许所有字符(问题中已经这样做了)而不仅仅是数字[0-9]和[A-F]时,你可以获得一个更独特的哈希。这意味着4个字符哈希的总数从64k增加到1.6M,将冲突风险降低到非常小的程度。要利用这一点,您需要更改算法 - 您可以修改hash4以生成6位十六进制代码,然后转换为4个字符的“基36”数字。碰撞的概率会相应地下降。 - Floris

    7

    针对字符串具有低碰撞率的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哈希算法


    我已经使用您上面链接的示例工作簿尝试了您的函数,但是它无法正常工作,因为即使我插入了“PtrSafe”,Private Declare Sub CopyMemory Lib "kernel32"在x64系统上也无法正常工作。请问您能否查看此工作簿并找出错误? - nixda
    哈哈,我觉得这真是个有趣的巧合,昨天我决定使用你的实现,只有4小时后你就回来编辑了你4.5年前的答案。还有感谢提供链接 - 我一直在想这个十六进制值(初始哈希)。:) - Inarion

    0
    在最近的 Excel 版本(2022 年 3 月及以后),新的数组公式使得可以在不使用 VBA 的情况下创建哈希函数。
    以下是 Bernstein 的 djb2 哈希函数的公式(参见例如 http://www.cse.yorku.ca/~oz/hash.html):
    hash_djb2 = LAMBDA(v,
        MAP(
            v,
            LAMBDA(x,
                LET(
                    y, VALUETOTEXT(x, 0),
                    l, LEN(y),
                    REDUCE(
                        5381,
                        SEQUENCE(l),
                        LAMBDA(a, j,
                            LET(
                                z, CODE(MID(y, j, 1)),
                                MOD(a * 33 + z, 2 ^ 32)
                            )
                        )
                    )
                )
            )
        )
    );
    

    输出是小于2^32(~4e9)的整数。它可以使用DEC2HEX进一步缩短为8个字符,也可以使用Base64实现缩短为6个字符。

    你会如何将这个转化为公式? - undefined
    你可以将LAMBDA函数保存在Excel名称管理器中,然后像其他Excel函数一样使用该名称。请参阅官方文档:https://support.microsoft.com/zh-cn/office/lambda-%E5%87%BD%E6%95%B0-bd212d27-1cd1-4321-a34a-ccbf254b8b67 - undefined

    0

    虽然以下不是哈希函数,但我已将其用作快速生成数字ID的方法,这些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))
    

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接