Jump to content
Sign in to follow this  
Cr4zYPT

Função Hash

Recommended Posts

Cr4zYPT

Boas Tardes,

Eu estive cá a ver umas funções hash e agora gostava de as implementar em C, claro.

So que nem sei por onde pegar.

Queria se alguem ajudasse o codigo para calcular a hash baseada nesta função.

 hash(i)=hash(i­‐1)+valor[i]

com tamanho=tamanho da tabela hash

str = string

e valor(i) = caracter na posiçao i da string

Agradecia ajuda

Share this post


Link to post
Share on other sites
Baderous

Não percebi o que queres. Isso é uma parte do código da função de hash que tens de definir? Ou é alguma espécie de pseudo-código?

Share this post


Link to post
Share on other sites
Cr4zYPT

Tipo numa função hash passas uma string e o tamanho da tabela e ela retorna o indice onde colocar a string.

Eu queria era essa função baseada naquela formula.

Share this post


Link to post
Share on other sites
Baderous

Essa fórmula é recursiva, isso não tem um caso de paragem (talvez para i=0 ou i=1)?

Share this post


Link to post
Share on other sites
Baderous

Essa fórmula é facilmente traduzível num ciclo for onde se somam os valores das letras da string, excepto a 1ª que é 0:

Ex: Para a string "banana" (tamanho da string é 6):

hash(0)=0

hash(1) = hash(0)+valor[1] = 0+(int)'a' = 0+97

hash(2) = hash(1)+valor[2] = 0+97+110

...

Ou seja, será algo deste género:

#define HASH_SIZE 100

int hashFunction(char *str) {
        int i, len=strlen(str), hash=0;
        for (i=1;i<len;i++)
                hash+=str[i];
        return hash%HASH_SIZE;
}

Utiliza-se o operador % com o HASH_SIZE (tamanho da tabela de hash) para garantir que os índices gerados se encontram dentro dos limites possíveis.

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
Sign in to follow this  

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