Sim, HashSet não tem qualquer garantia de ordem.
O algoritmo que ele usa é, a grosso modo, descrito assim:
Crie um array, de um tamanho qualquer, onde cada índice desse array é uma lista de objetos.
Ao inserir um objeto:
Divida o hashcode desse objeto pelo tamanho do array, e pegue a parte inteira.
Na posição do resultado, adicione esse objeto na lista, se ele já não estiver lá.
Exemplo:
//Criamos um array:
List<Object> array[100] = new List<Object>[100];
//Ao adicionar o elemento de hashcode 2109
int pos = elemento.hashCode() / array.length; //pos = 2109 / 100 = 21;
if (array[pos].contains(elemento))
return; //Não adicionamos nada
array[pos].add(elemento);
Note que, num hashcode bem implementado, haverá poucas colisões de hash, então a lista de cada posição ficará relativamente vazia.
Caso contrário, a lista pode encher e a performance certamente vai cair.
É claro que na prática é um pouco mais complicado que isso, já que a implementação na realidade se baseia na do Map, prevê o crescimento da lista em caso de colisões de hash, etc...
Mas acho que esse pseudo-código já ajuda a entender como seria um possível HashSet e porque é tão rápido.