Jump to content
Manhoso

[Dúvida] - String hashing

Recommended Posts

Manhoso

Boas.

Estou a tentar construir um dicionário, coisa que já fiz nas aulas, mas em java. 

O que me faltou na altura foi mesmo a implementação de hash para reduzir nos tempos de execução. Como não percebi a matéria das hashes muito bem, pedia que alguém me esclarecesse em como posso fazer a pesquisa num vector com muitos (10K+) elementos. Estes elementos estão ordenados e é tudo texto.

Lá está; sei que com hashes o prog porta-se muito bem, mas não estou a ver como fazer.

Desde já obrigado.

Share this post


Link to post
Share on other sites
vitortomaz

não usando hash podes usar pesquisa dicotómica acho eu que se chama assim

comparas a chave com o elemento do meio, se for maior usas a segunda metade, senão usas a primeira metada...

voltas a comparar mas agora com o elemento do meio da meta escolhida....assim sucessivamente...

não sei se me fiz entender?

Share this post


Link to post
Share on other sites
Warrior

Se já tens o dicionário ordenado, uma pesquisa binária é a solução mais fácil.

Para implementar uma hash table, qualquer função que te disperse bem as palavras pode ser usada. Normalmente recomenda-se que uma hash table tenha pelo menos 30% mais posições do que o número máximo de palavras, e que esse número seja primo.

Depois arranjas uma função, que dada uma palavra, te retorna uma posição no vector. (usa aritmética modular).

De seguida, é só inserires as strings todas na hash table, e sempre que quiseres pesquisar, fazes o processo inverso.

O modo como lidas com colisões (duas palavras diferentes que mapeiam para a mesma posição de memória) pode variar: ou cada posição representa uma lista das palavras com essa hash, ou passas para a posição seguinte. E neste caso tens que ter cuidado ao inserir/verificar, e fica muito complicado remover.

Isto assim um resumo de hash tables, o resto deves poder resolver por ti.

No entanto, a maioria dos dicionários é feita com Tries por ser mais eficiente. Mas vais ter mais trabalho a implementar:

http://en.wikipedia.org/wiki/Trie

Share this post


Link to post
Share on other sites
Manhoso

Obrigado a todos.

Amanhã vou ter exame, mas se tiver tempo hj ainda tento fazer alguma coisa.

Também pensei em pesquisa binária, que foi o que utilizei no trabalho que falei (o tal em Java). Depois lembrei-me que o que era lento era a carregar as palavras de um ficheiro (lusiadas). 😳

Mais uma vez obrigado, quando tiver alguma coisa de concreto posto o resultado no Armazém de Código da linguagem.

Hasta

P.S.: Podem fechar este tópico.

Share this post


Link to post
Share on other sites
Warrior

Não há qualquer necessidade de fechar o tópico, fica aberto em caso de necessidade.

Share this post


Link to post
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

×
×
  • 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.