Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <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&lt;K&gt; keySet() { Set&lt;K&gt; 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 &lt; 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>
    singulars
    1. This table or related slice is empty.
    1. POHow expensive is a call to java.util.HashMap.keySet()?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USluis.espinal
    1. USluis.espinal
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou wrote "A call to keySet() on most Map implementations will be constant time." This is plain false and just based on the **false assumption** that a Hashmap avoids collisions most of the time. In fact a Hashmap only avoids a singnificant number of collisions, depending on its filling factor (the more the Hashmap is filled, the more you get collisions). But a default Hashmap uses a fill factor of about 85%, which means that you'll get 1 collision on about half cases (for random accesses). An in average you'll get about 1.5 values to traverse to get the good one.
      singulars
      1. PO
      1. USverdy_p
    2. COAnd this also depends on how good the values are distributed on their computed hash(): if your hash() function is not correctly written to correctly randomize the bits of the all the possible source values they intend to hash, the results will be much poorer, and you'll get many more collisions. So you should have written ""A call to keySet() on most Map implementations will be performed in a O(1) time." without warranty that this O(1) time will small (there are even worst cases were it could be O(n) with a bad hash() function !)
      singulars
      1. PO
      1. USverdy_p
    3. CONote that the builtin hash() functions for native types (byte, short, int, long, float, double) are extremely basic and do **not** create really randomized distribution of bits in the 32-bit patterns returned as hash ! This means that HashMap<int,...> does not warranty at all a constant time, and not even a O(1) access time for many easily reproducible worst cases (in that case the HashMap behaves like an unordered list with O(n) access time!, only mitigated by the HashMap fill factor, which is too large in my opinion and should be reduced to 50% instead of the default 85%....)
      singulars
      1. PO
      1. USverdy_p
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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