Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hash Tables - Coggle Diagram
Hash Tables
Hashing
distribuir chaves entre um array unidimensional
Maneira muito eficiente implementar dicionários em termos de eficiência temporal
A distribuição de chave é chamada de
hash function
h : Key → 0..m − 1
A função atribui a um inteiro entre 0 e m - 1,
hash address
, uma chave
Precisa satisfazer alguns requisitos
A distribuição de chaves precisar ser o mais uniforme possível
colisões
quando 2 ou mais chaves são atribuídas na mesma célula da hash tables
1 more item...
Precisa de uma relação adequada entre o tamanho da
hash table
e o numero de chaves
Precisa ser fácil de calcular
O array é chamado de
hash table
H[0..m − 1]
Space and time trade-offs
temos uma eficiência de espaço pior para obtermos uma eficiência de tempo melhor
Conjuntos
coleção de elementos distintos não ordenados, podendo ser vazia
Operações
Essas operações são implementadas a partir de uma estrutura de dados
Dicionário
tipos
inserção
remoção
busca