Please enable JavaScript.
Coggle requires JavaScript to display documents.
SETS AND DICTIONARIES, HASINHG, SPACE AND TIME TRADE-OFFS - Coggle Diagram
SETS AND DICTIONARIES
SET
-
as operações mais importantes são: checar se um item qualquer se encaixa em tal set, achar a união de dois sets e também suas interseções .
duas formas de implementar:
a primeira considera apenas sets limitados que fazem já fazem parte de um set universal, e a segunda é utilizando uma estrutura de lista para indicar os elementos.
DICTIONARY
implementa operações importantes como: procurar por um certo item, adicionar um novo item e deletar um elemento da coleção.
HASINHG
OPEN HASHING
-
a eficiencia da busca depende do tamanho da linked list, que depende do dicionario
e do tamanho das tabelas, assim como da qualidade da funcao hash
-
CLOSED HASHING
Todas as chaves são armazenadas na hash table propriamente dita, sem o uso de linked lists
diferentes estratégias podem ser aplicadas, como linear probing (checa a célula seguinte depois da colisão).
-
a chave do dicionário é o que identifica cada elemento adicionado, hashing é baseado em distribuir essas chaves por arrays de uma
dimensão, chamados de hash table
se escolhermos um tamanho para a tabela hash menor que o numero de
chaves, vão ocorrer colisões, por isso o sistema de hash precisa ter mecanismos que resolvam essas colisões.
-