Implementing -hash and -isEqual for a geo coordinate class

Question

I have an object which stores a latitude/longitude/altitude, and need reliable and fast -hash and isEqual implementations. I am using double to store all of the primitives.

The accepted answer for Best practices for overriding isEqual: and hash, looks good, but it only talks about integer values.

My question is how to deal with doubles, since they aren't precise values. I want to compare the primitives within 8 decimal places, which is already quite a bit more accurate than the GPS chip itself.

Here is what I've come up with so far, have I done it right or does it need improvement?

My -isEqual: implementation is fairly simple:

- (BOOL)isEqualToAGPoint:(AGPoint *)otherPoint
{
  if (fabs(otherPoint->latitude - latitude) > 0.00000001)
    return NO;

  if (fabs(otherPoint->longitude - longitude) > 0.00000001)
    return NO;

  if (fabs(otherPoint->altitude - altitude) > 0.00000001)
    return NO;

  return YES;
}

But I'm not so sure about my -hash implementation:

- (NSUInteger)hash
{
  NSUInteger prime = 31;
  NSUInteger result = 1;

  result = prime * result + lround(latitude * 100000000);
  result = prime * result + lround(longitude * 100000000);
  result = prime * result + lround(altitude * 100000000);

  return result;
}

A quick test demonstrates it seems to work as I need it to:

// all three have the same longitude and altitude, while a and b have slightly different (but should be considered identical) latitudes, while c's latitude is just different enough to be considered not equal to the a and b
AGPoint *a = [[AGPoint alloc] initWithLatitude:-16.922608127 longitude:145.77124538 altitude:2.74930134];
AGPoint *b = [[AGPoint alloc] initWithLatitude:-16.922608128 longitude:145.77124538 altitude:2.74930134];
AGPoint *c = [[AGPoint alloc] initWithLatitude:-16.922608147 longitude:145.77124538 altitude:2.74930134];

NSLog(@"a == b: %i", (int)[a isEqual:b]);
NSLog(@"a == c: %i", (int)[a isEqual:c]);
NSLog(@"hash for a: %lu  b: %lu c: %lu", (unsigned long)[a hash], (unsigned long)[b hash], (unsigned long)[c hash]);

output:
  a == b: 1
  a == c: 0
  hash for a: 3952407433  b: 3952407433 c: 3952405511

Does this look correct?

Where will `-hash` be called repeatedly on the same object? Adding another `NSUInteger` instance variable to this object would increase my memory consumption by ~30MB. I'm going to have a lot of these objects. — Abhi Beckert, Jan 01 '12 at 09:24
"which is already quite a bit more accurate than the GPS chip itself" Why did you choose to do this? Possible forward compatibility? If the data are significant to 1e-5? You gain nothing, and any datum with values in the 1e-6, 1e-7, 1e-8 ranges are "garbage" anyway. What happens near the equator or the Greenwich meridian? — jim mcnamara, Jan 01 '12 at 14:31
Apple is using doubles everywhere, so I decided to do the same. I primarily want isEqual/hash to check if a point is a `copy` of another point, not if a user is in the same location as they were previously (which is possible but highly unlikely). An 8th decimal place is accurate to somewhere between 1.1mm and 1/100,000th of a millimetre, depending on which value/where in the world. These values will primarily be used for drawing, which also uses floating point values everywhere. I don't want to convert a double to an int and then convert the int back to a double when drawing it. — Abhi Beckert, Jan 01 '12 at 16:58

score 1 · Accepted Answer · edited Jan 01 '12 at 19:36

1

You're in trouble with values like (0.5 ± 0.015625)*1e-8. The absolute difference of the coordinate is less than the tolerance, but the rounding leads to different integers.

EDIT:

This means two objects can be considered equal, but have different hash codes. Inconsistent equality and hash code can pose serious problems if you ever use a hash map.

A solution is to compare each object's hash inside isEqual:

- (BOOL)isEqualToAGPoint:(AGPoint *)otherPoint
{
  if ([otherPoint hash] != [self hash])
    return NO;

  if (fabs(otherPoint->latitude - latitude) > 0.00000001)
    return NO;

  if (fabs(otherPoint->longitude - longitude) > 0.00000001)
    return NO;

  if (fabs(otherPoint->altitude - altitude) > 0.00000001)
    return NO;

  return YES;
}

edited Jan 01 '12 at 19:36

Abhi Beckert

32,787
12
83
110

answered Jan 01 '12 at 05:12

Daniel Fischer

181,706
17
308
431

When would this cause problems? The 8th decimal place is around 1 millimetre or less (depending on distance from equator). The iPhone's GPS receiver is accurate to a few meters in ideal conditions, so I don't see any issues with two objects being considered equal by `NSDictionary` or `NSSet` if they're 1mm apart? – Abhi Beckert Jan 01 '12 at 09:21
2

The problem is that two objects can be considered equal, but have different hash codes. Inconsistent equality and hash code can pose serious problems if you ever use a hash map. – Daniel Fischer Jan 01 '12 at 09:26
I see. How can I solve this? Perhaps `isEqual` should just be `[self hash] == [otherPoint hash]`? – Abhi Beckert Jan 01 '12 at 10:21
1

Two objects are equal if they're close and have equal hash code? That would work. On the other hand, perhaps it would be better to store the coordinates as integers, multiples of 1/1000-th second or something. That depends on what you need to do with them. – Daniel Fischer Jan 01 '12 at 10:29
Apple is using doubles everywhere in the location API (the variables are actually `CLLocationDegrees`/etc, which is defined by Apple as a double), and they will eventually be used to either draw to the screen as `CGFloat` values (double on 64 bit, float on 32 bit) or exported to an XML file (where it will be a string with 8 decimal places). Keeping all that in mind, sticking with `CLLocationDegrees`/`double` seems like the correct thing to do. – Abhi Beckert Jan 01 '12 at 17:07
Is there any reason to do the equality math *and* compare the hash code? Seems like I could get away with only comparing the hash code? – Abhi Beckert Jan 01 '12 at 17:08
1

Yes, if the API uses `double`, stick with that. And yes, there is a pretty good reason, hash functions are in general not injective, so far away locations can have the same hash. If you can prove that that won't happen, hash would be enough. But the hash is an integer, probably 64 bits, long, lat and alt can each take something in the region of 10^9 values (after rounding), makes 10^27 or so locations, while a 64-bit integer can take only about 1.8*10^19 values. So your hash can't be injective. – Daniel Fischer Jan 01 '12 at 17:16
Thanks for your help. I'll update my `-isEqualToAGPoint:` method to compare the hash before doing the other comparisons. Do you mind if I edit your answer to include the results of these comments? – Abhi Beckert Jan 01 '12 at 18:30
But you're multiplying with 10^8 before the round, so I supposed you have an accuracy of something like 10^(-7) or 10^(-8) degrees, similarly for altitude. Re edit: go ahead, if I don't like it, I can re-edit :) – Daniel Fischer Jan 01 '12 at 18:35

Implementing -hash and -isEqual for a geo coordinate class

1 Answers1