De que componentes é composta uma tabela hash?

Uma tabela de dispersão consiste em dois componentes principais:

1. Array (ou lista) de células (baldes): É a estrutura principal de armazenamento. Cada célula pode conter um ou vários elementos de dados (pares chave-valor).

2. Função de dispersão: Algoritmo que transforma a chave de entrada num índice numérico, usado para determinar a célula onde o elemento de dados correspondente deve ser guardado ou encontrado.

Além disso, para resolver colisões (situações em que diferentes chaves são dispersas para o mesmo índice), utilizam-se mecanismos como:

• Método de encadeamento: Cada célula armazena uma lista (por exemplo, uma lista ligada) de elementos dispersos nesse índice.
• Método de endereçamento aberto: Em caso de colisão, o algoritmo procura pela próxima célula livre seguindo uma estratégia definida (sondagem linear, sondagem quadrática, dupla dispersão).

# Exemplo de função de dispersão simples
def simple_hash(chave, tamanho_array):
    # Transformação da chave em número
    if isinstance(chave, str):
        valor_hash = sum(ord(caractere) for caractere in chave)
    elif isinstance(chave, int):
        valor_hash = chave
    else:
        raise TypeError("Tipo de chave não suportado")

    # Retornar o índice dentro do tamanho do array
    return valor_hash % tamanho_array

# Exemplo de componente de array de células para método de encadeamento
class HashTable:
    def __init__(self, tamanho):
        self.tamanho = tamanho
        self.array = [[] for _ in range(self.tamanho)] # Array de listas (encadeamentos)

    def inserir(self, chave, valor):
        indice = simple_hash(chave, self.tamanho)
        self.array[indice].append((chave, valor)) # Adicionar par chave-valor à lista

    def buscar(self, chave):
        indice = simple_hash(chave, self.tamanho)
        for k, v in self.array[indice]:
            if k == chave:
                return v
        return None # Chave não encontrada