int target = N;
int index = 0;
for (Map.Entry<String,Foo> it : foos.entrySet()) {
    if (index == target) {
        return it.getValue();
    }
    index++;
}

List<Entry<String,Foo>> randAccess = new ArrayList<Entry<String,Foo>>(foos.entrySet());

randAccess.get(N)