HashMap方法的时间复杂度
由于我正在研究时间复杂性，我一直在搜索oracle Java类库，以了解列表，地图和类中使用的一些标准方法的时间复杂性。 （更具体地说，ArrayList，HashSet和HashMap）
现在，在查看HashMap javadoc页面时 ，他们只是真正谈论get()和put()方法。
我仍然需要知道的方法是：
remove(Object o) size() values()
我认为remove()将与get() ， O(1)具有相同的复杂性，假设我们没有具有相同hashCodes的巨型HashMap等等……
对于size()我还假设为O(1) ，因为HashSet（也没有顺序size()具有复杂度为O(1)的size()方法。
我不知道的是values() – 我不确定这个方法是否会以某种方式“复制”HashMap，给出O(1)的时间复杂度，或者它是否必须迭代HashMap，使复杂性等于HashMap中存储的元素数量。
谢谢。
源代码通常很有帮助： http ： //kickjava.com/src/java/util/HashMap.java.htm
-
remove:O（1） -
size:O（1） -
values:O（n）（在遍历迭代器时）
删除代码（如在HashMap的rt.jar中）是：
/** * Removes and returns the entry associated with the specified key * in the HashMap. Returns null if the HashMap contains no mapping * for this key. */ final Entry removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry prev = table[i]; Entry e = prev; while (e != null) { Entry next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }
显然，最坏的情况是O（n）。
您可以随时查看源代码并自行检查。
无论如何……我曾经检查过源代码，我记得的是有一个名为size的变量，总是保存HashMap的项目数，所以size()是O(1) 。
搜索：O（1 + k / n）
插入：O（1）
删除：O（1 + k / n）其中k为no。 添加到同一LinkedList的碰撞元素（k个元素具有相同的hashCode）
插入是O（1），因为您在LinkedList的头部添加了元素。
在给定良好的hashFunction的情况下，摊销时间复杂度接近于O（1）。 如果你太在意查找时间，那么尝试使用BinarySearchTree而不是Java的Default实现解析冲突，即LinkedList