CODEWITHSUNDEEP
c#.nethash
Jader Dias
Jader Dias

Reputation: 90475

Fastest hash code generator .NET

I'm implementing a custom GetHashCode for the System.Drawing.Point class in C#. My method currently fails the following requirement:

var hashA = MyGetHashCode(new Point(1, 0));
var hashB = MyGetHashCode(new Point(0, 1));
var hashC = MyGetHashCode(new Point(0, 0));
var hashD = MyGetHashCode(new Point(1, 1));
Assert.AreNotEqual(hashA ^ hashB, hashC ^ hashD);

To pass this test I'm sure that using new SHA256Managed().ComputeHash(currentHash) will do. But there is any other faster hashing algorithm? I know SHA256 is all about security, and I don't need that.

Upvotes: 3

Views: 5705

Answers (7)

Brian
Brian

Reputation: 25834

If you know in advance that your point value is between 0 and N, you can use hashcode = X+Y*N; This is a rather obvious possible hash. It's not random at all, has ugly repetition, and is generally pretty silly. It's equivalent to concatenating the bits of your two points, assuming N is a power of 2. And it's got perfect uniform distribution and no collisions.

I've used this strategy to excellent effect in the past, but admit it has some real (but obvious) limitations. The biggest one being what happens when N is large enough that N^2 won't fit into your hash value (i.e. painful collisions.

Upvotes: 0

Fantius
Fantius

Reputation: 3862

I don't know what your application is, but you may be looking for Zobrist hashing.

http://en.wikipedia.org/wiki/Zobrist_hashing

It can be updated incrementally, which makes it very fast.

Upvotes: 0

Marc Gravell
Marc Gravell

Reputation: 1062780

A simple hash? how about something like:

 (17 * point.X) + (23 * point.Y);

Or for more obvious entropy:

int hash = -1047578147;
hash = (hash * -1521134295) + point.X;
hash = (hash * -1521134295) + point.Y;

(numbers from C#'s anonymous type code)

Upvotes: 6

Jorge Córdoba
Jorge Córdoba

Reputation: 52123

A simple Elf hash implementation (it's in delphi, shoudl be easy to translate)

function ElfHash(id : string; tableSize : integer) : integer;
var
  i : integer;
  h,x : longint;
begin
  h := 0;
  // Obtener el valor numérico
  for i := 1 to Length(id) do
  begin
    h := (h shl 4) + Ord(id[i]);

    x := h and $F0000000;
    if x <;>; 0 then
       h = h xor (x shr 24) xor x;
  end;
  // Ajustar al tamaño de la tabla
  result := h mod tableSize;
end;

Upvotes: 1

TWA
TWA

Reputation: 12816

Here's an interesting article about hashing speed:

A Hash Function for Hash Table Lookup

Upvotes: 1

mqp
mqp

Reputation: 71945

  • Why are you doing this? Surely System.Drawing.Point has a fine hashing function already?

  • You understand that test doesn't represent a strict requirement, right? Hash codes don't have to be unique.

  • If you really want a really good hash of the coordinates in question, you might want to start at this page about hashing multiple integers.

Upvotes: 3

Joel Martinez
Joel Martinez

Reputation: 47749

I know this isn't going to answer your question, but I must mention for the sake of other readers that you are changing the default behavior of a built in method of the framework. As per the documentation:
http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

The default implementation of the GetHashCode method does not guarantee unique return values for different objects. Furthermore, the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value it returns will be the same between different versions of the .NET Framework. Consequently, the default implementation of this method must not be used as a unique object identifier for hashing purposes.

Upvotes: 1

Related Questions