HashSet pra quem sabe o que é uma List no C#
Tags: beginners, programming, braziliandevs, csharp
Published: 2023-08-03 22:07:57

Tanto o **`HashSet`** quanto o **`List`** são estruturas de dados em C# que permitem armazenar uma coleção de elementos. No entanto, há diferenças importantes entre eles.

O **`List`** é uma lista ordenada de elementos, onde cada elemento é acessado por um índice numérico. O **`List`** permite elementos duplicados e mantém a ordem dos elementos adicionados.

Por outro lado, o **`HashSet`** é uma coleção de elementos não ordenados e não permite elementos duplicados. O **`HashSet`** usa um algoritmo de hashing para armazenar e recuperar elementos, o que torna a verificação da presença de um elemento muito rápida em comparação com o **`List`**.

Pense na situação em que você precisa encontrar o primeiro número duplicado em um array, onde o índice da segunda ocorrência desse número seja o menor possível. Nesse caso, o uso do **`HashSet`** pode ser especialmente útil.

Considere o seguinte exercício: dado um array **`a`** que contém apenas números no intervalo de 1 a **`a.length`**, devemos encontrar o primeiro número duplicado para o qual a segunda ocorrência tem o índice mínimo. Em outras palavras, se houver mais de um número duplicado, devemos retornar o número cuja segunda ocorrência tem um índice menor do que a segunda ocorrência dos outros números duplicados. Caso não haja elementos que satisfaçam essa condição, o valor retornado será -1.

Imagine que temos o seguinte array:

```csharp
int[] a = {2, 3, 1, 5, 2, 4, 3};
```

Nesse caso, o número 2 é o primeiro número duplicado, pois aparece nas posições 0 e 4 do array. A segunda ocorrência do número 2 ocorre na posição 4, que é menor do que a segunda ocorrência dos outros números duplicados (o número 3 aparece nas posições 1 e 6, e o número 5 aparece apenas na posição 3).

Para resolver esse problema, podemos utilizar um **`HashSet`** para armazenar os números que encontramos durante a iteração pelo array. Ao percorrer o array, podemos verificar se cada número já existe no **`HashSet`**. Se já existir, encontramos o primeiro número duplicado e podemos retorná-lo. Caso contrário, adicionamos o número ao **`HashSet`** e continuamos a iteração.

Por isso, no exemplo apresentado, usamos um **`HashSet`** para implementar a solução.

```csharp
int FindFirstDuplicate(int[] array)
{
    HashSet<int> numbers = new HashSet<int>();

    foreach (int num in array)
    {
        if (numbers.Contains(num))
        {
            return num;
        }

        numbers.Add(num);
    }

    return -1;
}
```

Nesse exemplo, criamos um **`HashSet`** chamado **`numbers`** para armazenar os números encontrados. Em seguida, percorremos o array utilizando um loop **`foreach`** e verificamos se cada número já existe no **`HashSet`**. Se já existir, retornamos o número duplicado. Caso contrário, adicionamos o número ao **`HashSet`** e continuamos a iteração.

Usar um **`List`** exigiria percorrer todo o **`List`** para verificar se cada elemento já foi adicionado anteriormente, o que levaria O(n²) tempo no pior caso.

Por outro lado, usar um **`HashSet`** permite verificar rapidamente se um elemento já foi adicionado anteriormente, em O(1) tempo no melhor caso. Como o **`HashSet`** não permite elementos duplicados, o primeiro elemento duplicado que encontrarmos será a duplicata que procuramos.