Pesquisar numa tabela hash polinomial

[angelicous]

Boas

eu tenho uma tabela hash polinomial, que me codifica palavras que têm 2 letras e 2 números. Por exemplo

AB123

o formato que uso para a codificação é esta

key(k) = k1 + k2*A² + k3*A^3... +Kn*A^n

Onde k1 é a primeira letra, k2 a segunda ... e A é um número primo, que no meu caso é 11.

Agora eu tenho a tabela com as palavras, sem qualquer problema a pesquisar palavras completas...

O meu problema é, eu quero fazer uma função, onde é fornecida a primeira letra, e eu quero que ele me retorne todas as palavras na tabela que começam com essa letra. Não conhecendo a ordem da tabela visto que a hash gera as posições aleatóriamente, como é que posso fazer isto, sem ter que correr a tabela toda de ponta a ponta?

[HappyHippyHippo]

se a ordem dos elementos é completamente aleatória, então não tens alternativa senão percorrer/verificar todos os elementos

[angelicous]

Hmm, eu posso alterar estrutura e até o algoritmo da hash... Achas que existe algo eficiente para este formato ou o melhor é descartar já hash?

[HappyHippyHippo]

qualquer tipo de estrutura/algoritmo desse género, é agnóstico ao tipo de dados em si contido.

agora, se não te importa a ordem dos valores guardados, o que não faltam são estrutura em que a ordem de grandeza em termos de pesquisa são de O(log n)

[angelicous]

Mas eu queria encontrar algo de O(1) 😛

Dai escolher as hash. Não era sempre O(1) quando existissem colisões, mas na maior parte era... E mesmo quando existiam colisões, penso que mesmo assim era melhor que log n. Não cheguei a testar essa parte, por ter encontrado este contratempo que não tinha pensado...

No pior dos casos faço mix de estruturas para a pesquisa que quiser fazer... Se bem que só encontro problemas quando não tenho como pesquisar a palavra toda...

[angelicous]

Precisava de uma ajuda pessoal em seguimento deste problema. Decidi contornar este problema, fazendo um género de array de hash's para cada letra, em vez do ficheiro geral. Isto é um AB111 indexa na hash na posição 0 do array, o BA111 na posição 1, etc etc

Com base nesta ideia estou a tentar criar uma matriz de estruturas. Só que têm que ser dinâmica visto que o número de ocorrências por letra varia.

A ideia é no fim poder usar os [ ] [ ] para aceder às estruturas da matriz. As dimensões para cada coluna, eu tenho guardadas em um array auxiliar chamado r que ao ler um ficheiro vai incrementando o número de ocorrências.

Mas algo não está a bater aqui bem, porque apesar de compilar com warnings, ao imprimir o conteúdo da matriz, dá-me lixo. Alguém me pode ajudar a ver o que estou a fazer mal?

struct cliente {
char nome[9];
struct cliente* next;
};
typedef struct cliente *ClienteSing;
typedef ClienteSing* Cliente[26];
//Aloca memoria para a matriz. R é o array que me diz o número de ocorrências de determinada letra no ficheiro.
void initArrayCliente (Cliente a, int* r){
int i=0;
for(i=0;i<26;i++)
a[i]=(ClienteSing) calloc (r[i],sizeof(struct cliente));
}
//Em caso de obter uma colisão resultante da hash, faz uma lista ligada dessas estruturas a partir dessa posição.
void ultimoRamo (ClienteSing a, ClienteSing b){
ClienteSing temp;
temp=a;
while (temp->next!=NULL)
temp=temp->next;
temp->next=b;
}
//Cria um cliente b a partir da palavra str. Caso a posição no array esteja nula, insere o B. Caso não esteja, vai até à ultima posição do ramo, e insere.
void insere(Cliente a, char* str, int indice){
ClienteSing b;
b= (ClienteSing) malloc (sizeof(struct cliente));
strcpy (b->nome, str);
b->next=NULL;
if (a[str[0]-'A'][indice]==NULL)
{
a[str[0]-'A'][indice]=b;
printf("Livre\n");
}
else {
ultimoRamo(a[str[0]-'A'][indice],b);
printf("Colisão\n");
}
}

[mogers]

Como já foi dito, uma hash table não me parece ser uma solução adequada para o teu problema.

Se queres todas as palavras começadas por um dado prefixo, seja "A", "B", "XYZ", etc, considera o uso de uma Trie - http://en.wikipedia.org/wiki/Trie

Cuidado que a Trie pode consumir bastante memória dependendo da tua implementação e do teu conjunto de palavras.

[angelicous]

Tries não são uma solução para o problema.

E como disse, estou a fazer uma hash para cada letra. É uma solução.