1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Tabelas de Dispersão em Java

Discussão em 'Programação' iniciada por guilherme, 10 de Novembro de 2005. (Respostas: 7; Visualizações: 1816)

  1. guilherme

    guilherme Power Member

    Boas!
    Estou a fazer um trabalho em java em que tenho q utilizar tabelas de dispersão, mas como nao entendi bem as aulas em que isso foi dado, se alguem puder disponibilizar alguns exemplos ficava muito agradecido.
     
    Última edição pelo moderador: 10 de Novembro de 2005
  2. TuxBoss

    TuxBoss Power Member

  3. turbulence

    turbulence Power Member

  4. HecKel

    HecKel The WORM

    Boas, acho que convem saberes uma série de noções sobre isso..., não sei bem a que "ponto" estás, mas vou tentar fazer uma explicaçãozita "à minha maneira" :P

    Tabelas de Dispersão (HashTables) são uma estrutura de dados cuja principal característica é a complexidade temporal constante, tanto na insersão, remoção como pesquisa, isto é, quando tens um simples vector e queres inserir "algo" lá dentro, por norma terias de "procurar" onde existe um lugar vago e só depois inserir, só por esta pesquisa tens um certo "gasto", com as hashtables isto não acontece..., devia uma uma função hash é possivel saber exactamente onde inserir esse objecto consoante a sua "chave" de entrada, logo é fácil de deduzir que com esta mesma função, dando a "chave de entrada", a localização de um objecto também é constante (tal como a remoção)

    Existem hashtables fechadas e hashtables abertas, as hashtables fechadas são "simples vectores" com a função de dispersão (hash), no entanto aqui corremos risco de "colisão".

    As colisões é a designação que se dá a 2, ou mais, objectos com a mesma hashkey, quando isto acontece a hashtable "tenta" colocar estes objectos na mesma posição, dependendo do algoritmo escolhido nas hashtables fechadas, isto pode dar problemas (ou não :P).

    Para resolver este problema das colisões, existem as hashtables abertas, que na prática é um vector de listas, quando se dá uma colisão, este objecto é inserido na lista dessa posição do vector, logo não há o risco de perda de dados, ou dados a irem parar a outros "locais" da hashtable :P

    Acho que isto tá minimamente bem explicado..., mas isto são apenas palavras minhas..., não significa que estejam correctas...

    abraços, HecKel
     
  5. turbulence

    turbulence Power Member

    tens ido às teoricas :D tá bem explicado sem dúvida!
     
  6. guilherme

    guilherme Power Member

    Obrigado pelas respostas, eu tenho essas noçoes todas tava mesmo so com dificuldade na implementação, vou dar uma olhadela,
    1 abraço.
     
  7. TuxBoss

    TuxBoss Power Member

    Esta afirmação só está correcta no caso de ser considerada uma hashtable fechada e com função de hash "perfeita", ou seja que é sempre conseguido calcular um hash (seja utilizando a função de hash primária ou outras) que permita colocar o objecto pretendido numa posição vazia e calculavel por funções de hash sem recurso a outro tipo de algoritmos. No caso de hashtables abertas todas as operações terão complexidades temporais semelhantes ás das listas, ou seja lineares e não constantes (salvo operações unicamente sobre cabeça e cauda).

    O problema que se coloca nas hashtables fechadas em que não é possivel á partida saber o valor de hash de todos os elementos que nela vao ser inseridos (e com isso construir uma função de hash perfeita) é o do surgimento de fragmentação, ou seja o recurso que se utiliza normalmente para tratar colisões em hashtables fechadas é o de utilizar uma 2ª função de hash para calcular um novo hash para o objecto e, caso haja nova colisão, é utilizado um algortimo de inserção linear (tenta-se colocar o objecto na primeira posição livre a contar da do novo valor de hash), o problema que se pode levantar com este método é o de que caso hajam muitos objectos com hash's proximos uns dos outros as inserções começam a ter uma complexidade mt grande pois é necessário percorrer grande parte do vector até encontrar uma posição livre.

    Excluindo este reparo e esta adenda que considero uteis tá uma boa explicação.
     

Partilhar esta Página