C - Fazendo uma tabela de hash de encadeamento separada - Problema
Passei algum tempo fazendo isso, esforçando-me para colocar variáveis compreensíveis e outras coisas. Tentei fazer com que parecesse limpo e arrumado. Para que eu possa depurá-lo facilmente. Mas não consigo encontrar o meu problema ... O terminal não exibe nada. Por favor me ajude a identificar meu erro!
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct list_node *node_ptr;
struct list_node
{
node_ptr next;
char *key;
char *value;
};
typedef node_ptr LIST;
typedef node_ptr position;
struct hash_table
{
LIST *list_ptr_arr;
unsigned int table_size;
};
typedef struct hash_table *HASHTABLE;
unsigned long long int
hash(const char *key, unsigned int hash_size)
{
unsigned long long int hash;
for(int i = 0; key[i]; i++)
{
hash = (hash<<32)+key[i];
}
return (hash%hash_size);
}
unsigned int
next_prime(int number)
{
int j;
for(int i = number; ; i++)
{
for(j = 2; j<i; j++)
{
if(i%j == 0){break;}
}
if(i==j){return j;}
}
}
HASHTABLE
initialize(unsigned int table_size)
{
HASHTABLE H;
H = (HASHTABLE) malloc(sizeof(struct hash_table));
if(H==NULL){printf("Out of Space!"); return 0;}
H->table_size = next_prime(table_size);
H->list_ptr_arr = (position*) malloc(sizeof(LIST)*table_size);
if(H->list_ptr_arr==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr = (LIST*) malloc(sizeof(struct list_node)*table_size);
for(unsigned int i = 0; i<table_size; i++)
{
if(H->list_ptr_arr[i]==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr[i]=NULL;
}
return H;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
node_ptr prev;
while(entry!=NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
prev = entry;
entry = prev->next;
}
entry = (position) malloc(sizeof(struct list_node));
entry->value = malloc(strlen(value)+1);
entry->key = malloc(strlen(key)+1);
strncpy(entry->key,key,strlen(key));
strncpy(entry->value,value,strlen(value));
entry->next = NULL;
prev->next = entry;
}
void
dump(HASHTABLE H)
{
for(unsigned int i = 0; i<H->table_size; i++)
{
position entry = H->list_ptr_arr[i];
if(H->list_ptr_arr[i]==NULL){continue;}
printf("slot[%d]: ", i);
for(;;)
{
printf("%s|%s -> ", entry->key, entry->value);
if(entry->next == NULL)
{
printf("NULL");
break;
}
entry = entry->next;
}
printf("\n");
}
}
int main()
{
HASHTABLE H = initialize(10);
insert("name1", "David", H);
insert("name2", "Lara", H);
insert("name3", "Slavka", H);
insert("name4", "Ivo", H);
insert("name5", "Radka", H);
insert("name6", "Kvetka", H);
dump(H);
return 0;
}
Tentei modificá-lo e mudar um pouco algumas coisas, mas nada ajudou ...
Agradecemos antecipadamente pessoal!
Respostas
Existem alguns problemas de beleza e pelo menos dois erros que quebram o código. Não vou entrar em coisas menores, é principalmente estilístico, mas suas funções initialize()e insert()não funcionam.
Em initialize()você aloca memória para H->list_ptr_arrayduas vezes. Isso vaza a memória da primeira alocação sem um bom motivo, mas é claro, isso não travará seu código, apenas vazará. Na segunda alocação, você aloca o tamanho errado, você usa sizeof(struct list_node) * tale_size, mas quer um array de ponteiros e não os structs (que, uma vez que os structs contêm ponteiros, serão maiores). Isso, novamente, apenas desperdiça memória e não a bloqueia. Ainda assim, você estaria melhor com a memória certa, que você pode obter usando
H->list_ptr_arr = malloc(table_size * sizeof *H->list_ptr_arr);
Você não precisa converter o resultado de malloc(), é um void *e você não precisa converter isso para tipos de ponteiro, mas isso é uma questão estilística. A parte importante dessa linha é que podemos obter o tamanho dos dados subjacentes da variável que atribuímos, o que sempre garantirá que obteremos o tamanho certo, mesmo se alterarmos o tipo em algum ponto. Eu também costumo usar sizeof(type)de vez em quando, mas sizeof *ptré o melhor padrão e vale a pena se acostumar.
De qualquer forma, embora você aloque a quantidade errada de memória, você aloca o suficiente para que seu programa não trave por causa disso. Mas quando você percorre os compartimentos alocados na tabela, retorna com um erro, se estiverem NULL. Eles não são inicializados de forma alguma, então se eles são NULL(e podem ser), então é por pura sorte. Ou, se você considerar isso um sinal de erro, infortúnio. Mas se você considerar NULLum sinal de erro de alocação aqui, por que então inicializa cada bin NULLlogo após concluir que não são?
Como está, sua inicialização será abortada se por acaso você obtiver um NULLponteiro no array, e como você não verifica os erros de alocação main()(o que é bom para um teste), esse pode ser o motivo pelo qual seu programa está travando. Não é o problema principal e só acontece se, por acaso, você pegar um NULLem uma de suas lixeiras, mas pode acontecer. Não faça a verificação para NULLquando você passar pelas caixas. As caixas não são inicializadas. Basta definir cada um para NULL.
É nas insert()principais mentiras do problema. Sua prevvariável não é inicializada antes do while-loop e, se você não entrar no loop, também não será depois. Definir prev->next = entryquando prevnão inicializado significa problema e é um provável candidato a um erro de travamento. Especialmente considerando que a primeira vez que você inserir algo em uma lixeira, entryserá NULL, então você acionará o erro logo na primeira vez. O que acontece quando você desreferencia um ponteiro não inicializado é indefinido, mas raramente significa algo bom. Um acidente é o melhor cenário.
Eu entendo a lógica aqui. Você deseja mover-se prevao longo da lista para que possa inserir o novo entryno final, e você não tem um último elemento antes de percorrer as entradas no bin. Mas isso não significa que você não pode ter um ponteiro inicializado para onde deseja inserir uma nova entrada. Se você usar um ponteiro para um ponteiro, pode começar com a entrada no array da tabela. Isso não é um list_node, então um list_node *não servirá prev, mas list_node **funcionará muito bem. Você pode fazer algo assim:
node_ptr new_entry(const char *key, const char *value)
{
node_ptr entry = malloc(sizeof *entry);
if (!entry) abort(); // Add error checking
entry->value = malloc(strlen(value) + 1);
entry->key = malloc(strlen(key) + 1);
strncpy(entry->key, key, strlen(key));
strncpy(entry->value, value, strlen(value));
entry->next = NULL;
return entry;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
// Make sure that we always have a prev, by pointing it
// to the location where we want to insert a new entry,
// which we want at the bin if nothing else
node_ptr *loc = &H->list_ptr_arr[slot];
while(entry != NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
// make loc the entry's next
loc = &entry->next;
// and move entry forward (we don't need prev->next now)
entry = entry->next;
}
// now loc will hold the address we should put
// the entry in
*loc = new_entry(key, value);
}
Claro, uma vez que as listas nas caixas não são classificadas ou mantidas em nenhuma ordem particular (a menos que haja restrições que você não tenha mencionado), você não precisa acrescentar novas entradas. Você também pode prefixá-los. Então você não precisa arrastar tal locpara outra busca linear. Você poderia fazer algo como:
node_ptr find_in_bin(const char *key, node_ptr bin)
{
for (node_ptr entry = bin; entry; entry = entry->next) {
if(strcmp(entry->key, key)==0)
return entry;
}
return 0;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr *bin = &H->list_ptr_arr[slot];
node_ptr entry = find_in_bin(key, *bin);
if (entry) {
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
} else {
*bin = new_entry(key, value, *bin);
}
}
Se você corrigir a inicialização e a inserção dessa forma, acho que o código deve funcionar. Ele serve para os poucos testes que eu passei, mas posso ter perdido algo.
Não é um erro como tal, mas algo que ainda comentarei rapidamente. A next_prime()função parece uma versão lenta da peneira de Eratóstenes. Tudo bem, ele calcula um primo (a menos que eu tenha esquecido alguma coisa), mas não é algo de que você precisa. Se você procurar por isso no Google, encontrará tabelas dos primeiros K primos, para K bem grande. Você pode incorporá-los facilmente em seu código. Isto é, se você realmente deseja que suas tabelas tenham tamanhos primos. Você não precisa, no entanto. Não há nada de errado em ter mesas de outros tamanhos.
Existem alguns benefícios no módulo primes para hashing, mas a tabela de hash não precisa ter o tamanho do primo para que isso funcione. Se você tem um grande P primo e uma tabela hash de tamanho M, você pode fazer ((i% P)% M) e obter os benefícios de fazer o módulo P e a conveniência de ter uma tabela de tamanho M. Quando você redimensiona tabelas e assim, é mais fácil se M for uma potência de dois, e então a última operação do módulo pode ser um mascaramento de bits muito rápido:
#define mask_k(n,k) (n & ((1 << k) - 1))
e depois ...
int index = mask_k(i % P, k); // where table size is 1 << k
O i % Ppode não ser necessário, depende de quão boa é a sua função hash. Se você tiver uma função hash que fornece números próximos a aleatórios, os bits em isão aleatórios e os kbits menos significativos também, e % Pnão fazem nada para melhorá-los. Mas se você quiser fazer um módulo primo, pode fazê-lo para um primo grande e mascará-lo para um tamanho de mesa menor, de forma que você não precise usar um tamanho de mesa que seja primo. E se você quiser ter um tamanho de mesa que seja primo de qualquer maneira, use uma tabela de primos. É lento ter que calcular novos números primos toda vez que você redimensiona a tabela.