2

I have a trouble with an exercise for school.

I have to implement a hash table using this structure :

struct Book {
char * title;
char * author;
int price;
struct Book * next;
}

So I have to create a function initTable() which create my hash table which is a table of struct Book of 1000 elements. So my function is :

struct Book* initTable(){
struct Book *tab = malloc(sizeof(struct Book) * 1000);
return tab;
}

Note that the function is supposed to return the first element of my table. But I don't know if this syntax is correct.

So my questions are :

  1. Is that a correct syntax ?

  2. How can I navigate in the table ? For example, if I want to go to the cell 50 of my table, how can I do?

Then, if there's a collision in my hash table, I have to create a linked list where I put my elements in conflict. But each cells of my table are a structure and not a pointer of this structure, so I don't understand how I can link my elements.

Improve this question
6
  • Are you sure your table is supposed to be a table of structs, and not table of pointers to structs? Commented Jun 22, 2014 at 17:29
  • for clarification you are likely creating an array[1000] of linked lists. These lists can contain only a single element but on hash conflict will contain more Commented Jun 22, 2014 at 17:30
  • One thing you are missing is initializing the table items. You could add memset call after malloc, or replace malloc with calloc (which zeroes the memory it allocates). Commented Jun 22, 2014 at 17:42
  • is that a correct syntax? - well why do you ask? why don't you try compiling it? if it compiles, the syntax is correct. Commented Jun 22, 2014 at 17:48
  • I mean, is that the good way to make a hash table of struct Book Commented Jun 22, 2014 at 17:49

2 Answers 2

Reset to default
3

A hash table is meant to look up an entry in a collection by key in constant time. In terms of implementation this typically consists of a "hidden" array of object pointers (not the objects themselves). You then need a hashing function that converts a key into an array lookup index (integer). As an example:

ValueObjectType **createHashTable(int hashSize)
{
    ValueObjectType **table = malloc( sizeof(ValueObjectType *) * hashSize);
    return table;
}

void hashInsert(ValueObjectType **hashTable, KeyObjectType key, ValueObjectType *value)
{
    int arrayIndex = hashingFunction(key);
    if ( hashTable[arrayIndex] != NULL ) traverseLinkedListAndAdd(...);
    else hashTable[arrayIndex] = value;
}

ValueObjectType *lookupByKey(ValueObjectType **hashTable, KeyObjectType key)
{
    int arrayIndex = hashingFunction(key);
    return traverseLinkedListAndReturnObjectWithKey(...);        
}

A hashing function usually involves taking one or more key elements (which can be of any type) and converting them to a single integer value and then converting that to an array index by taking the modulo of the hash array size.

The purpose for the linked list in your Book struct is to deal with hash collisions. A hash collision occurs on insert either because the given key already exists in the hash (in which case you should replace the value object reference with the new object) or because of the non-uniqueness of the hashing function. When the latter happens, the linked list is used to store multiple entries with different keys that hash to the same array index (typically by iterating through the list, replacing an element of the list if key equality is seen, and otherwise tacking the new object on at the end).

In the example code above I have a separate key object, but in order to evaluate equality of the key it needs to be either included in the object itself (I suspect in your case the key is some combination of title and author), or wrapped in a meta structure (such as a "KeyValue" struct that contains a pointer to the key and the value, which you would hash instead of ValueObjectType). You need to provide logic to evaluate equality/inequality of two keys in order to properly handle the hash collision case.

I've left the hashing function, linked list navigation, and key equality logic unspecified here because this is clearly what your instructor wants you to learn how to do.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

My teacher gave me the hash function that deals only with the title of the Book. The header of the function initTable() has to be the same that my teacher gave me. What disturbing me is, if I have to deal with linked list in my hash table, so my hash table has to contain pointer to structures Book and not only structure no ?
Like I said in the answer, the linked list is how you deal with hash collisions (which happen when two different keys yield the same array lookup index). The general algorithm for hashes is described in the answer above - you can figure out the specifics for your homework problem.
0

you want to 

malloc(sizeof(struct book) * 1000)

What malloc does is allocates memory. First a pointer for the start of the object then additional space for anything else that will be stored in this object. In your case you want to create an array of 1000 objects so you need to allocate memory for all of these objects after the initial pointer.

for navigating an allocated array look into pointer arithmetic. Essential what this means is that you are looking for an object at an offset from the initial pointer.

for a start on pointer arithmatic check out http://www.eskimo.com/~scs/cclass/notes/sx10b.html

Improve this answer

7 Comments

Thank you for you reply.But excuse me for asking this but how can I do what you propose ? I don't see very clearly how I can do. Sorry for disturbing you.
you are mallocing an array of Livre and storing that array as a pointer to a Livre
Sorry I've made a mistake, is Book in the function.
In fact, the subject that I have says "Make a function allowing to create a hash table, which is a table of struct Book containing 1000 elements. This function has to allocate a table of 1000 struct Book and return a pointer to the first element of the table"
great looks like you got it now. As long as you understand why you need sizeof(struct book) inside of the call to malloc
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.