public static final Map<Integer, Integer> foo2(final int size) {
        final List<Integer> values = new ArrayList<Integer>(size);
        final Map<Integer, Integer> out = new HashMap<Integer, Integer>(size*5);
        for (int i = 0; i < size; i++) values.add(i, i);
        Collections.shuffle(values);
        int i = 0;
        for (int j : values) out.put(i++,j);
        return out;
    }

final static transient Random r = new Random();
final public static Map<Integer, Integer> foo(final int size) {
    final Map<Integer, Integer> out = new HashMap<Integer, Integer>(size*5);
    final List<Integer> values = new ArrayList<Integer>(size);
    int i;

    for (i = 0; i < size; i++) {
        values.add(i, i);
    }
    for (; i > 0; i--) {
        out.put(new Integer(i), values.remove(r.nextInt(i)));
    }
    return out;
}