iOS 常见集合对象的时间复杂度

昨天在写一个字典判断是否包含 Key 的时候，发现自己写混了

if ([dic.allKeys containsObject:key]) {
     // Do To
}

写成了上面这个，发现怎么用下来时间好像有点久
原来是将其用成数组了，其实是可以直接用：

if ([dic objectForKey:key]) {
     // Do To
}

下面一个怎么说都比上面数目方式寻找时间复杂度要低一点的
于是想着先回顾下，我们常见的 集合对象 方法的时间复杂度。

NSArray / NSMutableArray

• containsObject; indexOfObject; removeObject均会遍历元素查看是否匹配，复杂度等于或小于 O（n）
• objectAtIndex；firstObject；lastObject; addObject; removeLastObject这些只针对栈顶，栈底的操作时间复杂度都是 O(1)
• indexOfObject:inSortedRange:options:usingComparator:使用的是二分查找，时间复杂度是O(log n)

NSSet / NSMutableSet (集合类型是无序并且没有重复元素的)

• addObject; removeObject; containsObject都是按照 O(1) 来的。
  需要注意的是将数组转成Set 时，会将重复元素合并为一个，并且失去排序。

NSDictionary / NSMutableDictionary

• 添加和删除元素都是 O(1)

回过头来看，那 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;
}

上面的代码是从__NSDictionaryI类的角度编写的， 具体的可以看看文中的这个探索的过程，发现自己还是很年轻。

文中最后得出的结论：是在糟糕的情况下：objectForKey 是线性的，😒
但是正常情况下是OK 的，所以我们还是可以放心使用的，还是高效的