HASHTABLE

[Llaverola]

Ola pessoal, tenho um enorme problema. tenho um trabalho final pa fazer numa cadeira d programação no meu curso e tou com imensas dificuldades.

ALGUM DE VOCES PODE-ME ARRANJAR O CODIGO EM C DE UMA HASHTABLE?

obrigado

[Rui Carlos]

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

Eu sugeria-te ler alguma coisa sobre hash tables, em vez de andar a pedir código. Não é difícil encontrar implementações de hash tables na net, mas é bom que compreendas os conceitos que estão por trás delas, até porque há vários tipos de hash table, com as mais variadas implementações.

[mogers]

O Rui Carlos disse tudo. Eu tenho a minha implementação de uma hash table mas se ta fornecesse não ias aprender nada com isso e provavelmente não a ias saber usar sem analisar a estrutura de uma hash table.

Contudo, posso enviar-te para o email uma página web da usaco, sobre estruturas de dados (incluindo hash tables). Não posso por o link porque a página não é pública. Só avançando no treino deles é que vamos tendo acesso aos textos deles.

[Llaverola]

Mais uma coisa, eu tenho as funçoes todas duma hashtable implementadas.

só q n sei criar o main, para poder usar a hastable....ou seja, quero ver a correr o programa. como fazer isso?

[Llaverola]

Estou a fazer uma hastable, e neste momento deparo-me com uma duvida....

como criar uma hastable?

outra duvida: e esta importante tb, alguem me pode fornecer o source code da função hashcode()? pretendo criar uma função hashcode dum determinada string. aguardo ajuda. obrigado

[Rui Carlos]

Não há a função hashcode, há várias formas de implementar uma função para esse efeito. Uma simples, é somar todos os caracteres.

[Llaverola]

mas ao somar todos caracteres, n vai haver palavras com o mm hashcode...ou vai?

ja agora,é uma soma simpleS? ou cada caracter corresponde ao seu codigo ascii e soma-se esse codigo?

[mogers]

Uma melhor função de hash é multiplicar os códigos ascci dos caracteres... a soma é demasiado fraca...

melhor ainda é multiplicares o código ascii de cada letra por um número primo, exemplo 37 😄

[Rui Carlos]

mas ao somar todos caracteres, n vai haver palavras com o mm hashcode...ou vai?

ja agora,é uma soma simpleS? ou cada caracter corresponde ao seu codigo ascii e soma-se esse codigo?

Para não haver colisões podes elevar números primos diferentes ao valor de cada letra.

Por exemplo:

2^str[0] + 3^str[1] + 5^str[3] + 7^str[4] + ...

(os primos não precisam de estar ordenados, apenas precisam de ser todos diferentes).

Matematicamente, garantes que não há duas strings diferentes com o mesmo hash, mas também vão poder atingir valores extremamente elevados. Logo isto não vai evitar colisões na Hash Table, a menos que as posições da tua Hash Table cresçam tanto quanto queiras.

Dependendo do tamanho da Hash Table e das strings, a soma das letras poderá ou não ser suficiente.