How expensive is a call to java.util.HashMap.keySet()?

Question

I implemented a sparse matrix as List<Map<Integer,Double>>.
To get all entries of row i I call list.get(i).keySet(). How expensive is this call?

I also used the trove library for an alternative implementation as List<TIntDoubleHashMap>.
What's the cost of calling list.get(i).keys(), here?

Do you have any further ideas of how to implement an efficient sparse matrix?
Or can you provide a list of existing implementations in java?

Answer 1

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).

-- Edited to show the following code snippet (since verdy_p below doesn't read well, and likes to go off the tangent): --

// 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()));
}

-- end of edit --

A call to keySet() on most Map implementations will be constant time.

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).

I would also assume that is the case for most (if not all) Map implementations that are backed by arrays.

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).

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.

For classes under java.util.concurrent (like ConcurrentHashMap), you'll have to take other considerations to determine how expensive they are.

---

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 significantly faster than the later since array traversal will always be faster than traversing through pointers (or references in this Java specific case.)

Now, if you take both list.get(i).keySet() and the iteration of the set into account, with a linked list implementation, that will be O(n^2). So instead of doing list.get(i).keySet(), you should use an iterator (see pseudocode below, it obviates generic syntax for clarity)

This is O(n^2) for lists that do not implement java.util.RandomAccess (like LinkedList):

for( int i = 0; i < list.size(); i++ )
{
   Set keySet = list.get(i).keySet();
   for( Integer key : keySet.iterator() )
   {
      ... stuff (assuming constant time) ...
   }
}

This is O(n) for that same type of List implementations:

for( Map m : list.iterator() )
{
   for( Integer key : m.keySet() )
   {
      ... stuff (assuming constant time) ...
   }
}