In his hypothetical "using imaginary iterator() on AbstractMap" O(n) solution, he's overlooking that the Set returned by keySet() has an iterator, and doesn't involve any reallocation/copying. So randomKey() can be:

  int index = random.nextInt(map.size());
  for(String key : map.keySet()) {
    if(index==0) return key;
    index--;
  }

Abstractly, maps aren't the right structure for quick/constant-time random-choice. He could possibly choose an internal implementation that was better at offering random-choice, but that's unlikely to be the optimal implementation for other map uses. He could maintain a parallel structure during inserts that allows constant-draws later. Or do one array shuffle after all inserts, before all draws (if that fits the usage pattern).

(edit: code corrected per replies below)