Так как я работаю с временной сложностью, я просматривал библиотеку классов Java оракула для временной сложности некоторых стандартных методов, используемых в списках, картах и классах. (более конкретно, ArrayList, HashSet и HashMap)
Теперь, глядя на страницу HashMap javadoc, они действительно говорят только о методах get()
и put()
.
Методы, которые мне все еще нужно знать, следующие:
remove(Object o)
size()
values()
Я думаю, что remove()
будет такой же сложностью, как get()
, O(1)
, предполагая, что у нас нет гигантского HashMap с равными хэш-кодами и т.д. и т.д....
Для size()
я также предполагал бы O(1)
, так как HashSet, который также не имеет порядка, имеет метод size()
со сложностью O(1)
.
Тот, о котором я понятия не имею, - это values()
. Я не уверен, будет ли этот метод как-то "скопировать" HashMap, задав временную сложность O(1)
, или если ему придется перебирать по HashMap, делая сложность равной количеству элементов, хранящихся в HashMap.
Спасибо.