Hashing function

This is a discussion on Hashing function within the C++ Programming forums, part of the General Programming Boards category; Can some on recommend what hashing function I could use for two points, (x,y) co ordinates?...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    38

    Hashing function

    Can some on recommend what hashing function I could use for two points, (x,y) co ordinates?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    What data type would x and y be?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jul 2009
    Posts
    38
    x and y would be ints

  4. #4
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    I think it depends more on the distribution of points.

    For example, if the points are random and fairly sparse then it might be good to just sort by x or y-coordinate. Also if the points tend to fall in a line then you could sort by the axis parallel to that line.
    If the points tend to group together or form perpendicular lines, though, that could be rather inefficient. You'd have to try something else, and knowing where the data comes from is probably the best way to know how to hash it well.

    You could also represent the coordinates as a long int, specifically:
    Code:
    long int coord = ((long int)x << 16) + y;
    and use a standard hash function on that.
    Consider this post signed

  5. #5
    Registered User
    Join Date
    Jul 2009
    Posts
    38
    it would be for the game of life, so not sure under which category it falls under

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    In case you're having trouble deciding over the hashes in the above link. The FNV-1a hash is often a good choice.

    Or if I needed something really fast, I'd be temped to do:
    Code:
    hash = ((x * prime1 + prime2) ^ y) * prime3 + prime4;
    Where primes 1 through 4 are values often found in LCRNGs.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    In the past, I've used a 64-to-32-bit downmixing function for this. See the section on this page called "64 bit to 32 bit Hash Functions". You pack your two 32-bit coordinates into a single 64-bit long value, pass it to this function, and out comes a 32-bit hash result.

    Another possibility would be the 3-way 32-bit mixer on the same page in section "Robert Jenkins' 96 bit Mix Function" -- it takes three inputs. Two of those inputs would be your coordinates, the third input is some random (but fixed) value.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 03:25 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Troubleshooting Input Function
    By SiliconHobo in forum C Programming
    Replies: 14
    Last Post: 12-05-2007, 06:18 AM
  4. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  5. Replies: 28
    Last Post: 07-16-2006, 11:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21