由于我在处理时间复杂度,所以我一直在搜索使用列表、映射和类的一些标准方法的Oracle 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中存储的元素数量。
谢谢。
values()
只是以某种方式“复制”HashMap,那么它怎么可能达到O(1)
的效率呢? - Pacerier