CODEWITHSUNDEEP
clinked-listhashtable
user3765131
user3765131

Reputation:

Hash Table with linked list

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.

Upvotes: 2

Views: 10518

Answers (2)

T3am5hark
T3am5hark

Reputation: 866

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.

Upvotes: 3

pwilmot
pwilmot

Reputation: 315

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

Upvotes: 0

Related Questions