0

For example, I have:

List<HashMap<Integer,Edge>> gfAdjacencyList = new ArrayList<HashMap<Integer,Edge>>(); 
for(int v : gfAdjacencyList.get(u).keySet()){ //u is an int 
    //do stuff
}

What is the run time of gfAdjacencyList.get(u).keySet()? I can't find the run time on the Java documentation

14wml
  • 4,048
  • 11
  • 49
  • 97
  • Um, keySet().size()? It is not clear what you mean by "run-time". If you are asking the run-time of a List dereference, .keySet()'s runtime would be inconsequential here. – rmlan Mar 15 '17 at 16:33
  • It's O(1). What is returned is a *view* on the HashMap. I.e. it's a set that uses the existing underlying HashMap. No copy is made. For example, the set's contains() method just delegates to the map's containsKey() method. – JB Nizet Mar 15 '17 at 16:35
  • The more relevant point is what you are going to do with the keys in that loop. If you are using the key to get values from the `HashMap`, then a better approach will be to use `map.entrySet()`. – Jos Mar 15 '17 at 16:44
  • @rmlan I mean what is the `O()` bound for getting all the keys in the hashmap using `.keyset()`? – 14wml Mar 15 '17 at 17:06
  • @redflar3 all I'm doing with `int v` is pushing it onto a stack and using `v` to lookup and insert into another hashmap, so I don't think I would need `map.entrySet()`. Although if I were using all the values in the hashmap, why would `map.entrySet()` be better? – 14wml Mar 15 '17 at 17:08
  • @JBNizet Really?? My intuition would be that it would take `O(n)` b/c you would have to iterate through the entire hashmap, but I don't have a strong understanding of how hashmaps are implemented in java. Could you explain a little more how a hashmap is a set and how being a set allows getting the keys in `O(1)`? – 14wml Mar 15 '17 at 17:10
  • @15ongm the best way to understand is to look at the implementation. It basically does `return new Set { public boolean contains(Object o) { return this.containsKey(o); } ... }`. In short, the keySet is a wrapper class that implements Set by delegating to the map. – JB Nizet Mar 15 '17 at 17:18
  • @15ongm even though Hash lookups are O(1), they have a constant factor difference with the lookup approach.. lots of discussion here http://stackoverflow.com/questions/46898/how-to-efficiently-iterate-over-each-entry-in-a-map – Jos Mar 15 '17 at 17:31

0 Answers0