• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

benkas

Função de Hash

6 mensagens neste tópico

Boas

Alguem me poderia ajudar a encontrar um boa função de hash para uma HashTable com cerca de 1.000.000 de entradas, que é para intrudizir cerca de 500.000 palavras. Esta é a minha função de hash e está muito lento a introduzir, ja tive cerca de 40minutos e não chegou a introduzir os dados todos.

public static int hash(String chave, int tamTabela){

    int valorHash = 0;

   

    for(int i=0;i<chave.length();i++)

      valorHash = 37*valorHash + chave.charAt(i);

   

    valorHash %= tamTabela;

    if(valorHash<0) valorHash += tamTabela;

    return valorHash;

  }

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não sei se para tantos registos não de algo bastante mais flexível do que um hash "caseiro" mas tenta lá com este.

Já agora a tua hashtable é aberta ou fechada? É que não percebo porque não consegues meter todos os registos!

public class Hash{
        public static void main(String args []){
                String pv = args[0];
                int hash = 0;
                int tamanho =  1000000;

                for( char c : pv.toCharArray() ){
                        hash += 37*hash + ((int)c);
                }
                hash *= pv.length();
                hash %= tamanho;

                if(hash < 0){
                        hash +=tamanho;
                }
                System.out.println(hash);
        }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É uma hash aberta com resolução de colisões quadraticas. Essa que me indicaste não resolve o problema...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque não fazes colisões lineares ? Assim em de certeza que insere tudo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas,

Eu já tive um problema semelhante, tive de implementar um dicionário com cerca de 900.000 entradas (palavras).  :eek:

Tambem tentei usar HashTables mas depressa desisti dessa ideia e usei o Lucene http://lucene.apache.org/. Com o lucene podes indexar todas as entradas (cria uns ficheiros em disco) e depois podes pesquisar nesse index, ou seja, apenas tens de indexar uma vez.

Com esta solução fiquei com um tempo de cerca de 45 minutos para indexar e as pesquisas com com tempos abaixo dos 20ms.  :)

Na enventualidade de precisares de adicionar mais entradas ao index é bastante simples e como não precisas de re-indexar tudo é bastante rápido.  :)

Espero ter ajudado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora