Re: Implementing isEqual: and hash
Re: Implementing isEqual: and hash
- Subject: Re: Implementing isEqual: and hash
- From: Peter Duniho <email@hidden>
- Date: Sat, 23 Aug 2008 21:28:24 -0700
Date: Sat, 23 Aug 2008 17:52:21 -0700
From: "Adam R. Maxwell" <email@hidden>
Well, if your hash values collide, they collide regardless of the
hash table. As long as you've got a well-distributed hash function,
any collisions generated by the hash table implementation should be
well-distributed as well.
My understanding was that the table might not use all bits of the hash
value, so even differing hash values could be placed in the same
bucket; [...]
Sure. Unless you've got a table that has as many entries as can be
indexed by the full size of your hash value, it _has_ throw some sort
of information away. With a 32-bit hash value, you'd need a 4
billion entry table, which obviously doesn't happen in practice.
I don't know the Cocoa hash table implementations, so I can't speak
for how they work. And any hash table implementation will have some
particular "worst-case" input that could lead to pathological cases.
But, it seems likely that the Cocoa hash table implementations
perform reasonably well given reasonable, well-distributed hash value
inputs.
Basically, don't worry about it until it's actually a problem. Just
make sure you're generating well-distributed hash values, and let
Cocoa worry about how to apply those values with respect to its own
hash table implementations.
Pete
_______________________________________________
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