• Hashing com Tratamento de Colisão

  • INFO:

  • HUB

  • 1/1

  • Tamanho do Vetor:

  • Tamanho da Área de Overflow:

Informações da Estrutura
Estrutura de Dados

NoHash

{

  info : String;

  proximo : inteiro;

}

EstruturaHash

{

  TabelaHash : vetor de NoHash;

  AreaDeOverflow : vetor de NoHash;

  DISP : inteiro;

}

Constantes

TAMANHO_DA_TABELA : inteiro;

Descrição
A função HASH, ou função de espalhamento, mapeia um conjunto de chaves em uma tabela de tamanho fixo de acordo com um conjunto de valores. Ou seja, dado um valor existe uma chave respectiva e de modo unidirecional. A Área de Overflow é uma forma de tratamento de colisão onde se utiliza uma lista estática para armazenar as colisões. Esta lista pode ser tanto com com ordenação quanto sem ordenação. Caso a Área de Overflow estiver cheia, realiza a substituição do valor na Tabela.

Mais informações
Implementação: Realizada por meio de um vetor de tamanho fixo para armazenar a Tabela Hash e outro vetor de tamanho fixo para a Área de Overflow.

Regras: Cada valor possui uma chave respectiva obtida por uma função.

Aplicação: Utilizada na otimização de algoritmos e armazenamento temporário de dados.

Requisitos para aplicação: Dados podem ser sobrescrevidos.

Vantagem: Pode se armazenar em qualquer ordem e é de fácil implementação.
Desvantagem: A tabela não pode ser muito grande, pois terá grande gasto de memória. A função Hash tem que possuir um perfeito nível de espalhamento para não ocorrer muitas colisões, caso contrário, muitos dados serão perdidos quando a área de overflow ficar cheia.
FUNÇÃO
Insere(INFO)

indice : inteiro;

indice := Hash(INFO);

Se TabelaHash[indice] == nulo então

INICIO

TabelaHash[indice] := alocar();

TabelaHash[indice].info := INFO;

TabelaHash[indice].proximo := -1;

FIM

Senão se DISP != -1 então

INICIO

Se TabelaHash[indice].proximo == -1 então

TabelaHash[indice].prox := DISP;

Senão

INICIO

leitor : inteiro;

leitor := TabelaHash[indice].proximo;

Enquanto AreaDeOverflow[leitor].prox != -1 faça

leitor := AreaDeOverflow[leitor].prox;

AreaDeOverflow[leitor].proximo := DISP;

FIM

 

aux : inteiro;

aux := AreaDeOverflow[DISP].proximo;

AreaDeOverflow[DISP].info := INFO;

AreaDeOverflow[DISP].proximo := -1;

DISP = aux;

FIM

Senão

TabelaHash[indice].info := INFO;

FUNÇÃO
Hash(INFO)
RETORNA
O índice do respectivo valor

soma,total : inteiro;

soma := 0;

total := INFO.comprimento;

 

Para i de 0 até total passo 1 faça

soma := soma + (i+1)*INFO.caracter(i);

soma := soma%TAMANHO_DA_TABELA;

Retornar soma;

FUNÇÃO
Remove(INFO)

ind : inteiro;

ind := Hash(INFO);

Se TabelaHash[ind] != nulo então

INICIO

Se TabelaHash[ind].info == INFO então

INICIO

Se TabelaHash[ind].proximo == -1 então

INICIO

Liberar(TabelaHash[ind]);

TabelaHash[ind] := nulo;

FIM

Senão

INICIO

prox : inteiro;

prox := TabelaHash[ind].prox;

TabelaHash[ind].info := AreaDeOverflow[prox].info;

TabelaHash[ind].proximo := AreaDeOverflow[prox].proximo;

AreaDeOverflow[prox].proximo := DISP;

AreaDeOverflow[prox].info := nulo;

DISP := prox;

FIM

FIM

Senão Se TabelaHash[ind].proximo != -1 então

INICIO

leitor, anterior : inteiro;

anterior := -1;

leitor := TabelaHash[ind].prox;

 

Enquanto leitor != -1 e AreaDeOverflow[leitor].info então

INICIO

anteiror := leitor;

leitor := AreaDeOverflow[leitor].proximo;

FIM

 

Se leitor != -1 então

INICIO

Se anterior != -1 então

AreaDeOverflow[anterior].proximo := TabelaHash[leitor].proximo;

Senão

TabelaHash[ind].proximo := AreaDeOverflow[leitor].proximo;

AreaDeOverflow[leitor].proximo := DISP;

AreaDeOverflow[leitor].info := nulo;

DISP := leitor;

FIM

FIM

FIM

FUNÇÃO
Hash(INFO)
RETORNA
O índice do respectivo valor

soma,total : inteiro;

soma := 0;

total := INFO.comprimento;

 

Para i de 0 até total passo 1 faça

soma := soma + (i+1)*INFO.caracter(i);

soma := soma%TAMANHO_DA_TABELA;

Retornar soma;

FUNÇÃO
Busca(INFO)
RETORNA
Se o valor está na Tabela

indice : inteiro;

leitor : EstruturaLista;

indice := Hash(INFO);

 

Se TabelaHash[indice] != nulo então

INICIO

Se TabelaHash[indice].info == INFO então

Retornar Verdadeiro;

Senão

INICIO

leitor : inteiro;

leitor := TabelaHash[indice].proximo;

Enquanto leitor != -1 faça

INICIO

Se AreaDeOverflow[leitor].info == INFO então

Retornar Verdadeiro;

leitor := AreaDeOverflow[leitor].proximo;

FIM

FIM

FIM

Retornar Falso;

FUNÇÃO
Hash(INFO)
RETORNA
O índice do respectivo valor

soma,total : inteiro;

soma := 0;

total := INFO.comprimento;

 

Para i de 0 até total passo 1 faça

soma := soma + (i+1)*INFO.caracter(i);

soma := soma%TAMANHO_DA_TABELA;

Retornar soma;

Última animação

Nenhuma animação disponível para revisar!

Executando animação ...

Aguarde encerrar !

Última animação que foi executada:

# Descrição
Entradas Programadas

Configurações

Entradas

Limpar entrada ao final da animação

Chance de gerar número negativo na entrada aleatória:

50%

Estrutura

Ocultar Ponteiros Nulos

Impedir inserção de valores repetidos

Mostrar Descritores

Cor do componente primário

Cor do componente secundário

Código

Usar delimitador em chaves

Contar linhas brancas

Configurações serão salvas para este navegador
Histórico
    • #
    • INFO
    • Vazio
Principal
Menu das Estruturas

  • Pseudo-código

  • Informações da Estrutura

  • Entradas Programadas

  • Rever Passos

  • Histórico

Hashing com Tratamento de Colisão

  • Vazio
Logo

Estruturas

Listas

Sem ordenação

Simples

Dupla

Com ordenação

Simples

Dupla

Estática

Cruzada

Filas

Estáticas

Simples

Circular

Dinâmicas

Normal

Com Prioridade

Circular

Pilhas

Estáticas

Simples

Múltipla

Dinâmicas

Simples

Hashing

Sem Tratamento

Simples

Com Tratamento

Listas Encadeadas

Área de Overflow

Árvores

Balanceadas

AVL

Rubro-Negra

B

Não Balanceadas

Binária

Trie

Patricia
Histórico

Lista Ordenada Simples

Lista Ordenada Estática

Lista Ordenada Dupla

Lista Sem Ordenação Simples

Lista Sem Ordeneção Dupla

Lista Cruzada

Fila Estática

Fila Estática Circular

Fila com Prioridade

Fila Dinâmica

Fila Circular

Pilha Estática

Pilha Múltipla

Pilha Dinâmica

Hash sem Tratamento

Hash com Tratamento

Hash com Overflow

Árvore AVL

Árvore B

Árvore RubroNegra

Árvore Binária

Árvore Trie

Árvore Patricia

Estrutura não encontrada