Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sets and Dictionaries, Space and Time Trade-Offs - Coggle Diagram

- - - - Cada lista contém chaves mapeadas para sua célula correspondente. Utiliza-se uma função de hash simples para strings, adicionando as posições das letras no alfabeto e computando o resto da divisão por 13.
      - Ao buscar uma chave na tabela, aplica-se o mesmo procedimento usado para criar a tabela. A eficiência da busca depende do tamanho das listas encadeadas, que por sua vez dependem do tamanho do dicionário, da tabela e da qualidade da função de hash.
      - O fator de carga da tabela de hash, representado por α = n/m (onde n é o número de chaves e m é o tamanho da tabela), desempenha um papel crucial na eficiência do hashing. Quando esse fator está próximo de 1, o esquema se torna surpreendentemente eficiente, permitindo buscar uma chave com uma média de uma ou duas comparações.
      - As operações de inserção e exclusão no dicionário são semelhantes à busca, com uma complexidade média de O(1) quando o número de chaves é aproximadamente igual ao tamanho da tabela de hash. Estas operações são realizadas adicionando ao final da lista (para inserção) ou localizando e removendo a chave correspondente (para exclusão).
    - - Em uma estratégia chamada linear probing, após uma colisão, a tabela é percorrida sequencialmente até encontrar uma célula vazia para inserir a nova chave ou até alcançar o final da tabela, quando a busca continua do início, tratando a tabela como um array circular. Na busca por uma chave, calcula-se sua posição na tabela pela função de hash e verifica-se se está ocupada. Se estiver, verifica-se se é a chave correta; caso contrário, continua-se a busca nas células subsequentes até encontrar a chave ou uma célula vazia.
      - Embora a busca e a inserção sejam operações simples, a exclusão de elementos pode ser mais complexa. Uma solução comum é a "deleção preguiçosa", onde locais previamente ocupados são marcados para diferenciação.
      - O desempenho do linear probing é impactado pela "agrupamento" (clustering) quando a tabela está quase cheia, tornando as operações menos eficientes. Outras estratégias, como o double hashing, são usadas para resolver esse problema.
      - Comparado às árvores de busca balanceadas, o hashing oferece eficiência de tempo média de O(1), mas pode chegar a O(n) no pior caso, enquanto as árvores de busca balanceadas têm eficiência média de O(log n) em ambos os casos. O hashing tem aplicações em armazenamento de tabelas de símbolos em programas de computador, em inteligência artificial e em técnicas como o extendible hashing para armazenamento eficiente de grandes dicionários em discos.