Time Complexity of HashMap methods

Question

Since i'm working around time complexity, i've been searching through the oracle Java class library for the time complexity of some standard methods used on Lists, Maps and Classes. (more specifically, ArrayList, HashSet and HashMap)

Now, when looking at the HashMap javadoc page, they only really speak about the get() and put() methods.

The methods i still need to know are:

remove(Object o) size() values() 

I think that remove() will be the same complexity as get(), O(1), assuming we don't have a giant HashMap with equal hashCodes, etc etc...

For size() i'd also assume O(1), since a HashSet, which also has no order, has a size() method with complexity O(1).

The one i have no idea of is values() - I'm not sure whether this method will just somehow "copy" the HashMap, giving a time complexity of O(1), or if it will have to iterate over the HashMap, making the complexity equal to the amount of elements stored in the HashMap.

Thanks.

Answer 1

The source is often helpful: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O(1)
• size: O(1)
• values: O(n) (on traversal through iterator)

Answer 2

The code for remove(as in rt.jar for HashMap) is:

/**  * 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<K,V> removeEntryForKey(Object key) {     int hash = (key == null) ? 0 : hash(key.hashCode());     int i = indexFor(hash, table.length);     Entry<K,V> prev = table[i];     Entry<K,V> e = prev;      while (e != null) {         Entry<K,V> 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; } 

Clearly, the worst case is O(n).