Is the search operation selector objectForKey: of the NSDictionary class of order 1 time complexity like a hashtable?
I hate to have a mostly-link answer, but everything you might want to know and more is here: Exposing NSDictionary
This is the code suggested for objectForKey:
- (id)objectForKey:(id)aKey
{
NSUInteger sizeIndex = _szidx;
NSUInteger size = __NSDictionarySizes[sizeIndex];
id *storage = (id *)object_getIndexedIvars(dict);
NSUInteger fetchIndex = [aKey hash] % size;
for (int i = 0; i < size; i++) {
id fetchedKey = storage[2 * fetchIndex];
if (fetchedKey == nil) {
return nil;
}
if (fetchedKey == aKey || [fetchedKey isEqual:aKey]) {
return storage[2 * fetchIndex + 1];
}
fetchIndex++;
if (fetchIndex == size) {
fetchIndex = 0;
}
}
return nil;
}
As Bartosz Ciechanowski says:
Worse case performance is linear
He proves that there is definitely object instance == checking before an isEqual test. And a lot more.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments