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.
HashMap has complexity of O(1) for insertion and lookup.
It is O(1) only if your hashing function is very good. The Java hash table implementation does not protect against bad hash functions. Whether you need to grow the table when you add items or not is not relevant to the question because it is about lookup time.
Hashtables seem to be O(1) because they have a small constant factor combined with their 'n' in the O(log(n)) being increased to the point that, for many practical applications, it is independent of the number of actual items you are using.
With HashMap, we can achieve an average time complexity of O(1) for the put and get operations and space complexity of O(n).
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)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).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With