Aprender algoritmos

Capítulo 3. Viver melhor através de um melhor hashing

Este trabalho foi traduzido com recurso a IA. Agradecemos o teu feedback e comentários: [e-mail]

Neste capítulo, aprenderás:

• Como armazenar pares (chave, valor) numa tabela de símbolos e recuperar valores associados a uma chave.¹

• Como utilizar uma matriz para armazenar pares (chave, valor) para uma pesquisa eficiente, se o tamanho da matriz for suficientemente grande, em comparação com o número de pares armazenados.

• Como utilizar uma matriz de listas ligadas para armazenar pares (chave, valor) para suportar a capacidade extra de remover uma chave.

• Como redimensionar uma tabela de símbolos para manter a eficiência.

• Análise amortizada para determinar o desempenho médio do tempo de execução quando o comportamento de uma operação pode mudar com invocações sucessivas.

• Como o redimensionamento geométrico reduz a frequência da dispendiosa operação de redimensionamento, o que significa que put() tem um desempenho O(1) amortizado em média.

• Como uma função hash computacional pode distribuir uniformemente os valores-chave, o que garante a eficiência da implementação da tabela de símbolos.

Como associar valores a chaves

Em vez de armazenar apenas valores, podes precisar de armazenar uma coleção de pares (chave, valor) para associar valores a chaves específicas. Isto é conhecido como um tipo de dados de tabela de símbolos, que te permite encontrar o valor associado dado apenas a sua chave. O hashing ...