Please enable JavaScript.

Coggle requires JavaScript to display documents.

Conjuntos e dicionários, Hashing, Hash tables - Coggle Diagram

- - - - Um dicionário é definido por suas operações de procurar por um item dentro dele, adicionar um novo item e deletar um item existente
- - - - Esse numero gerado representa o dado, e pode ser utilizado para identificar a posição de onde ele será armazenado em um array
        
        Existem diferentes algoritmos de hashing, cada um com sua peculiaridade
        
        Alguns requisitos para uma boa função de hashing
        
        O tamanho de uma hash table não deve ser muito grande quando comparada com seu número de entradas (keys)
        
        Uma hash function deve distribuir as keys ao longo da hash table o mais homogeneamente possível
        
        Uma hash function deve ser fácil de computar
        
        Para ter um baixo running time
- - - - Isso pode ser ruim e é chamado de "conflito"
        
        A forma como uma hash table lida com o conflito caracteriza os dois tipos principais de hash tables
        
        Open hashing
        
        Coloca elementos que pertencem a uma mesma posição do array em um subgrupo
        
        Esse subgrupo tipicamente é uma linked list
        
        Sendo assim, uma hash table com open hashing é um array de linked lists
        
        1 more item...
        
        Closed hashing
        
        Ao ocorrer uma colisão, busca a primeira posição disponível após aquela que foi obtida pela hash function
        
        Não há a utilização de linked lists, apenas o próprio arrays
        
        Implicação = O tamanho da hash table deve ser pelo menos igual ao tamanho da quantidade de keys
        
        1 more item...