Um hashset é como um livro, no qual as chaves são o sumário e os valores são os capítulos.
Em outras palavras... Quando você insere um elemento em um hashset, é gerado um hash do objeto. Daí você tem uma estrutura que guarda informações em pares. Cada par tem de um lado o hash do objeto e do outro uma referência pro objeto.
Acontece que hashes são geralmente strings bem... aleatórias. Por exemplo, supondo que o algoritmo de hash seja o MD5:
- o hash da string
foo
é acbd18db4cc2f85cedef654fccc4a4d8
;
- Já o hash de
bar
é 37b51d194a7513e45b56f6524f2d51f2
;
- E de
baz
é 73feffa4b7f6bb68e44cf984c85f6e88
.
Se você fosse ordenar os hashes por ordem alfabética ou hexadecimal, teria que reindexar o conjunto a cada elemento adicionado. Isso deixaria as inserções lentas, e um dos objetivos do hashset é ser rápido.
Pra complicar, é possível haver colisão de hashes. Isso ocorre quando dois objetos tem o mesmo hash. Nesse caso, é comum que um hashset adicione um pouco de sal (isso é um termo técnico!) a um dos objetos e gere um novo hash diferente pra ele. Assim a bagunça nos índices fica maior ainda.
Talvez você queira usar um mapa de hashes encadeados. Essa estrutura garante a ordem de inserção e existe uma classe em Java para isso: http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html
for ( Contato contato : contatos ) { ... }
(foreach). Lembrando sempre que a posição retornada pode mudar no decorrer do programa, é claro.