StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Depends on the class implementing List and Map. If you are using a List class implementing java.util.RandomAccess (ie. ArrayList), then a call to get(i) is O(1). If it is a LinkedList, it will be O(n).</p> <p><strong>-- Edited to show the following code snippet (since verdy_p below doesn't read well, and likes to go off the tangent): --</strong></p> <pre><code>// In HashMap.java, line 867, JDK 1.6.0.24, how much more // constant time do we want? public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } </code></pre> <p><strong>-- end of edit --</strong></p> <p>A call to keySet() on most Map implementations will be constant time.</p> <p>Regarding traversing the keySet() If you are using an array-backed Map implementation (like HashMap), keySet() relies on entrySet() which returns an internal iterator backed by an array. So iteration of keySet() is O(n).</p> <p>I would also assume that is the case for most (if not all) Map implementations that are backed by arrays.</p> <p>For SortedMap implementations (like TreeMap), iterating on its keys will be akin to iterating on a tree from lowest to greatest key. This is equivalent to a failed binary search which is O(n).</p> <p>Both cases appear to be O(n). If you use Eclipse, you can actually look at the code implementing the java classes and get a better idea of their complexity.</p> <p>For classes under java.util.concurrent (like ConcurrentHashMap), you'll have to take other considerations to determine how expensive they are.</p> <hr> <p>To expand a bit more, if you use a linked list, list.get(i).keyset() will be O(n). With ArrayList, it will be O(1). Traversing the keyset will depend on whether you use an array-backed Map (HashMap) or a SortedMap (TreeMap). In both cases, traversing will be O(n) with the former being <em>significantly</em> faster than the later since array traversal will always be faster than traversing through pointers (or references in this Java specific case.)</p> <p>Now, if you take <strong>both</strong> list.get(i).keySet() and the iteration of the set into account, with a linked list implementation, <strong>that</strong> will be O(n^2). So instead of doing list.get(i).keySet(), you should use an iterator (see <strong><em>pseudocode</em></strong> below, it obviates generic syntax for clarity)</p> <p>This is O(n^2) for lists that do not implement java.util.RandomAccess (like LinkedList):</p> <pre><code>for( int i = 0; i < list.size(); i++ ) { Set keySet = list.get(i).keySet(); for( Integer key : keySet.iterator() ) { ... stuff (assuming constant time) ... } } </code></pre> <p>This is O(n) for that same type of List implementations:</p> <pre><code>for( Map m : list.iterator() ) { for( Integer key : m.keySet() ) { ... stuff (assuming constant time) ... } } </code></pre>

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