C++ (Hashing Function Help)

[wale89]

Hello..can anyone help me in order to solve this problem regarding the collision that happend.. I use the modulo-division hash function and intended to use the chaining solution method to resolve this collision but i got stuck.. because i dont really have the full knowledge in link list..Can someone that are good in this area help me..
Thanks so much..

This is the output from this program..

Modulo-Division Hashing Function

Student ID 379452 hashes to 0
Student ID 367173 hashes to 9
Student ID 166702 hashes to 10
Student ID 572556 hashes to 0
Press any key to continue . . .

#include <iostream>
#include <string>

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

using namespace std;
// Declare the struct

#define EMPTY_STUDENT_ID 0 // An Id of 0 means an empty record.
struct Student
{
    int id;
    std::string name;
    std::string telephone;
    std::string email;

    Student* pNext;
};

/* 
The HashTable is a structure of 2 elements, the first element records the size of the prime area
and the second element is a pointer to the start of the prime area.
*/
struct HashTable 
{
    int size;       /* the size of the table */
    Student *primeArea; /* the table elements */  
};

HashTable  *my_hash_table;
int size_of_table = 12;         


// Create an array of students.
// These will be put into a hash table
Student studentList[] = 
{
    {379452, "Mary Odd", "5555555", "[e-mail]" },
    {367173, "Sarah Alice", "5555555", "[e-mail]" },
    {166702, "Harry Joy", "5555555", "[e-mail]" },
    {572556, "Hidayah", "5555555", "[e-mail]"},
};

HashTable* create_hash_table(int size)
{
    HashTable* new_table; 

    if (size<1) return NULL; /* invalid size for table */

    // Allocate the hash table main structure
    if ((new_table = new HashTable) == NULL) {
        return NULL;
    }

    // Allocate the primeArea
    if ((new_table->primeArea = new Student[size]) == NULL) { 
        return NULL;
    }

    /* Initialize the elements of the table */
    for(int i=0; i<size; i++) 
    {
        new_table->primeArea[i].pNext = NULL;
        // An id of 0 means an empty record.
        new_table->primeArea[i].id = EMPTY_STUDENT_ID;

    }

    /* Set the table's size */
    new_table->size = size;

    return new_table;
}

// This is a hashing function.
unsigned int moduloDivisionHashFunction(Student *pStudent, unsigned int listSize)
{
    return pStudent->id % listSize;
}


void insert_to_hash_table(HashTable* ht, Student* record)
{
     
     //This is where the chaining solution should be taken
      
    unsigned int hashValue = moduloDivisionHashFunction(record, my_hash_table->size);	
    cout<< "Student ID " << record->id << " hashes to " << hashValue << endl;

    ht->primeArea[hashValue].id = record->id;     
    ht->primeArea[hashValue].name = record->name;
    ht->primeArea[hashValue].telephone= record->telephone;
    ht->primeArea[hashValue].email = record->email;

}

int main(void)
{
    cout<<"Modulo-Division Hashing Function"<<endl;

    my_hash_table = create_hash_table(size_of_table);

    // go through the studentList using a loop
    int studentListSize = ARRAY_SIZE(studentList);
    for(int i = 0; i < studentListSize ; i++) 
    {

        insert_to_hash_table(my_hash_table, &studentList[i]);
    }

    system("pause");
    return 0;
}

[craig_ka]

This will solve your collision problem. When a record is added its pNext pointer is allocated and id set to EMPTY, this way you can simply iterate the list til you get to the EMPTY id and insert your new data in this record.

void insert_to_hash_table(HashTable* ht, Student* record)
{
     
     //This is where the chaining solution should be taken
    Student* currentRecord;  
    unsigned int hashValue = moduloDivisionHashFunction(record, my_hash_table->size);	
    cout<< "Student ID " << record->id << " hashes to " << hashValue << endl;
    
    currentRecord = &ht->primeArea[hashValue];
    while(currentRecord->id != EMPTY_STUDENT_ID)
    {
        currentRecord = currentRecord->pNext;
    }
    currentRecord->id = record->id;     
    currentRecord->name = record->name;
    currentRecord->telephone= record->telephone;
    currentRecord->email = record->email;
    currentRecord->pNext = new Student;
    currentRecord->pNext->id = EMPTY_STUDENT_ID;
        

}

Although this program will work and modern OS's can clean up your mess for you, you really should have a destructor function for your hash table and also for your student records. Your current version has a lot of memory leaks.