13

I want to get 64 bit hash code of given string. How can i do that with fastest way ? There is a ready method for get 32 bit hash code but i need 64 bit.

I am looking for only integer hashing. Not md5.

Thank you very much.

C# 4.0

12
  • 2
    I am going to store crawled urls at the database. So for minimizing the collision and having maximum speed i need 64 bit hash code. Jan 11, 2012 at 13:53
  • 1
    If fast is the only requirement, you can simply assign the 32 bit hash value to a 64 bit variable.
    – Codo
    Jan 11, 2012 at 13:54
  • 1
    It is not the only requirement. The main aim is decreasing the possible collision. There can be up to 10 million urls. Jan 11, 2012 at 13:59
  • 2
    Yes but if you calculate with math it has very big risk of collision when there are 10 million strings with 32 bit :) 64 bit is best solution for me. Jan 11, 2012 at 14:02
  • 1
    The birthday paradox gives that you will have a risk of one in 368936 for a collision with 10 million rows. That is if the hash has a perfect distribution. 1 - e ^ ( -10^7 * (10^7 - 1) / ( 2 * 2^64 ) ) Jan 11, 2012 at 15:08

6 Answers 6

13

Simple solution:

public static long GetHashCodeInt64(string input)
{
    var s1 = input.Substring(0, input.Length / 2);
    var s2 = input.Substring(input.Length / 2);

    var x= ((long)s1.GetHashCode()) << 0x20 | s2.GetHashCode();

    return x;
}
10
  • Kirill this one or Pratik one would work faster ? And would they produce same result ? Jan 11, 2012 at 14:19
  • @MonsterMMORPG, this will be faster, they will produce different hashes. Jan 11, 2012 at 14:22
  • 2
    @MonsterMMORPG, Also, if you are storing these hashes prefer MD5 or any other hash implementation (e.g. @Pratik solution), because future version of a string might use a different algorithm for calculating the object's hash code. Jan 11, 2012 at 14:26
  • 1
    @KirillPolishchuk, there's a bug with this piece of code on some machines (can't pin point the causing spec). If the hashcode of the first half is negative. Consider casting both hashcodes to UInt64 before the SHIFT and OR operations.
    – giladrv
    Mar 29, 2015 at 14:03
  • 1
    The values from GetHashCode should never be stored to permanent storage like a database. There's no guarantee you'll get consistent values the next time you run your application (especially if you made updates). Sep 26, 2019 at 18:53
7

Since the question was about making URL I presume you always need the same hashed 64 bit int. GetHashCode is not relyable in this way. To make a hash with few collisions i use this one.

public static ulong GetUInt64Hash(HashAlgorithm hasher, string text)
{
    using (hasher)
    {
        var bytes = hasher.ComputeHash(Encoding.Default.GetBytes(text));
        Array.Resize(ref bytes, bytes.Length + bytes.Length % 8); //make multiple of 8 if hash is not, for exampel SHA1 creates 20 bytes. 
        return Enumerable.Range(0, bytes.Length / 8) // create a counter for de number of 8 bytes in the bytearray
            .Select(i => BitConverter.ToUInt64(bytes, i * 8)) // combine 8 bytes at a time into a integer
            .Aggregate((x, y) =>x ^ y); //xor the bytes together so you end up with a ulong (64-bit int)
    }
}

To use it just pass whatever hashalgorithm you prefer

ulong result = GetUInt64Hash(SHA256.Create(), "foodiloodiloo")
//result: 259973318283508806

or

ulong result = GetUInt64Hash(SHA1.Create(), "foodiloodiloo")
//result: 6574081600879152103

Difference between this one and the accepted answer is that this one XOR's all the bits, and you can use whatever algorithm you want

4
  • 1
    I think this answer is seriously underrated. GetHashCode() is, as you point out, NOT GUARANTEED to give the same value between invocations. That means that if you store the hash and try to match it later, you will have funny bugs. Also, you use all the bytes in the bytes array (the current top answer has a bug there) Aug 18, 2020 at 13:43
  • Seems like this approach (mainly bytes.Length / 8) will not work with some algorithms (like SHA1) that produce a hash of indivisible length (e.g. SHA1 produces a 20 bytes hash).
    – Nick
    Nov 23, 2020 at 3:31
  • @Nick you are right. Had a bug in the code before that only used the first 16 bytes if you used SHA1. Updated it now to resize the array to a multiple of 8. Thank you! Nov 24, 2020 at 14:55
  • @Daniel Nice. Do you think XORing the chunks of bytes from a SHA hash will avoid collisions like a full SHA hash? Isn't a XOR of [1, 5] and [5, 1] the same despite them being different sequences. I'm just trying to understand if XOR is a safe option for hash bytes over 8-bytes.
    – Nick
    Nov 24, 2020 at 22:25
5

This code is from Code Project Article - Convert String to 64bit Integer

 static Int64 GetInt64HashCode(string strText)
{
    Int64 hashCode = 0;
    if (!string.IsNullOrEmpty(strText))
    {
        //Unicode Encode Covering all characterset
          byte[] byteContents = Encoding.Unicode.GetBytes(strText);
        System.Security.Cryptography.SHA256 hash = 
        new System.Security.Cryptography.SHA256CryptoServiceProvider();
        byte[] hashText = hash.ComputeHash(byteContents);
        //32Byte hashText separate
        //hashCodeStart = 0~7  8Byte
        //hashCodeMedium = 8~23  8Byte
        //hashCodeEnd = 24~31  8Byte
        //and Fold
        Int64 hashCodeStart = BitConverter.ToInt64(hashText, 0);
        Int64 hashCodeMedium = BitConverter.ToInt64(hashText, 8);
        Int64 hashCodeEnd = BitConverter.ToInt64(hashText, 24);
        hashCode = hashCodeStart ^ hashCodeMedium ^ hashCodeEnd;
    }
    return (hashCode);
}  
8
  • 1
    Pratik is your solution or Orentet solution better ? Jan 11, 2012 at 13:57
  • @MonsterMMORPG You try & let me know if it satisfies your requirement, but as per my understanding of the given question, This best suits you!
    – Pratik
    Jan 11, 2012 at 14:03
  • Thanks. It seems like best solution. Jan 11, 2012 at 14:04
  • 12
    Wow this is using extreme cpu power. I compared this with strText.GetHashCode() method and this is 376 times slower. Jan 11, 2012 at 21:29
  • 9
    Pretty slow, endian dependent and weird. Why are you reading 3 64 bit integers from the SHA-256 hash and xor them? That doesn't gain you anything over just reading a single 64 bit integer and using it. Apr 18, 2013 at 20:12
5

I'll introduce a new possible answer. xxHash is very fast. Check out the benchmarks here:

https://cyan4973.github.io/xxHash/

It has a NuGet package: https://www.nuget.org/packages/System.Data.HashFunction.xxHash

Or open sources: https://github.com/brandondahler/Data.HashFunction/blob/master/src/System.Data.HashFunction.xxHash/xxHash_Implementation.cs

The other answers here are either 1. questionable as to their real prevention of collision or 2. just wrappers around the large and slow existing HashAlgorithm implementations.

xxHash is not cryptographic strength, but it would seem to fit the bill better for what you need. Its:

  1. 64 bits all the way,
  2. Bench-marked faster than others.
  3. Has good distribution for maximized collision avoidance.
3

I assume you are refering to the MD5 hashing algorithm for your current use?

You can do a SHA 256 for twice the length....

http://msdn.microsoft.com/en-us/library/system.security.cryptography.sha256.aspx

Extract...

byte[] data = new byte[DATA_SIZE];
byte[] result;
SHA256 shaM = new SHA256Managed();
result = shaM.ComputeHash(data);
2
  • I am looking for only integer hashing. Jan 11, 2012 at 13:58
  • 2
    @MonsterMMORPG you know that you can trivially change from a byte[8] <===> Int64, right? So... as long as you have 8 bytes output, you have an Int64 Jan 11, 2012 at 14:11
3

I have used the @Kirill solution. I'm a little bit weird and I don't like "var" (I guess it's because I come from c++) so I make a variant:

string s1 = text.Substring(0, text.Length / 2);
string s2 = text.Substring(text.Length / 2);

Byte[] MS4B = BitConverter.GetBytes(s1.GetHashCode());
Byte[] LS4B = BitConverter.GetBytes(s2.GetHashCode());
UInt64 hash = (UInt64)MS4B[0] << 56 | (UInt64)MS4B[1] << 48 | 
              (UInt64)MS4B[2] << 40 | (UInt64)MS4B[3] << 32 |
              (UInt64)LS4B[0] << 24 | (UInt64)LS4B[1] << 16 | 
              (UInt64)LS4B[2] << 8  | (UInt64)LS4B[3] ;

I'm not very sure about the order of the bytes, depends on the machine, (whether is little-endian or big-endian) but, who cares? it's just a number (a hash). Thank you @Kirill, it was very useful to me!

3
  • If you want efficiency as I think you do, maybe you should avoid creating the two byte arrays and shift the integers themselves?
    – Djof
    Aug 30, 2013 at 15:13
  • 3
    @chasques, if you don't like var, then you probably also don't like C++ auto ....
    – Sebastian
    Oct 8, 2013 at 14:17
  • The values from GetHashCode should never be stored to permanent storage like a database. There's no guarantee you'll get consistent values the next time you run your application (especially if you made updates). Sep 26, 2019 at 18:52

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.