Какова временная сложность метода keySet () класса java.util.HashMap?

Question

Я пытаюсь реализовать алгоритм плоской развертки, и для этого мне нужно знать временную сложность метода java.util.HashMap 'keySet () . Я подозреваю, что это O (n log n). Я прав?

Уточнение: Я говорю о временной сложности метода keySet (); итерация по возвращенному множеству, очевидно, займет время O (n).

Answer 1

На самом деле, получение набора ключей стоит O(1) и дешево. Это потому, что HashMap.keyset () возвращает фактический объект KeySet, связанный с HashMap.

Возвращенный набор - не копия ключей, а оболочка для фактического состояния HashMap. Действительно, если вы обновите набор, вы сможете изменить состояние HashMap; например вызов clear() на устройстве очистит HashMap!

Answer 2

Конечно, это будет O (1). Все, что он делает, это возвращает объект-оболочку в HashMap.

Если вы говорите о обходе набора ключей, то это O (n), поскольку каждый следующий вызов () равен O (1), и это необходимо выполнить n раз.

Answer 3

Это должно быть выполнимо за O (n) время ... Карта хеша обычно реализуется как большой массив блоков, размер блока (обычно) прямо пропорционален размеру карты хешей. Чтобы извлечь набор ключей, необходимо выполнить итерацию сегмента, и для каждого элемента набора должен быть получен ключ (либо через промежуточный набор, либо через итератор с прямым доступом к блоку) ...

** РЕДАКТИРОВАНИЕ: Как уже отмечали другие, фактический метод keyset () будет запущен за O (1) время, однако итерация по набору ключей или передача его в выделенную коллекцию будет операцией O (n). Не совсем уверен, какой вы ищете **

Answer 4

Чтобы ответить на комментарий «итерация по возвращенному набору займет явно O (n) время», это на самом деле не правильно для комментариев документа из HashMap:

Итерации по представлениям коллекции требуют времени, пропорционального «емкости» экземпляра HashMap (количество сегментов) плюс его размер (количество отображений ключ-значение). Таким образом, очень важно не устанавливать начальную емкость слишком высокой (или слишком низким коэффициентом загрузки), если важна производительность итерации.

Другими словами, для итерации по возвращенному Set потребуется O(n + c), где n - это размер карты, а c - это ее емкость, а не O(n). Если были выбраны неправильная начальная емкость или коэффициент загрузки, значение c могло бы перевесить фактический размер карты с точки зрения времени итерации.

Answer 5

Java-коллекции занимают много места и поэтому не занимают много времени. Я полагаю, что этот метод O (1). Коллекция просто сидит там.