StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First of all, this depends entirely on which type of Map you're using. But since the JavaRanch thread talks about HashMap, I'll assume that that's the implementation you're referring to. And lets assume also that you're talking about the standard API implementation from Sun/Oracle.</p> <p>Secondly, if you're concerned about performance when iterating through your hash map, I suggest you have a look at <a href="http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html" rel="noreferrer"><code>LinkedHashMap</code></a>. From the docs:</p> <blockquote> <p><em>Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.</em> </p> </blockquote> <h3>HashMap.entrySet()</h3> <p>The source-code for this implementation is available. The implementation basically just returns a new <code>HashMap.EntrySet</code>. A class which looks like this:</p> <pre><code>private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); // returns a HashIterator... } // ... } </code></pre> <p>and a <code>HashIterator</code> looks like</p> <pre><code>private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } // ... } </code></pre> <p>So there you have it... Thats the code dictating what will happen when you iterate through an entrySet. It walks through the entire array which is as long as the maps capacity.</p> <h3>HashMap.keySet() and .get()</h3> <p>Here you first need to get hold of the set of keys. This takes time proportional to the <em>capacity</em> of the map (as opposed to <em>size</em> for the LinkedHashMap). After this is done, you call <code>get()</code> once for each key. Sure, in the average case, with a good hashCode-implementation this takes constant time. However, it will inevitably require lots of <code>.hashCode</code> and <code>.equals</code> calls, which will obviously take more time than just doing a <code>entry.value()</code> call.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload