VBA hash string

问题:

How do I get a short hash of a long string using Excel VBA

Whats given

• Input string is not longer than 80 characters
• Valid input characters are: [0..9] [A_Z] . _ /
• Valid output characters are [0..9] [A_Z] [a_z] (lower and upper case can be used)
• The output hash shouldn't be longer than ~12 characters (shorter is even better)
• No need to be unique at all since this will result in a too long hash

What I have done so far

I thought this SO answer is a good start since it generates a 4-digit Hex-Code (CRC16).

But 4 digits were to little. In my test with 400 strings 20% got a duplicate somewhere else.
The chance to generate a collision is too high.

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

How to reproduce

You can copy these 400 test strings from pastebin.
Paste them to column A in a new Excel workbook and execute the code above.

Q: How do I get a string hash which is short enough (12 chars) and long enough to get a small percentage of duplicates.

回答1:

Split your string into three shorter strings (if not divisible by three, the last one will be longer than the other two). Run your "short" algorithm on each, and concatenate the results.

I could write the code but based on the quality of the question I think you can take it from here!

EDIT: It turns out that that advice is not enough. There is a serious flaw in your original CRC16 code - namely the line that says:

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

This only handles text that can be interpreted as hex values: lowercase and uppercase letters are the same, and anything after F in the alphabet is ignored (as far as I can tell). That anything good comes out at all is a miracle. If you replace the line with

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

Things work better - every ASCII code at least starts out life as its own value.

Combining this change with the proposal I made earlier, you get the following code:

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

You can place this code in your spreadsheet as =hash12("A2") etc. For fun, you can also use the "new, improved" hash4 algorithm, and see how they compare. I created a pivot table to count collisions - there were none for the hash12 algorithm, and only 3 for the hash4. I'm sure you can figure out how to create hash8, ... from this. The "no need to be unique" from your question suggests that maybe the "improved" hash4 is all you need.

In principle, a four character hex should have 64k unique values - so the chance of two random strings having the same hash would be 1 in 64k. When you have 400 strings, there are 400 x 399 / 2 "possible collision pairs" ~ 80k opportunities (assuming you had highly random strings). Observing three collisions in the sample dataset is therefore not an unreasonable score. As your number of strings N goes up, the probability of collisions goes as the square of N. With the extra 32 bits of information in the hash12, you expect to see collisions when N > 20 M or so (handwaving, in-my-head-math).

You can make the hash12 code a little bit more compact, obviously - and it should be easy to see how to extend it to any length.

Oh - and one last thing. If you have RC addressing enabled, using =CRC16("string") as a spreadsheet formula gives a hard-to-track #REF error... which is why I renamed it hash4

回答2:

Maybe others will find this useful.

I have collected some different functions to generate a short hash of a string in VBA.
I don't take credit for the code and all sources are referenced.

1. CRC16
   • Function: =CRC16HASH(A1) with this Code
   • hash is a 4 characters long HEX string
   • 19 code lines
   • 4 digits long hash = 624 collisions in 6895 lines = 9 % collision rate
2. CRC16 numeric
   • Function: =CRC16NUMERIC(A1) with this Code
   • hash is a 5 digits long number
   • 92 code lines
   • 5 digits long hash = 616 collisions in 6895 lines = 8.9 % collision rate
3. CRC16 twice
   • Function: =CRC16TWICE(A1) with this Code
   • hash is a 8 characters long HEX string
   • hash can be expanded to 12/16/20 etc. characters to reduce collision rate even more
   • 39 code lines
   • 8 digits long hash = 18 collisions in 6895 lines = 0.23 % collision rate
4. SHA1
   • Function: =SHA1TRUNC(A1) with this Code
   • hash is a 40 characters long HEX string
   • 142 code lines
   • can be truncated
   • 4 digits hash = 726 collisions in 6895 lines = 10.5 % collision rate
   • 5 digits hash = 51 collisions in 6895 lines = 0.73 % collision rate
   • 6 digits hash = 0 collisions in 6895 lines = 0 % collision rate
5. SHA1 + Base64
   • Function: =BASE64SHA1(A1) with this Code
   • hash is a 28 characters long unicode string (case sensitive + special chars)
   • 41 code lines
   • requires .NET since it uses library "Microsoft MSXML"
   • can be truncated
   • 4 digits hash = 36 collisions in 6895 lines = 0.5 % collision rate
   • 5 digits hash = 0 collisions in 6895 lines = 0 % collision rate

Here is my test workbook with all example functions and a big number of test strings.

Feel free to add own functions.

回答3:

For the record, this one quickly generates a 32 bit hash with a low level of collision:

Public Function HashFNV(txt As String) As Long
  Const max# = 2 ^ 31
  Dim hash#, upper&, i&
  If txt = Empty Then Exit Function
  hash = &H11C9DC5
  For i = 1 To Len(txt)
    hash = 31# * (hash - upper * max Xor AscW(Mid$(txt, i, 1)))
    upper = hash / max
  Next
  HashFNV = hash - upper * max Or &H80000000 * (upper And 1&)
End Function

回答4:

While the below is not a hash function, I've used it as a quick way to generate numeric id's that have a low collision rate over a small list (small enough to verify by inspection).

How it Works: Column A holds the strings from row 2 onward. In row 1, A1 and B1 hold an arbitrary start and end position midway in the string. The formula uses the first letter of the string and a fixed letter taken from mid-string and uses LEN() as a 'fanning function' to reduce the chance of collisions.

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

If strings are pulled from a database table with fixed width fields, you may need to trim the lengths:

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