Thread: Help understanding Hash Table

Code:

	for(i = 0 ; i < hashTable->size ; i++)
		hashTable->table[i] = (Hash_list*)malloc(sizeof(Hash_list)) ;

It seems to me that each table[i] is uninitialized (because you've used malloc() here, and not calloc() or memset() or anything).

Thank you, calloc made it all better! Now i have a slightly more annoying problem:
I have started making a real hash function now, instead of just returning 0 it now adds up each character in the string like so:

Code:

/* Hash function */
int hash(Hash_table *hashTable , char *elem){
	int i ;
	int x = 0 ;
	char c = elem[0];
	for(i = 0 ; c != '\0' ; i++){
		x = x + c ;
		c = elem[i+1] ;
	}
	return x ;
}

i initially had my hash table size set to 8, now i am getting keys way above that, to deal with that i am trying to resize the hash table like this:

Code:

Hash_table *addTableElement(Hash_table *old , char *elem){
	int h = hash(old , elem) ; //get hash key of string
	if(old->size < h){
		//printf("%s" , elem ) ;
		int oldSize = old->size - 1;
		old->size = h ;
		old->table = (Hash_list**)realloc(old->table , sizeof(Hash_list)*h) ;
		int i ;
		for(i = oldSize ; i < old->size ; i++){
			old->table[i] = (Hash_list*)calloc(1 , sizeof(Hash_list)) ;
		}
	} 
...... deal with nicely resized table....
return old ;
}

I know its wrong as its effecting code further in the program, but i'm not sure whats causing it! Am i at least on the right lines?

thanks!

Originally Posted by boblettoj99

Thank you, calloc made it all better! Now i have a slightly more annoying problem:
I have started making a real hash function now, instead of just returning 0 it now adds up each character in the string like so:

Code:

/* Hash function */
int hash(Hash_table *hashTable , char *elem){
	int i ;
	int x = 0 ;
	char c = elem[0];
	for(i = 0 ; c != '\0' ; i++){
		x = x + c ;
		c = elem[i+1] ;
	}
	return x ;
}

That works, but it hurt my brain a little, unnecessarily. What's wrong with

Code:

int hash(Hash_table *hashTable , char *elem) {
    int sum = 0, i;
    for(i = 0; elem[i]; i ++) {
        sum += elem[i];
    }
    return sum;
}

or even this? (If you happen to like pointers.)

Code:

int hash(Hash_table *hashTable , char *elem) {
    int sum = 0;
    while(*elem) {
        sum += *elem;
        elem ++;
    }
    return sum;
}

i initially had my hash table size set to 8, now i am getting keys way above that, to deal with that i am trying to resize the hash table ...

Usually in a hash table the key is modded by the size of the table; so you'd find the correct index into the table by using something like

Code:

hash(table, data) % table->size

You really shouldn't be resizing the table just because you have a key that's larger than it.

Then, since you're using a hash table with chaining, if multiple keys map to the same location in the table, you just look through the list of elements there. Read Wikipedia or something if you want to know more about this . . . .