NSMutableSet реализован как связанный список?

Question

Поскольку вы не можете получить доступ к элементу NSMutableSet случайным образом, означает ли это, что он реализован как связанный список?

т.е. будет ли он быстрее вставлять / удалять, чем NSMutableArray?

Answer 1

Исходный код доступен, поэтому вы можете посмотреть: CFSet.c .(Это аналог Core Foundation для NSSet, но они в основном одинаковы.) Это хеш-таблица.

Но вы также должны иметь в виду, что NSArray на самом деле не реализовано какмассив.Вы можете увидеть реализацию здесь: CFArray.c .Может быть, эту статью в блоге легче понять, хотя она немного устарела (~ 5 лет.)

Answer 2

Нет. Время поиска будет быстрее, потому что будут использоваться хэши.

Answer 3

Я не программист Objective-C, но обычно наборы реализуются через хеш-таблицы, которые (если все сделано правильно) будут давать O (1) для вставки, удаления и поиска.

Технически, хэши обычно дают вам O (M), где M - размер ключа, но для набора вы просто используете идентификатор объекта ключа, который является постоянным, поэтому вы возвращаетесь к O 1).

Answer 4

Наборы обычно реализуются с помощью сбалансированных бинарных деревьев поиска (например, красно-черные деревья, деревья avl).