Please enable JavaScript.

Coggle requires JavaScript to display documents.

Conjuntos e Dicionários, Trade-Offs de espaço e tempo - Coggle Diagram

- - - - Hashing
        
        Os elementos dese conjunto podem ser de natureza arbitrária.
        
        Hashing é baseado na ideia de distribuir chaves entre um unidimensionalmatriz H[0..m − 1] chamada de tabela de hash. A distribuição é feita por computação, pois
        cada uma das chaves, o valor de alguma função predefinida h chamada função hash.
        
        Em geral, uma função hash precisa satisfazer requisitos um pouco conflitantes:
        
        O tamanho de uma tabela de hash não deve ser excessivamente grande em comparação com o número de chaves, mas deve ser suficiente para não comprometer o tempo de implementação
        
        Uma função hash precisa distribuir chaves entre as células da tabela de hash como
        uniformemente possível.
        
        Existem duas principais versões de Hashing
        
        Open Hashing
        
        No hash aberto, as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela de hash.Cada lista contém todas as chaves com hash para sua célula
        
        Closed Hashing
        
        No hash fechado, todas as chaves são armazenadas na própria tabela de hash sem o usode listas vinculadas. (Claro, isso implica que o tamanho da tabela m deve ser pelo menos como
        grande como o número de chaves n.)
      - indexação com árvore B