Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hashing - Coggle Diagram
Hashing
Conjuntos
Um conjunto é uma coleção não-ordenada e possivelmente vazia de itens distintos.
Pode ser implementado de duas formas:
Como subconjunto de U (conjunto universal)
Se U tem n elementos, então qualquer subconjunto de U pode ser representado por uma string de bit de tamanho n, chamada de bit vector. O iº elemento do bit vector é 1 se e somente se esse elemento de U está incluso em S.
Ex: U = {1, 2, 3, 4, 5} e S = {2, 3}. O bit vector será 01100.
Utilizar uma estrutura de lista para indicar os elementos do conjunto.
Abordagem mais utilizada na computação. Entretanto, é necessário prestar atenção em alguns pontos: um conjunto não pode conter elementos idênticos enquanto uma lista pode; mudar a ordem dos elementos não muda o conjunto, mas muda a lista.
Geralmente as operações que precisaremos fazer se baseiam em pesquisar um item, adicionar um novo item e deletar um item a partir da coleção. A ADT que implementa essas três operações se chama dicionário.
Antes de abordar os conceitos de dicionário, é importante discutir a ideia de trocas entre espaço e tempo.
A ideia por trás disso é pré-processar o input do problema (seja ele inteiro ou em partes) e estocar informações adicionais obtidas para acelerar a resolução do problema depois. É uma troca: ceder mais espaço para melhorar o tempo.
Prestructuring: usar o espaço extra para facilitar o acesso mais rápido ou mais flexível para os dados.
Programação dinâmica: técnica de design de algoritmos relacionada à ideia de troca. Registra soluções para subproblemas sobrepostos de um problema dado em uma tabela para qual a solução para o problema em questão é então obtido.
Dicionários
Métodos
public void clear() - esvaziar o dicionário;
public void insert(Key k, E elemento) - inserir um elemento;
public E remove(Key k) - remover um elemento específico;
public E removeAny() - remover um elemento qualquer;
public E find(Key k) - procurar um elemento com chave k;
public int size() - obter o tamanho do dicionário.
Pode ser implementado de várias maneiras. Entre as mais sofisticadas estão as árvores de busca ou hashing.
Geralmente usados para armazenar registros. Ex: estudantes em uma escola, registros de cidadãos, etc.
1 more item...
Hashing
A ideia é distribuir chaves entre um array de 1 dimensão H[0..m-1], chamado de hash table. A distribuição é feita computando para cada chave o valor de alguma função predefinida h, chamada de função hash. A função atribui um inteiro entre 0 e m-1, chamado de hash address, para uma chave.
1 more item...