Necesito implementar una estructura en Java que sea una lista de clave-valor (de tipos Integer-String) y quiero barajarla.

Básicamente, me gustaría hacer algo así.

    public LinkedHashMap<Integer, String> getQuestionOptionsMap(){

    LinkedHashMap<Integer, String>  shuffle = new LinkedHashMap<Integer, String> ();

    if (answer1 != null)
        shuffle.put(new Integer(1), answer1);
    if (answer2 != null)
        shuffle.put(new Integer(2), answer2);
    if (answer3 != null)
        shuffle.put(new Integer(3), answer3);
    if (answer4 != null) 
        shuffle.put(new Integer(4), answer4);

    Collections.shuffle(shuffle);
    return shuffle;
}

Sin embargo, HashMap no se puede barajar.

Podría obtener aleatoriamente una clave del mapa hash y luego devolver el elemento vinculado, pero estoy seguro de que esta no es la mejor solución para mi problema.

¿Hay alguna forma mejor?

Gracias por adelantado.