Jump to content

Função de Hash


benkas
 Share

Recommended Posts

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;

  }

Link to comment
Share on other 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);
        }
}

I haven’t lost my mind; it’s backed up on DVD somewhere!

Link to comment
Share on other sites

Boas,

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

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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.