Apesar do instrutor insistir muito no fato de que a ordem dentro de um set é aleatória (e isso está correto, em quase todos os casos), existe uma exceção. A implementação LinkedHashSet garante que a ordem de iteração é a mesma de adição dos elementos.
Vide https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html
Olá Victor,
O instrutor não está errado quando diz que não é possível garantir a ordem de um set, pois há diferentes implementações para o mesmo, onde algumas não garantem a ordem como o HashedSet ou pode ser ordenado de acordo com a implementação de Comparator dos objetos adicionados como é o caso do TreeSet, sendo assim, tendo uma instância de um Set e não sabendo qual foi a implementação utilizada, não terei como saber em qual ordem os objetos estarão distribuídos.