3 ms·
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
by gojomo 16y ago
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)
- apgwoz 16y agoI did overlook that, so yes, this should work properly. Thanks! One thing to note is that Random.next() is protected, so it's gotta be random.nextInt(map.size()).
- gojomo 16y agoSorry to have referred to you in third-person; wasn't sure you were reading this thread. Thanks for the correction; I've changed my code fragment.