19

My goal is to generate a short Hash string of 6 characters (possibly containing characters [A-Z][a-z][0-9]) for a string which is 42 case-insensitive alphanumeric characters in length. Uniqueness is the key requirement. Security or performance is not so important.

Is there a specific algorithm which will give this result or should I stick to truncating a MD5 Hash or a SHA-1 Hash (Like in this question)? If so, what is the probability of a collision?

3
  • I tried this, string sourceString = "SomeTestStringWhichIs42CharactersInLength!"; Console.WriteLine(sourceString.GetHashCode().ToString("X6")); It returns an 8 Character Hash.
    – Isuru
    Aug 27, 2013 at 11:52
  • 1
    How can you generate a unique 6 chars hash for a 42 chars long string? Aug 27, 2013 at 11:58
  • 1
    With your limits, you can (at best) hash 62^6 numbers without collision. Although after hashing half that many, you'll have a 50% chance of collision (at best). Depends on the data to hash and the hashing algorithm - of course. Some algorithms will do better with different sets of data
    – Bob2Chiv
    Aug 27, 2013 at 12:21

3 Answers 3

29

Your best bet would be the truncating well-known hash function (MD5 or SHA-family) because these algorithms have statistically good uniform distributions of the hash values (and also using full hash and not just 6 chars there).

Now some calculations for probability of collision

- Number of letters in English alphabet: 26
- Add capitals: 26
- Add numerics: 10
--------------

In total you get 26 + 26 + 10 = 62 characters. 

Now you have 6 places, which gives you 62^6 possible combinations.
That is 56.800.235.584 ~ 57 billion combinations. 
This is a space of possible hash values - N.
--------------
To compute collisions let's use the formula 

Pcollision = K^2 / 2N

Which is a very rough approximation of collision probability

Now let's see the result table for a number of items in a table - K

# items     | Probability of collision
---------------------------------------
10          |  1.7 * 10^-9
100         |  1.7 * 10^-7
1K          |  1.7 * 10^-5
10K         |  1.7 * 10^-3
100K        |  0.17

This formula can only be used for small K, but it shows that given 100K entries in the hash table you would roughly have 17% chance of collision.

Links

Collision probability

2
  • 3
    Thanks for your instructive comment. But I think you calculated Pcollision = K^2 / N in your table rather than Pcollision = K^2 / 2N? Apr 3, 2020 at 21:14
  • 1
    Are there mathematical proofs that these truncated forms of the hash algorithms have the same qualities as the full version? Aug 29, 2022 at 14:14
11

Easy hash :)

private string Hash(string str)
{
    var allowedSymbols = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".ToCharArray();
    var hash = new char[6];

    for (int i = 0; i < str.Length; i++)
    {
        hash[i % 6] = (char)(hash[i % 6] ^ str[i]);
    }

    for (int i = 0; i < 6; i++)
    {
        hash[i] = allowedSymbols[hash[i] % allowedSymbols.Length];
    }

    return new string(hash);
}
3
  • 5
    This algorithm has a high collision rate due to the XOR here hash[i % 6] ^ str[i]. OP states that the input string is case-insensative, for both a-z and A-Z the highest two bits are the same for all characters. Even if you used all the normal printable ASCII characters (0x20-0x7e) the top two bits are still identical for 66% of the character set.
    – Syon
    Aug 29, 2013 at 2:09
  • Fits Perfectly for me. I had to generate a color based on an name and an degree of nested elements. jsfiddle.net/fgg8xx2k example is written in Typescript
    – Venson
    Jul 12, 2016 at 15:18
  • I found this function is very useful for my use, but it does have a problem of high collision rate. My solution is use to MD5 to hash my str first, and then use this function to get a user friendly output. It seems to resolve the issue for me.
    – Feng Jiang
    Sep 19, 2020 at 19:34
4

The best solution is almost certainly to use SHA1, convert to Base62 (although Base64 would be much easier as it's built in to the framework Convert.ToBase64String. You'll have to do some looking for a decent Base62 library), and then truncate the output to 6 bytes.

I would not use GetHashCode() as it has a history of collision problems. (I'm not trying to claim that this specific bug would apply to you, only mentioning this as evidence that GetHashCode hasn't been implemented well in the past.)

I also would not implement a custom hashing algorithm, it's extremely easy to accidentally write an algorithm with a high collision rate. A lot of research and scrutiny has gone in to SHA1 and the other major hashing algorithms, and you'd be very hard pressed to come up with anything better.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.