Implementing isEqual: and hash
I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? tia, Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Sat, Aug 23, 2008 at 11:41 PM, Graham Cox [EMAIL PROTECTED] wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? If you're deferring both -isEqual: and -hash to an NSString, you'll be fine. Hash doesn't need to be anything complicated (although a good distribution is nice), just as long as two objects that return YES for -isEqual: return the same value for -hash (the inverse doesn't have to be true). Phil ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Sat, Aug 23, 2008 at 7:41 AM, Graham Cox [EMAIL PROTECTED] wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? The implementation of -hash should *always* match the implementation of -isEqual:. If you compare primitives in -isEqual:, you should combine them (using xor or the like) in -hash. If you compare objects by calling -isEqual: on them, you should combine their hashes (using xor or the like). If you do some of each, combine them all. If you compare only one thing for equality, return it (if it's a primitive) or its hash value (if you call isEqual: on it). Mike ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On 23 Aug 2008, at 10:13 pm, Michael Ash wrote: On Sat, Aug 23, 2008 at 7:41 AM, Graham Cox [EMAIL PROTECTED] wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? The implementation of -hash should *always* match the implementation of -isEqual:. If you compare primitives in -isEqual:, you should combine them (using xor or the like) in -hash. If you compare objects by calling -isEqual: on them, you should combine their hashes (using xor or the like). If you do some of each, combine them all. If you compare only one thing for equality, return it (if it's a primitive) or its hash value (if you call isEqual: on it). Thanks guys - works fine. cheers, Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
Le 23 août 08 à 13:41, Graham Cox a écrit : I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? Yes, that the way to do it. To understand what an hash is and how it is used, I suggest you read the hash table article in wikipedia. http://en.wikipedia.org/wiki/Hash_table Hash tables are used in Cocoa in NSDictionary, NSSet, NSHashTable, NSHashMap and maybe more. When you understand how it works, choosing the implementation should be obvious. ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On 23 Aug 2008, at 9:52 pm, Jean-Daniel Dupas wrote:
Le 23 août 08 à 13:41, Graham Cox a écrit :
I have a class for which equality can be defined as having the same
internal string value (which happens to be a UUID-turned-string). I
can easily implement isEqual: based on that but the docs say I also
need to implement -hash. Any pointers on what is a good way to do
that? Could I just safely defer to the -hash returned by the string
in question?
Yes, that the way to do it.
To understand what an hash is and how it is used, I suggest you read
the hash table article in wikipedia.
http://en.wikipedia.org/wiki/Hash_table
Hash tables are used in Cocoa in NSDictionary, NSSet, NSHashTable,
NSHashMap and maybe more. When you understand how it works, choosing
the implementation should be obvious.
Thanks for that. I'm pretty familiar with hash tables in general (and
in quite a bit of theory too) but I wasn't able to find out what Cocoa
uses for its hashing function or how good this needed to be to work
well with the built-in classes. However, by deferring to the string I
can avoid the issue altogether.
For curiosity's sake, I would be interested to know what sort of
hashing functions Cocoa does use. I haven't come across the need to
generate one for any of my custom classes before so it's not something
I need right now, but every bit of knowledge is worth having.
For example, here's a very crude hash function I used in a very simple
symbol table implementation from a long while ago. I imagine most hash
functions in Cocoa would be more sophisticated.
unsigned long ZHashTable::Hash( const char* name )
{
register unsigned long h = 1;
register char* p = (char*) name;
register char c;
while(( c = *p++ ) != 0 )
h *= (unsigned long) c;
return h % kHashTableSize;
}
cheers, Graham___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
Le 23 août 08 à 15:39, Graham Cox a écrit :
On 23 Aug 2008, at 9:52 pm, Jean-Daniel Dupas wrote:
Le 23 août 08 à 13:41, Graham Cox a écrit :
I have a class for which equality can be defined as having the
same internal string value (which happens to be a UUID-turned-
string). I can easily implement isEqual: based on that but the
docs say I also need to implement -hash. Any pointers on what is a
good way to do that? Could I just safely defer to the -hash
returned by the string in question?
Yes, that the way to do it.
To understand what an hash is and how it is used, I suggest you
read the hash table article in wikipedia.
http://en.wikipedia.org/wiki/Hash_table
Hash tables are used in Cocoa in NSDictionary, NSSet, NSHashTable,
NSHashMap and maybe more. When you understand how it works,
choosing the implementation should be obvious.
Thanks for that. I'm pretty familiar with hash tables in general
(and in quite a bit of theory too) but I wasn't able to find out
what Cocoa uses for its hashing function or how good this needed
to be to work well with the built-in classes. However, by deferring
to the string I can avoid the issue altogether.
For curiosity's sake, I would be interested to know what sort of
hashing functions Cocoa does use. I haven't come across the need to
generate one for any of my custom classes before so it's not
something I need right now, but every bit of knowledge is worth
having.
For example, here's a very crude hash function I used in a very
simple symbol table implementation from a long while ago. I imagine
most hash functions in Cocoa would be more sophisticated.
unsigned long ZHashTable::Hash( const char* name )
{
register unsigned long h = 1;
register char* p = (char*) name;
register char c;
while(( c = *p++ ) != 0 )
h *= (unsigned long) c;
return h % kHashTableSize;
}
Look into the CoreFoundation sources. as Cocoa primitive are tool free
bridged, they use the same hash functions. They is even a special case
for NSString into the CFString.c file.
http://www.opensource.apple.com/darwinsource/10.5.4/CF-476.14/
You can find Integer and double hash function into ForFoundationOnly.h.
And there is another generic hash function into CFData.c
According to the Leopard release notes, we can guess that thoses
function have been updated into Leopard:
Order of values in hashing-based collections
The CoreFoundation and Foundation framework-provided implementations
of hashing-based collections such as dictionaries have changed how
they store elements, so elements may be retrieved in a different order
than in previous releases. The order of elements in hashing-based
collections is undefined and can change at any time, so developers
must never rely on the order that elements are enumerated, or returned
from a function like CFDictionaryGetKeysAndValues(). This is true even
for cases where a developer may be trying to manipulate the hash codes
of the objects in order to achieve some particular ordering.
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 7:41 AM, Graham Cox wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? Graham, Is your object mutable? (That is, is any attribute of the attribute which affects equality or hash mutable? In this case that sounds like the internal string value which is a UUID.) If so, that opens up another can of worms to consider. Jim ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 8:57 AM, Jean-Daniel Dupas wrote: Look into the CoreFoundation sources. as Cocoa primitive are tool free bridged, they use the same hash functions. They is even a special case for NSString into the CFString.c file. http://www.opensource.apple.com/darwinsource/10.5.4/CF-476.14/ Those are not the sources for CoreFoundation. Those are the sources for 'CFLite', which is a dumbed-down version of CoreFoundation used by IOKit. The real CoreFoundation is not open source. There is no guarantee that CFLite and CoreFoundation are the same. In fact, there are known differences. -Jeff ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 5:13 AM, Michael Ash wrote: On Sat, Aug 23, 2008 at 7:41 AM, Graham Cox [EMAIL PROTECTED] wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? The implementation of -hash should *always* match the implementation of -isEqual:. And as Jim alluded, -hash must not depend on mutable properties; if the hash changes while the object is in a hashing collection, you'll end up with random crashes. If you compare primitives in -isEqual:, you should combine them (using xor or the like) in -hash. If you compare objects by calling -isEqual: on them, you should combine their hashes (using xor or the like). If you do some of each, combine them all. What's the motivation for combining hashes in this case? I've wondered what is the best thing to do when isEqual: is based on comparing multiple ivars; I typically just use one of them for the hash. thanks, Adam smime.p7s Description: S/MIME cryptographic signature ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 11:38 AM, Adam R. Maxwell wrote: On Aug 23, 2008, at 5:13 AM, Michael Ash wrote: On Sat, Aug 23, 2008 at 7:41 AM, Graham Cox [EMAIL PROTECTED] wrote: I have a class for which equality can be defined as having the same internal string value (which happens to be a UUID-turned-string). I can easily implement isEqual: based on that but the docs say I also need to implement -hash. Any pointers on what is a good way to do that? Could I just safely defer to the -hash returned by the string in question? The implementation of -hash should *always* match the implementation of -isEqual:. And as Jim alluded, -hash must not depend on mutable properties; if the hash changes while the object is in a hashing collection, you'll end up with random crashes. Right. Thus, it's a bad idea to use mutable properties in isEqual:. If you find yourself tempted to do that, impement an isEqualToMyClass: method rather than isEqual:. If you compare primitives in -isEqual:, you should combine them (using xor or the like) in -hash. If you compare objects by calling - isEqual: on them, you should combine their hashes (using xor or the like). If you do some of each, combine them all. What's the motivation for combining hashes in this case? I've wondered what is the best thing to do when isEqual: is based on comparing multiple ivars; I typically just use one of them for the hash. It's a documented requirement of the isEqual: and hash methods that the hash must be the same when isEqual: returns YES. Thus, whatever logic that returns YES in isEqual: must have some kind of match in hash. -Jeff ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 12:26 PM, Jeff Johnson wrote: If you compare primitives in -isEqual:, you should combine them (using xor or the like) in -hash. If you compare objects by calling - isEqual: on them, you should combine their hashes (using xor or the like). If you do some of each, combine them all. What's the motivation for combining hashes in this case? I've wondered what is the best thing to do when isEqual: is based on comparing multiple ivars; I typically just use one of them for the hash. It's a documented requirement of the isEqual: and hash methods that the hash must be the same when isEqual: returns YES. Thus, whatever logic that returns YES in isEqual: must have some kind of match in hash. -Jeff Also, you're probably less likely to have collisions by combining. ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 10:26 AM, Jeff Johnson wrote:
On Aug 23, 2008, at 11:38 AM, Adam R. Maxwell wrote:
On Aug 23, 2008, at 5:13 AM, Michael Ash wrote:
On Sat, Aug 23, 2008 at 7:41 AM, Graham Cox
[EMAIL PROTECTED] wrote:
I have a class for which equality can be defined as having the
same internal
string value (which happens to be a UUID-turned-string). I can
easily
implement isEqual: based on that but the docs say I also need to
implement
-hash. Any pointers on what is a good way to do that? Could I
just safely
defer to the -hash returned by the string in question?
The implementation of -hash should *always* match the implementation
of -isEqual:.
And as Jim alluded, -hash must not depend on mutable properties; if
the hash changes while the object is in a hashing collection,
you'll end up with random crashes.
Right. Thus, it's a bad idea to use mutable properties in isEqual:.
If you find yourself tempted to do that, impement an
isEqualToMyClass: method rather than isEqual:.
CF collection callbacks are also handy in cases like this, since you
can use equality functions that may not be correct for the general
case of isEqual:.
If you compare primitives in -isEqual:, you should combine them
(using
xor or the like) in -hash. If you compare objects by calling -
isEqual:
on them, you should combine their hashes (using xor or the like). If
you do some of each, combine them all.
What's the motivation for combining hashes in this case? I've
wondered what is the best thing to do when isEqual: is based on
comparing multiple ivars; I typically just use one of them for the
hash.
It's a documented requirement of the isEqual: and hash methods that
the hash must be the same when isEqual: returns YES. Thus, whatever
logic that returns YES in isEqual: must have some kind of match in
hash.
If I have
@interface Test : NSObject
{
id ivar1;
id ivar2;
}
@end
@implementation Test
- (BOOL)isEqual:(id)other
{
if ([other isKindOfClass:[self class]] == NO) return NO;
return ([ivar1 isEqual:(Test *)other-ivar1] [ivar2 isEqual:
(Test *)other-ivar2]);
}
- (unsigned)hash { return [ivar1 hash]; }
@end
I believe it's sufficient to use [ivar1 hash], since the object is
only equal if ivar1 is equal in both objects. I was just curious to
know what you gain by using ([ivar1 hash] ^ [ivar2 hash]); is it
possible to know in general if it reduces collisions? Presumably that
depends on the hash table implementation as well.
--
Adam
smime.p7s
Description: S/MIME cryptographic signature
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 2:05 PM, Adam R. Maxwell wrote:
If I have
@interface Test : NSObject
{
id ivar1;
id ivar2;
}
@end
@implementation Test
- (BOOL)isEqual:(id)other
{
if ([other isKindOfClass:[self class]] == NO) return NO;
return ([ivar1 isEqual:(Test *)other-ivar1] [ivar2 isEqual:
(Test *)other-ivar2]);
}
- (unsigned)hash { return [ivar1 hash]; }
@end
I believe it's sufficient to use [ivar1 hash], since the object is
only equal if ivar1 is equal in both objects. I was just curious
to know what you gain by using ([ivar1 hash] ^ [ivar2 hash]); is it
possible to know in general if it reduces collisions? Presumably
that depends on the hash table implementation as well.
--
Adam
Right, it depends on the hash table implementation, which we don't
know. Theoretically, it seems likely to reduce collisions. This could
only be confirmed by real-world performance tests, though.
-Jeff
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 9:43 PM, Jeff Johnson wrote:
On Aug 23, 2008, at 2:05 PM, Adam R. Maxwell wrote:
If I have
@interface Test : NSObject
{
id ivar1;
id ivar2;
}
@end
@implementation Test
- (BOOL)isEqual:(id)other
{
if ([other isKindOfClass:[self class]] == NO) return NO;
return ([ivar1 isEqual:(Test *)other-ivar1] [ivar2 isEqual:
(Test *)other-ivar2]);
}
- (unsigned)hash { return [ivar1 hash]; }
@end
I believe it's sufficient to use [ivar1 hash], since the object is
only equal if ivar1 is equal in both objects. I was just curious
to know what you gain by using ([ivar1 hash] ^ [ivar2 hash]); is it
possible to know in general if it reduces collisions? Presumably
that depends on the hash table implementation as well.
--
Adam
Right, it depends on the hash table implementation, which we don't
know. Theoretically, it seems likely to reduce collisions. This
could only be confirmed by real-world performance tests, though.
-Jeff
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/cocoa-dev
%40standin.se
This email sent to [EMAIL PROTECTED]
I think theoretically, it seems likely to increase collisions. If
ivar1 and ivar2 aren't independent of each other, xor can cluster
different values causing lots of collisions. Consider what happens if
ivars are laid out serially say 0x0100 and 0x0200, xor and you
get 0x300, and let's say that another completely different object's
ivars are 0xff000600 and 0xff000700, and you still get 0x300,
collision.
The hash table implementation has nothing to do with this, the problem
occurs before the hash table has any chance to make it even worse. (If
you always return the same hash value, the hash table has nothing to
work with in spreading the stored objects.)
/Pierre
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
Date: Sat, 23 Aug 2008 12:05:44 -0700
From: Adam R. Maxwell [EMAIL PROTECTED]
[...]
- (BOOL)isEqual:(id)other
{
if ([other isKindOfClass:[self class]] == NO) return NO;
return ([ivar1 isEqual:(Test *)other-ivar1] [ivar2 isEqual:
(Test *)other-ivar2]);
}
- (unsigned)hash { return [ivar1 hash]; }
@end
I believe it's sufficient to use [ivar1 hash], since the object is
only equal if ivar1 is equal in both objects. I was just curious to
know what you gain by using ([ivar1 hash] ^ [ivar2 hash]); is it
possible to know in general if it reduces collisions?
If you combine the hash values correctly, it will reduce collisions.
Note that the previously mentioned xor technique is not generally
considered correct and can in fact lead to increased collisions,
not fewer.
One reasonably common technique for combining hash values into a new
hash value is to multiply and accumulate using a prime number.
There's probably some good math theory as to what a nice prime number
to pick might be, but I've seen enough examples that use 37 that
that's what I usually use. :)
For example:
- (unsigned) hash
{
unsigned ret = 0;
ret += ret * 37 + [ivar1 hash];
ret += ret * 37 + [ivar2 hash];
return ret;
}
Note the redundant multiply and add in the first line. Writing the
code that way makes it easy to add/remove members if for some reason
the data structure should change in the future. But it would be just
as correct to simply initialize ret to the first hash value, of course.
Presumably that
depends on the hash table implementation as well.
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.
Pete
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
On Aug 23, 2008, at 5:20 PM, Peter Duniho wrote: Date: Sat, 23 Aug 2008 12:05:44 -0700 From: Adam R. Maxwell [EMAIL PROTECTED] [...] Note the redundant multiply and add in the first line. Writing the code that way makes it easy to add/remove members if for some reason the data structure should change in the future. But it would be just as correct to simply initialize ret to the first hash value, of course. Thanks for the example...I need to find time to do some profiling with this. Presumably that depends on the hash table implementation as well. 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; that may be a misinterpretation of [1]. I find CFSet/CFBag/ CFDictionary to be one of the more confusing implementations in CF-Lite. thanks, Adam [1] http://www.mulle-kybernetik.com/artikel/Optimization/opti-7.html smime.p7s Description: S/MIME cryptographic signature ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Implementing isEqual: and hash
Date: Sat, 23 Aug 2008 17:52:21 -0700 From: Adam R. Maxwell [EMAIL PROTECTED] 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 (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
