Re: NSMapTable with C strings as keys
Re: NSMapTable with C strings as keys
- Subject: Re: NSMapTable with C strings as keys
- From: Jean-Daniel Dupas <email@hidden>
- Date: Tue, 28 May 2013 09:03:28 +0200
Le 28 mai 2013 à 08:25, Oleg Krupnov <email@hidden> a écrit :
> Hi Jens,
>
> I guess you may be right. But… two questions in this regard:
>
> 1. I thought that "isEqual" method is alternative to "hash" method,
> because searching by key and searching by hash are two mutually
> exclusive methods of looking up values, aren't they?
>
No, they aren't. The hash is used to speed up the lookup.
The HashTable first uses the hash to find in which bucket the element is, and as the hash is not guarantee to be unique, it then use the isEqual method to determine what element in this bucket in the one you are looking for.
> 2. What hash function you'd suggest in my case, that would calculate
> unsigned int on output, for C strings? Because calculating hash
> functions (such as md5) may be computationally expensive, which could
> undermine my entire idea of sparing extra few calls on creating
> NSStrings :)
The main issue with using c string, is memory management of your keys. NSString does that using ref counting, but you will have to take care of everything if you are using C string.
Avoiding NSString without being sure this will impact the performance is just "premature optimization".
That said, there is 2 famous hash functions that are usually used for this kind of hashing: CityHash (http://code.google.com/p/cityhash/) and MurmurHash (http://code.google.com/p/smhasher/)
> Thanks!
>
> On Tue, May 28, 2013 at 9:08 AM, Jens Alfke <email@hidden> wrote:
>>
>> On May 27, 2013, at 10:46 PM, Oleg Krupnov <email@hidden> wrote:
>>
>> Now, the problem is that sometimes when I try to get a value from the
>> table, the MapTableKeyComparator function is not called at all, and
>> NSMapGet returns NULL, thought immediate dump of the table shows that
>> all previous records are perfectly present in the table.
>>
>>
>> Probably because you haven’t implemented a hash function, only an equals
>> function. I’m guessing NSMapTable’s default hash function merely hashes the
>> key pointer itself, which means that if you pass it a different pointer to
>> an equal C string, it won’t find anything.
>>
>> —Jens
>>
>
> _______________________________________________
>
> 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
-- Jean-Daniel
_______________________________________________
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