Converting System.Decimal to System.Guid

Question

I have a big dictionary where the key is decimal, but the GetHashCode() of System.Decimal is disasterously bad. To prove my guess, I ran a for loop with 100.000 neigboring decimals and checked the distribution. 100.000 different decimal numbers used only 2 (two!!!) different hashcodes.

Decimal is represented as 16 bytes. Just like Guid! But the GetHashCode() distribution of Guid is pretty good. How can I convert a decimal to Guid in C# as cheap as possible? Unsafe code is OK!

---

EDIT: The test was requested, so here is the code:

decimal d = 96000000000000000000m;
Dictionary<int, int> hashcount = new Dictionary<int, int>();
int length = 100000;
for (int i = 0; i < length; i++)
{
    int hashcode = d.GetHashCode();
    int n;
    if (hashcount.TryGetValue(hashcode, out n))
    {
        hashcount[hashcode] = n + 1;
    }
    else
    {
        hashcount.Add(hashcode, 1);
    }
    d++;
}

Console.WriteLine(hashcount.Count);

This prints 7. I do not remember the starting decimal that gave me 2.

Muskogee

Can you elaborate on the 100.000 decimals you tested? I just tried a small test of 1.000 neighbouring decimals and got 1.000 different hash codes. – Maemaeander

Enumerable.Range(0, 100000).Select(i => 1000000M + i/100000000000000M).Select(d => d.GetHashCode()).Distinct().Count() returns 10 which demonstrates that the distribution is bad when the significands are very close. – Maemaeander

@Martin: See this Eric Lipper's blog entry blogs.msdn.com/b/ericlippert/archive/2010/03/22/… – Anglesite

@abatishchev: Eric's blog doesn't explain why it's quite so bad as that. – Sanfo

@Martin: Wow - it's even worse in .NET 4... I only get one value then! – Sanfo

I've just tried my answer with the same numbers - I got 100,000 distinct values :) – Sanfo

Decimal.GetHashCode() is computed by converting the value to double. That produces 8 bytes, the upper and lower set of 4 are xor-ed. You are having a problem because double can only store 15 significant digits. – Marasco

Answer 1

EXTREMELY HACKY SOLUTION (but probably fastest possible)

public static class Utils
{
    [StructLayout(LayoutKind.Explicit)]
    struct DecimalGuidConverter
    {
        [FieldOffset(0)]
        public decimal Decimal;
        [FieldOffset(0)]
        public Guid Guid;
    }

    private static DecimalGuidConverter _converter;
    public static Guid DecimalToGuid(decimal dec)
    {
        _converter.Decimal = dec;
        return _converter.Guid;
    }
    public static decimal GuidToDecimal(Guid guid)
    {
        _converter.Guid = guid;
        return _converter.Decimal;
    }
}

---

// Prints 000e0000-0000-0000-8324-6ae7b91d0100
Console.WriteLine(Utils.DecimalToGuid((decimal) Math.PI));

// Prints 00000000-0000-0000-1821-000000000000
Console.WriteLine(Utils.DecimalToGuid(8472m));

// Prints 8472
Console.WriteLine(Utils.GuidToDecimal(Guid.Parse("00000000-0000-0000-1821-000000000000")));

Unlive

Hmmmmmm, I always thought overlapping fields to only apply when crossing native boundaries. Wow, it works! Learnt something new today :) +1 – Distrust

WAAAAAOOOOO, this is genius! Studying the Guid.GetHashCode() in Reflector, hashvalue depend primarily on the first 8 bytes of the Guid. While in the decimal, the first 8 bytes varry the least. Any idea, how to reverse the byte order, or swap the first and the last 8 bytes? – Muskogee

@user256890: Since you want it as fast as possible, just use the same trick again: csharp.pastebin.com/Jqg9F9HA – Unlive

It would need to be profiled, but I rather suspect that this is faster: for DecimalToGuid: return *((Guid*)((void*)&dec)); and for GuidToDecimal: return *((decimal*)((void*)&guid)); - you need to add an unsafe, but a union struct is already inherently unsafe - so no change introduced there. – Pliers

I think the above may work when using DecimalToGuid(decimal dec) but not GuidToDecimal(Guid guid). Here's an example of a guid that returns an invalid decimal "{dc78377c-89e6-43a9-8155-bd6e395d041a}" – Epos

Warning: Type of "Decimal" cannot represent the full of 2^128 different values due to its special bit useage rules. The method in this answer will likely cause irreversible conversions and data broken. – Request

Answer 2

If you're just trying to get a different hash algorithm, there's no need to convert to a Guid. Something like this:

public int GetDecimalHashCode(decimal value)
{
    int[] bits = decimal.GetBits(value);
    int hash = 17;
    foreach (int x in bits)
    {
        hash = hash * 31 + x;
    }
    return hash;
}

(Obviously substitute a different algorithm if you want.)

Admittedly this still involves creating an array, which isn't ideal. If you really want to create a Guid you could use the code above to get the bits and then a long Guid constructor passing in appropriate values from the array.

I'm somewhat suspicious of the decimal hashcode being so bad though. Do you have some sample code for that?

Sanfo

How would you use this when storing decimal values in a dictionary? Surely the dictionary will invariably use the original decimal::GetHashCode()? – Unlive

Just pass your custom IEqualityComparer in dictionary constructor – Prognosticate

@Unlive But the hashcode doesn't have to be unique within a dictionary, so that wouldn't matter so much. – Oscillator

@Rowland: sure, but dictionary performances decrease with bad hashing (the famous ~O(1) key-lookup time will only work with very good hashing) – Prognosticate

@Rowland: I don’t see how your comment relates to mine at all. – Unlive

@Unlive I was responding to the fact that the dictionary would refer to decimal's GetHashCode() - whilst not brilliant (if the OP's sample data is distributed in a similar manner to their test data), it would still work, so it maybe a case of worrying unduely which implementation gets called. – Oscillator

@Timwi: The constructor of Dictionary can accept an IEqualityComparer; one could thus implement a DecimalComparer class which would behave as indicated here. Note that if one computes hash codes based upon binary representation, one must compare equality likewise and be aware of what it "means"; notably, 1.0m and 1.00m will compare as distinct. – Inexcusable

Answer 3

Convert your decimal value to byte array, and then create a guid from it:

public static byte[] DecimalToByteArray (decimal src) 
{
    using (MemoryStream stream = new MemoryStream()) 
    {
        using (BinaryWriter writer = new BinaryWriter(stream))
        {
            writer.Write(src);
            return stream.ToArray();
        }
    }
}

Decimal myDecimal = 1234.5678M;
Guid guid = new Guid(DecimalToByteArray(myDecimal));

Tania

While I bet it works, it does not look fast. This code is to be used in a dictionary! – Muskogee

Dude, if you want it to work fast - say it! don't immediately give a down vote... people are here to help you. My solution answer you question - nowhere in your question did you say it HAVE to be fast. – Tania

By the way - I tested it on 100000 values and it took 00:00:00.0754544 seconds (75 ticks) - believe me - that's fast enough – Tania

I did say "cheap". And I did not vote it down. It was someone else. – Muskogee

@user: while Nissim's answer certainly wouldn't be fast, i doubt that anything will be very fast for this. Are the keys being generated each time you create the dictionary, or are they static bits of data (ie keys from some data source)? – Nonalcoholic

Answer 4

The distribution of GUID is good as it is meant to be unique...

What is the range of numbers used for this? The default GetHashcode() implementation for Decimal might only take a certain range of values into consideration.

Distrust