Quais são as formas de resolver colisões de hash…

Método de encadeamento (Separate Chaining):
- Cada elemento do array da tabela hash (bucket) é um ponteiro para uma lista ligada (ou outra estrutura de dados, como uma árvore).
- Todos os elementos hashados num mesmo bucket são adicionados a essa lista.
```
// Exemplo: nó de uma lista ligada para encadeamentos
struct Node {
    int key;
    int value;
    Node* next;
};

// No bucket armazena-se um ponteiro para o cabeçalho da lista
Node* buckets[TABLE_SIZE];
```

Métodos de endereçamento aberto (Open Addressing):

Todos os elementos são armazenados diretamente no array da tabela hash.
Em caso de colisão, procura-se a próxima posição livre no array.

Diferenciam-se pelo modo de determinar a próxima posição:

Probing linear (Linear Probing): Verificam-se as células em ordem com um passo fixo i, i+1, i+2, ... mod TABLE_SIZE.

// Exemplo de probing linear
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + 1) % TABLE_SIZE;
}
// Agora table[i] está vazio ou contém o elemento procurado

Probing quadrático (Quadratic Probing): Verificam-se as células com um passo que depende do quadrado da tentativa i, i+1², i+2², ... mod TABLE_SIZE.

// Exemplo de probing quadrático
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
int attempt = 0;
while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
    attempt++;
    i = (hash(key) + attempt * attempt) % TABLE_SIZE;
}
// Agora table[i] está vazio ou contém o elemento procurado (ou a tabela está cheia)

Double hashing (Double Hashing): Usa uma segunda função hash para determinar o passo de sondagem i, i + step, i + 2*step, ... mod TABLE_SIZE, onde step é calculado com a segunda função hash do key.

// Exemplo de double hashing
int hash1(int key) { return key % TABLE_SIZE; }
int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // Segunda função hash

int i = hash1(key);
int step = hash2(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + step) % TABLE_SIZE;
}
// Agora table[i] está vazio ou contém o elemento procurado

Redimensionamento dinâmico (Resizing):

Quando se atinge um determinado fator de carga, cria-se uma nova tabela hash de maior tamanho.
Todos os elementos da tabela antiga são re-hashados e inseridos na nova.

// Exemplo de lógica para redimensionar
if (current_size / (double)table_size > max_load_factor) {
    // Criar uma nova tabela de tamanho dobrado
    // Re-hash e inserir todos os elementos da antiga tabela
    // Eliminar a tabela antiga
}

A escolha do método depende dos requisitos de desempenho, memória, complexidade de implementação e do fator de carga esperado. O método de encadeamento é geralmente mais simples de implementar e funciona bem com fatores de carga elevados, mas requer memória adicional para os ponteiros. Os métodos de endereçamento aberto podem usar a memória de forma mais compacta, mas são mais sensíveis à função de hash e a problemas de "clustering". O redimensionamento é necessário para manter a eficiência à medida que o número de elementos cresce.

Quais são as formas de resolver colisões de hash?