Re: NSUInteger hash
Re: NSUInteger hash
- Subject: Re: NSUInteger hash
- From: "Michael Ash" <email@hidden>
- Date: Sat, 16 Aug 2008 17:21:25 -0400
On Sat, Aug 16, 2008 at 3:57 PM, Steve Wart <email@hidden> wrote:
> Hi all,
>
> I'm just getting started with Cocoa and I'm trying to implement hash and
> isEqual: methods according to the recommendations in the coding guidelines.
>
> To implement a hash method I would normally just hash the receiver's
> instance variables together and xor the result, but this only works if the
> instance variables are objects.
>
> However my instance variables are NSPoints, which are defined as structs,
> not objects. The C programmer in me wants to cast the floats into integers
> and hash those, but we are in a 64-bit world now, and I assume that 32-bit
> algorithms may not give a good result.
>
> Maybe I'm trying too hard, but it's important for what I'm doing that I
> don't have a lot of collisions so I want a good quality hash function.
>
> What's the standard way of hashing non-object values in Cocoa?
For primitives, the hash value can generally just be itself.
Recall that NSUinteger is just a typedef for either int (in 32-bit) or
long (in 64-bit). So it's just an integer.
You have a pair of floats. The simplest thing to do would be to cast
them to NSUInteger, thereby truncating off the decimal bits, and then
XOR the result together:
- (NSUInteger)hash { return (NSUInteger)p.x ^ (NSUInteger)p.y; }
Note that this stops making much sense if you expect your points to be
fractional values, and you want different fractional values to be
considered unequal*. In that case, I'd recommend simply using the
whole float bit-pattern as your hash:
static NSUInteger CGFloatHash(CGFloat f) { return *(NSUInteger *)&f; }
- (NSUInteger)hash { return CGFloatHash(p.x) ^ CGFloatHash(p.y); }
(This works in both 32-bit and 64-bit since NSUInteger and CGFloat
happen to be the same size. If you use this in real code then I
recommend at least adding a check that the sizes are in fact equal and
failing in some loud, obvious way if they aren't so you don't end up
reading junk.)
Note that if you ever expect to have both positive zero and negative
zero in your points then this will fall apart, as negative zero and
positive zero can compare as equal but don't have matching bit
patterns. The solution to this is left as an exercise to the reader,
with a pointer to the IEEE 754 spec.
* Note that in general it's bad to compare floating point numbers with
non-integral parts for equality anyway. Two numbers which you think
should be equal may well not be due to rounding error in the
calculations which generated them. There's even an optional gcc
warning flag, -Wfloat-equal, which will produce a warning any time the
== operator is used on floating point numbers. Thus if your instance
variables are NSPoints, and you expect those points to have fractional
values, and you're using those variables as part of your equality
comparison, you're probably doing something wrong. (Although if you
only expect two floats to be equal when you've merely saved a copy of
one to look up later, then that can be reasonably expected to work.)
Mike
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden