What is a Hash Table?
Lição 2 de 14 do curso Tabelas Hash - Série de Estruturas de Dados #4 da Coddy.
Uma tabela hash é uma estrutura de dados que armazena pares chave-valor, como um dicionário que busca entradas por sua chave. A mágica é a velocidade: uma tabela hash bem construída encontra, insere ou remove uma entrada em tempo médio O(1), não importa quantas entradas ela contenha.
O truque é a função hash. Cada chave é convertida em um índice de bucket, para que saibamos exatamente onde procurar sem varrer a tabela inteira. Quando duas chaves diferentes caem no mesmo bucket (uma colisão), nós as mantemos juntas em uma lista naquele bucket. Essa estratégia é chamada de encadeamento.
As cinco principais operações em uma tabela hash são:
- Put: Armazena um par chave-valor, ou atualiza o valor se a chave já existir.
- Get: Busca o valor para uma determinada chave.
- ContainsKey: Verifica se uma chave está armazenada na tabela.
- Remove: Exclui um par chave-valor.
- Size: Retorna o número de pares armazenados atualmente.
Vamos criar uma classe HashMap!
Experimente você mesmo
Esta lição não inclui um desafio de código.