Re: NSMapTable with C strings as keys
Re: NSMapTable with C strings as keys
- Subject: Re: NSMapTable with C strings as keys
- From: Oleg Krupnov <email@hidden>
- Date: Tue, 28 May 2013 10:38:23 +0300
I just made the following experiment:
I specified a hash method for my NSMapTable, but it always returns 0.
This seems to force the NSMapGet to always use key comparison for
searching for elements, as hash is always "not unique".
Is this a good idea?
Let me think. The keys are quite short strings, like 5-10 chars.
If we take the expense of calculating hash once for each search, then
comparing hash values is very quick, plus a few string comparisons in
the end if hash is not unique
If we spare on calculating hash, we will compare strings on each
ramification of the binary tree. Besides, it seems that isEqual method
returns BOOL which means the keys will not be sorted, which makes
binary tree search impossible? In this case hash seems the only sane
solution for NSMapTable. Am I right?
On Tue, May 28, 2013 at 10:03 AM, Jean-Daniel Dupas
<email@hidden> wrote:
>
> 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