Implementing String.GetHashCode() manually?

Question

We have a legacy system written in .NET, which we are migrating to Node.js.

The original system uses ("some string value").GetHashCode() to generate some tokens based on user data.

I'm looking for a way to implement this function in JavaScript in order to port this part of the system to Node.js.

Therefore, I'm interested in how String.GetHashCode() actually works. Is there an algorithm documented somewhere? Is it even a stable algorithm or does it change across various .NET versions?

I've tried to find some details on it's implementation, but it's really difficult for me, because .NET is not my primary technology and I'm not really familiar with it's resources and sources of information.

Answer 1

To add on to Bradley's answer This is a stable hash code based off of the 64 bit implmentation of String.GetHashCode() that uses no unsafe code that I wrote up for a answer a while ago.

public static class StringExtensionMethods
{
    public static int GetStableHashCode(this string str)
    {
        unchecked
        {
            int hash1 = 5381;
            int hash2 = hash1;

            for(int i = 0; i < str.Length && str[i] != '\0'; i += 2)
            {
                hash1 = ((hash1 << 5) + hash1) ^ str[i];
                if (i == str.Length - 1 || str[i+1] == '\0')
                    break;
                hash2 = ((hash2 << 5) + hash2) ^ str[i+1];
            }

            return hash1 + (hash2*1566083941);
        }
    }
}

Answer 2

Taken from Microsoft's Reference Source, one implementation is:

        // Gets a hash code for this string.  If strings A and B are such that A.Equals(B), then
        // they will return the same hash code.
        [System.Security.SecuritySafeCritical]  // auto-generated
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
        public override int GetHashCode() {

#if FEATURE_RANDOMIZED_STRING_HASHING
            if(HashHelpers.s_UseRandomizedStringHashing)
            {
                return InternalMarvin32HashString(this, this.Length, 0);
            }
#endif // FEATURE_RANDOMIZED_STRING_HASHING

            unsafe {
                fixed (char *src = this) {
                    Contract.Assert(src[this.Length] == '\0', "src[this.Length] == '\\0'");
                    Contract.Assert( ((int)src)%4 == 0, "Managed string should start at 4 bytes boundary");

#if WIN32
                    int hash1 = (5381<<16) + 5381;
#else
                    int hash1 = 5381;
#endif
                    int hash2 = hash1;

#if WIN32
                    // 32 bit machines.
                    int* pint = (int *)src;
                    int len = this.Length;
                    while (len > 2)
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2;
                        len  -= 4;
                    }

                    if (len > 0)
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                    }
#else
                    int     c;
                    char *s = src;
                    while ((c = s[0]) != 0) {
                        hash1 = ((hash1 << 5) + hash1) ^ c;
                        c = s[1];
                        if (c == 0)
                            break;
                        hash2 = ((hash2 << 5) + hash2) ^ c;
                        s += 2;
                    }
#endif
#if DEBUG
                    // We want to ensure we can change our hash function daily.
                    // This is perfectly fine as long as you don't persist the
                    // value from GetHashCode to disk or count on String A 
                    // hashing before string B.  Those are bugs in your code.
                    hash1 ^= ThisAssembly.DailyBuildNumber;
#endif
                    return hash1 + (hash2 * 1566083941);
                }
            }
        }

This is not stable across .NET versions, and from comments scattered around the string.cs source code, it may not even be stable across AppDomains within the same process.

If you want a real, stable hash code, that can "safely" be persisted outside the AppDomain, look at the hash functions in System.Security.Cryptography. MD5 is acceptable for low security jobs, the SHAx flavors are even better.

True Hashes are one way only, it is not possible to truly reverse a hash, since it is a "lossy" process. If the developers you got your code from claim they can reverse a hash, they were either lying, mistaken, or didn't implement the correct hash.