I understand what you're saying but it has very little to do with my main issues...
I just did linear probing in the first place because it was simpler and I just wanted to have the hash table working and then move to optimize it and make it better. One step at a time...
What "bothered" me about your first post is that you are saying that what I'm doing is not an HashTable while I think it is...
Originally Posted by
MK27
You have a fixed number of buckets (the array indexes).
That's what I have, the *items in the hash table is the array which will be dynamically allocated. Each element of that array, has a key/value pair.
Originally Posted by
MK27
The array should be an array of pointers, generally each pointer is to the head of a linked list.
It is in array of pointers to each element.
Originally Posted by
MK27
You don't look for an empty bucket -- you compute which bucket to use based on the value of the key.
And this is exactly what I'm doing... You can say that I'm looking for an empty bucket but that's because of open addressing using linear probing. But at first, I'm computing which is the bucket I'm supposed to use based on the key value and if it's free, good, if it's not, I move to the next one. That's the basis for linear probing. But like I said, I'll be moving to chaining in the future, I just need to fix my problems first.
But there's no problem in using linear probing. It's not the best method, I know that, but as long as I justify my choices.
But once again, this is very little to do with my main issues... I don't even know how you started pointing those things out when I didn't even posted my hashInsert code. Ok, I know you realized there was no *next pointer for the next bucket when dealing with collisions, but I didn't asked anything about that cause that was not my problem :P
Anyway, back into the issues...
So far, I think I've solved them, I just don't know if this is the way to go...
For testing purposes, I'm using char* as key and simple struct as value:
Code:
typedef struct sTest {
char string[10];
int num;
} Test;
Then I changed my hashInsert function to this:
Code:
Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz, HashValue value, size_t val_sz)
And I call it like this, for instance:
Code:
char str[50];
Test hVal;
strcpy(hVal.string, "ABC");
hVal.num = 123;
scanf("%s%*c", str);
hashInsert(t1, str, strlen(str)+1, &hVal, sizeof(Test));
And then, when I find an empty bucket (using linear probing) I do something like this:
Code:
table->items[index].key = xmalloc(key_sz);
memcpy(table->items[index].key, key, key_sz);
table->items[index].value = xmalloc(val_sz);
memcpy(table->items[index].value, value, val_sz);
Note: xmalloc() calls malloc and does some error handling.
And to finish, my hashDestroy function does something like this to free everything:
Code:
for(i = 0; i < (*table)->size; i++) {
if((*table)->items[i].status != EMPTY) {
free((*table)->items[i].key);
free((*table)->items[i].value);
}
}
So far, all my testing worked fine but do you think there's something wrong with this approach on allocating/freeing memory?
I can only think of one real problem for this solution, if my Test struct had some pointers inside, that would be an issue. Right? The solutions for this would be either to provide a function pointer in the hashInitialize function to free whatever it needs or don't bother it and that's the main programmer's job, to free whatever he allocated.
But since this is a project where I'll be coding everything and where one of the objectives is modular code, I simply won't use any pointers inside the struct and call it a day. If I have a time in the end, I might adapt the code to provide the "free function" pointer on the initialization.