Please enable JavaScript.

Coggle requires JavaScript to display documents.

Conjuntos e Dicionários - Coggle Diagram

- - - - A implementação ideal de um dicionário deve ser um meio-termo entre a eficiência de pesquisa e adição e remoção.
- - - - Por fim, temos a programação dinâmica, que se constitui de uma estratégia baseada no registro de soluções para subproblemas de um determinado problema em uma tabela a partir da qual uma solução para o problema em questão é obtido.
  - - - Hashing é baseado na ideia de distribuir chaves entre um array unidimensional chamado de tabela de hash. A distribuição é feita pelo computador, para cada uma das chaves, o valor de alguma função h pré-definida, atribui um inteiro entre 0 e m-1, chamado de endereço de hash, para a chave.
    - - O tamanho da tabela de hash não pode ser excessivamente grande quando comparada com o número de chaves, mas deve ser suficiente para não comprometer a implementação eficiente do tempo.
      - Uma função hash precisa atribuir as chaves entre as células de maneira mais uniforme possível.
      - Uma função hash precisa ser fácil de computar.
    - - Open Hashing
        
        Nelas, as chaves são armazenadas em listas ligadas atribuídas para as células da tabela de hash. Cada lista contém todas as chaves ligadas àquela célula.
        
        Quando há colisões, se faz um teste individual dos itens da chave para ver qual é o desejado.
      - Close Hashing
        
        Nesse modelo, todas as chaves são armazenadas diretamente na tabela de hashing. Diferentes estratégias podem ser usadas para solucionar colisões. A mais simples, chamada de sondagem linear, checa célula a célula se colisões ocorrem. Se a célula está vazia, uma nova chave é inserida lá, a próxima é inserida no próximo espaço livre e assim vai.
        
        A inserção e a busca são simples, entretanto, quando feito a remoção, pode ocorrer de ele interferir na procura de chaves posteriores a ela. Para solucionar isso, uma estratégia é marcar posições que já foram utilizadas previamente com um identificador especial.