Como é determinada a velocidade de busca de elementos na implementação do HashSet?

Na implementação do HashSet em Java, a velocidade de busca de elementos é determinada pelo uso interno do HashMap. O HashSet armazena elementos como chaves no HashMap, e os valores são fictícios.

A velocidade de busca depende de:

• A função hash do objeto: ela converte o objeto em um código hash que determina a posição no array de buckets.
• Colisões: se vários elementos têm o mesmo hash, eles caem no mesmo bucket, e a busca torna-se linear em relação ao número de elementos nesse bucket.

Em média, com uma boa função hash e baixo nível de colisões, a busca no HashSet é uma operação O(1) (tempo constante). Se houver muitas colisões, o tempo pode piorar para O(n).

Exemplo:

HashSet<String> set = new HashSet<>();
set.add("apple");
boolean exists = set.contains("apple"); // Busca rápida por hash