Dos JavaDocs deHashSet:

Esta classe oferece desempenho de tempo constante para as operações básicas (adicionar, remover, contém e tamanho), assumindo que a função hash dispersa os elementos corretamente entre os buckets. Iterar sobre esse conjunto requer tempo proporcional à soma do tamanho da instância do HashSet (o número de elementos) mais a "capacidade" da instância de HashMap de suporte (o número de depósitos). Portanto, é muito importante não definir a capacidade inicial muito alta (ou o fator de carga muito baixo) se o desempenho da iteração for importante

Por que a iteração leva tempo proporcional à soma (número de elementos no conjunto + capacidade do mapa de apoio) e não apenas ao número de elementos no próprio conjunto?

.