В Objective-C (и Swift при использовании Foundation) коллекции NSArray и NSSet — это два разных типа контейнеров, предназначенных для хранения объектов, но с разными внутренними устройствами, семантикой доступа и производительностью при выполнении операций, особенно поиска.**
Ключевое различие между ними заключается в структуре хранения данных и в времени доступа к элементам.
1. NSArray — упорядоченная коллекция
Что это такое:
NSArray — это упорядоченный список объектов, аналог обычного массива. Элементы в NSArray располагаются в том порядке, в котором они были добавлены.
Внутреннее устройство:
- **Реализован как динамический массив указателей.
** - **Каждый элемент хранится в определённой позиции.
** - **Быстрый доступ по индексу (O(1)).
** - **Поиск по значению осуществляется линейно — O(n).
**
Операции поиска:
Когда вы ищете объект в NSArray, используется метод containsObject: или indexOfObject:, который последовательно перебирает массив, сравнивая элементы с искомым.
Пример:
**NSArray \*array = @[@"apple", @"banana", @"cherry"];**
**BOOL exists = [array containsObject:@"banana"];**
Этот поиск — линейный: в худшем случае будет пройден весь массив.
2. NSSet — неупорядоченное множество
Что это такое:
NSSet — это неупорядоченное множество уникальных объектов, аналог математического множества.
Внутреннее устройство:
- **Основан на хэш-таблице.
** - **Каждый объект хэшируется, и по его хэшу определяется место хранения.
** - **Добавление и поиск — амортизированное O(1).
** - **Элементы не имеют порядка.
** - **Не допускает дубликатов.
**
Операции поиска:
Поиск в NSSet происходит через хеширование — то есть почти мгновенно, если реализован -hash и -isEqual: у объектов правильно.
Пример:
**NSSet \*set = [NSSet setWithObjects:@"apple", @"banana", @"cherry", nil];**
**BOOL exists = [set containsObject:@"banana"];**
Здесь поиск будет выполнен за постоянное время — O(1) в среднем случае, потому что NSSet использует хэш-таблицу.
3. Сравнение производительности поиска
| Операция | NSArray | NSSet |
|---|---|---|
| Поиск (containsObject:) | O(n) (линейный) | O(1) (почти мгновенно) |
| --- | --- | --- |
| Добавление | O(1) в конец | O(1) в среднем |
| --- | --- | --- |
| Доступ по индексу | O(1) | ✘ (не поддерживается) |
| --- | --- | --- |
| Удаление | O(n) по значению | O(1) в среднем |
| --- | --- | --- |
| Упорядоченность | Да | Нет |
| --- | --- | --- |
| Поддержка дубликатов | Да | Нет |
| --- | --- | --- |
Таким образом, поиск по NSSet почти всегда быстрее, особенно при большом объёме данных.
4. Практический пример и сравнение времени
**NSMutableArray \*array = [NSMutableArray array];**
**NSMutableSet \*set = [NSMutableSet set];**
**NSString \*target = @"item9999";**
**for (int i = 0; i < 10000; i++) {**
**NSString \*str = [NSString stringWithFormat:@"item%d", i];**
**[array addObject:str];**
**[set addObject:str];**
**}**
**NSDate \*start = [NSDate date];**
**[array containsObject:target];**
**NSTimeInterval arrayTime = [[NSDate date] timeIntervalSinceDate:start];**
**start = [NSDate date];**
**[set containsObject:target];**
**NSTimeInterval setTime = [[NSDate date] timeIntervalSinceDate:start];**
**NSLog(@"NSArray time: %f", arrayTime);**
**NSLog(@"NSSet time: %f", setTime);**
Результат почти всегда покажет, что поиск по NSSet будет в десятки или сотни раз быстрее, особенно при больших объёмах.
5. Почему NSSet быстрее
Потому что:
- **Используется хэш-функция для быстрого определения местоположения объекта;
** - **Поиск не требует прохода по всем элементам;
** - **Наличие ключевых методов -hash и -isEqual: позволяет NSSet оптимизировать сравнение;
** - **Не требует сортировки или проверки порядка.
**
В то время как NSArray не может избежать последовательного сравнения каждого элемента, особенно если объект — пользовательский и не поддерживает прямое сравнение указателей.
6. Особенности и ограничения
6.1. NSSet требует корректной реализации hash и isEqual:
Если вы используете собственные объекты, они должны корректно реализовать:
**\- (NSUInteger)hash {**
**return [self.identifier hash];**
**}**
**\- (BOOL)isEqual:(id)object {**
**if (![object isKindOfClass:[MyClass class]]) return NO;**
**return [self.identifier isEqualToString:((MyClass \*)object).identifier];**
**}**
Без этого NSSet не сможет корректно отличать уникальные значения и выполнять быстрый поиск.
6.2. Нет порядка в NSSet
Если вам нужен порядок следования элементов, используйте NSArray или NSOrderedSet.
NSSet не сохраняет порядок:
**NSSet \*set = [NSSet setWithObjects:@"a", @"b", @"c", nil];**
**NSLog(@"%@", set); // порядок может быть "b, a, c"**
6.3. Уникальность объектов
NSSet не допускает дубликатов. При добавлении двух одинаковых объектов (с точки зрения isEqual:) второй будет проигнорирован.
NSArray, напротив, может содержать повторяющиеся элементы.
6.4. Поддержка в Swift
В Swift эквиваленты:
- **NSArray ↔ Array
**
- **NSSet ↔ Set**
И та же логика применима:
**let arr = ["a", "b", "c", "d"]**
**arr.contains("c") // O(n)**
**let set: Set = ["a", "b", "c", "d"]**
**set.contains("c") // O(1)**
Swift Set работает аналогично NSSet, но типобезопасен и работает быстрее за счёт компиляции без рантайма Objective-C.
7. Когда выбирать NSArray, когда NSSet
| Сценарий | Коллекция |
|---|---|
| Важен порядок элементов | NSArray |
| --- | --- |
| Нужны дубликаты | NSArray |
| --- | --- |
| Часто обращаетесь по индексу | NSArray |
| --- | --- |
| Часто ищете, проверяете наличие элемента | NSSet |
| --- | --- |
| Не нужны дубликаты | NSSet |
| --- | --- |
| Часто выполняете множественные пересечения | NSSet |
| --- | --- |
8. Альтернативы: NSOrderedSet
Если нужно и уникальность, и сохранение порядка, можно использовать NSOrderedSet — это структура, совмещающая особенности NSArray и NSSet:
- **Уникальные элементы (как NSSet);
** - **Фиксированный порядок (как NSArray);
** - **Поиск по значению — быстрее, чем в массиве.
**
Однако NSOrderedSet менее производителен, чем чистый NSSet для поиска.
**