Como é que a busca de um elemento dentro de uma estrutura HashSet ocorre e qual é a sua complexidade temporal?

HashSet é baseado numa tabela de hash. Ao procurar um elemento, primeiro calcula-se o seu código de hash, depois determina-se o índice do balde (bucket) no array. A seguir, procura-se o elemento dentro desse balde, geralmente através de comparação com equals. A complexidade temporal da procura no HashSet, em média, é O(1), ou seja, tempo constante, assumindo uma distribuição uniforme dos hashes e poucas colisões.