Tabela Hash Flashcards
(9 cards)
O que é uma Tabela Hash (Hash Table) em Estruturas de Dados?
Uma Tabela Hash é uma estrutura de dados que associa chaves a valores, usando uma função hash para determinar a posição no array onde o valor será armazenado.
O que é uma Função Hash?
Uma Função Hash é uma função que recebe uma chave e retorna um número inteiro (hash) usado como índice para armazenar o valor na tabela.
O que é uma Colisão em uma Tabela Hash?
Uma Colisão ocorre quando duas ou mais chaves geram o mesmo valor de hash e, portanto, mapeiam para a mesma posição na tabela.
Quais são os métodos de resolução de colisões em uma Tabela Hash?
Métodos de resolução: Encadeamento (listas de elementos na mesma posição) e Endereçamento Aberto (busca por posição vazia dentro da própria tabela).
O que é o load factor em uma Tabela Hash?
O load factor é a razão entre o número de elementos e o número de posições disponíveis na tabela. Um valor muito alto pode indicar muitas colisões.
Qual a complexidade das operações em uma Tabela Hash?
Busca: O(1) no melhor caso, O(n) no pior caso. Inserção: O(1) no melhor caso, O(n) no pior caso. Remoção: O(1) no melhor caso, O(n) no pior caso.
Como é a implementação de uma Tabela Hash em C?
```c
#define SIZE 10
struct Node {
int key;
int value;
struct Node* next;
};
struct Node* hashTable[SIZE];
int hashFunction(int key) {
return key % SIZE;
}
void insert(int key, int value) {
int index = hashFunction(key);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->value = value;
newNode->next = hashTable[index];
hashTable[index] = newNode;
}```
O que é a Tabela Hash Dinâmica?
Uma Tabela Hash Dinâmica ajusta seu tamanho automaticamente, geralmente dobrando-o quando o número de elementos atinge um limite. Isso ajuda a manter a eficiência.
Quais são as vantagens de uma Tabela Hash?
Vantagens: Busca rápida (O(1) no melhor caso), eficiência nas operações, flexibilidade para mapear chaves para valores de diferentes tipos.
