Conforme o Paulo comentou, o HashSet utiliza uma tabela de espalhamento para funcionar. Para quem tiver mais curiosidade, perguntei à IA mais sobre essa estrutura de dados. Eis a resposta:
"O Set no Java é uma interface que define um conjunto de elementos únicos, ou seja, não pode conter elementos duplicados. A implementação mais comum do Set é o HashSet, que é baseado em uma tabela de dispersão (hash table) para armazenar os elementos.
Ao adicionar um elemento ao HashSet, o Java calcula um código hash para o elemento usando o método hashCode() do objeto. Esse código hash é usado para determinar em qual "bucket" (compartimento) o elemento deve ser armazenado na tabela de dispersão. Se houver outro elemento no mesmo bucket, o Java verifica se os dois elementos são iguais usando o método equals() do objeto.
O processo de espalhamento (hashing) usado pelo HashSet é projetado para minimizar colisões, ou seja, situações em que dois elementos diferentes têm o mesmo código hash e são armazenados no mesmo bucket. Isso pode ser feito usando um bom algoritmo de hash e um tamanho apropriado da tabela de dispersão.
Quando você deseja recuperar um elemento de um HashSet, o Java calcula o código hash do elemento e usa-o para procurar o bucket correto. Se houver mais de um elemento no mesmo bucket, o Java usa o método equals() para encontrar o elemento correto.
O espalhamento (hashing) usado pelo HashSet é uma maneira eficiente de armazenar e recuperar elementos únicos. No entanto, se os objetos armazenados no HashSet não tiverem uma boa implementação do método hashCode() ou equals(), pode ocorrer um grande número de colisões, o que pode prejudicar o desempenho da estrutura de dados. Portanto, é importante garantir que os objetos armazenados no HashSet implementem corretamente esses métodos."