Qual é a complexidade de verificar a presença de um elemento em um set no pior caso, quando todos os elementos têm o mesmo hash?

No pior cenário, quando todos os elementos em um conjunto têm um hash idêntico, a estrutura de dados, geralmente implementada como uma tabela de dispersão, degrada para uma lista ligada. Isso acontece porque todos os elementos caem na mesma caixa (bucket).

Nesse caso, verificar a presença de um elemento requer percorrer todos os elementos nessa caixa, o que dá uma complexidade de O(n), onde n é o número de elementos no conjunto.

Assim, no pior caso, procurar um elemento no conjunto é uma busca linear na lista, e não um tempo constante como na média.