Hashing a struct in C

Question

I'm trying to learn how chained hashing works, but can't get any further than this. I think hashing works, but after finishing this little program, someone told me that what I have created so far has nothing to do with hashing.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define size 5
//This is my struct I wanted to add to the hashtable
struct customer{
    char name[20];
    int id;
    int pin;
    double money;
    struct customer *next;
};

//creating the table
struct customer *hash_table[size];
struct customer *next=NULL;
//my hashfunction
int hash_function(int id){
    unsigned int adress_hash;
    adress_hash = 31 * id;
    return adress_hash % 5;
}

//Adding the cust elements to my table
void add_customer(){
    int id_set = rand() % 8999 + 1000;
    struct customer *start;
    struct customer *pointer;
    int adress = hash_function(id_set);

     //first element

    if(hash_table[adress]==NULL)
    {
        hash_table[adress] = malloc(sizeof(struct customer));
        hash_table[adress]->id= id_set;
        hash_table[adress]->pin= rand() % 8999 + 1000;

        hash_table[adress]->money= 0;
        hash_table[adress]->next=NULL;
    } else {
        //Adding new files if the first element of the table is NOT NULL
        pointer=hash_table[adress];
        while(pointer->next != NULL)
        {
            pointer= pointer->next;
        }
        pointer->next = malloc(sizeof(struct customer));
        pointer=pointer->next;
        pointer->id=id_set;
        pointer->pin= rand() % 8999 + 1000;
        pointer->money = 0;

        pointer->next=NULL;
    }
}

void list_customer(int a){
    struct customer *pointer;
    int x;
    for(x=0;x<5;x++){
        pointer = hash_table[x];
        printf("%d. ----------\n", x);
        while(pointer != 0){
            printf("KNR: %d, PIN: %d\n", pointer->id, pointer->pin);
            pointer = pointer->next;
        }
        printf("-------------------------\n");
    }
}

int main(){
    int adr,x;
    srand(time(NULL));
    for(x=0;x<5;x++){
        add_customer();
    }
    list_customer(size);
    getchar();getchar();
    return 0;
}

Answer 1

I see a number of things that may help you improve your code.

Understand the purpose of a hash table

The purpose of a hash table is as an associative array. In this code, the id element of the customer structure is used as the hashed value and the hash function converts that int value into a number in the smaller range of size. It's a valid use of a hash function and hash table. The only thing missing is a means to actually use the hash function to quickly find a customer record. To do that, you might implement a find_customer function that would search only in the appropriate "bucket" of the hash_table given the id. With a large number of records \$n\$ where \$n \gg\$ size, this could save look-up time by needing to search only 20% of the records rather than all of them. With that said, what follows is a review of the code you posted.

Eliminate unused variables

The parameter a in the list_customer() function, adr in main(), and start in add_customer() are all unused variables and should be omitted from the program.

Free allocated memory

Generally speaking, if you allocate memory using malloc or calloc, you should also free that memory to avoid "leaking" memory.

Eliminate "magic numbers"

In a number of cases, the code uses "magic numbers" such as 8999 and 1000 that have no obvious meaning. These would be better as named constants. Also, a named constant size is already defined in the code, and should be used within list_customer() instead of hard coding 5.

Use better variable names

The names hash_table and id are good names, but pointer is not a good name because it is too generic. I'd recommend something like cust_ptr (or Kunde if you prefer German).

Declare variables in the smallest practical scope

By declaring variables in the smalles practical scope, you reduce the chance for name collisions and make it clear to the reader of your code where variables are and are not needed. With any C compiler conforming to the 1999 specification (which should be all of them at this point!) one could rewrite list_customer like this for example:

void list_customer(){
    for(int x = 0; x < size; x++){
        printf("%d. ----------\n", x);
        for (struct customer *cust_ptr = hash_table[x];
                cust_ptr != NULL; cust_ptr = cust_ptr->next)
        {
            printf("KNR: %d, PIN: %d\n", cust_ptr->id, cust_ptr->pin);
        }
        printf("-------------------------\n");
    }
}

Note also that I have converted your while loop into a for loop which I think clarifies the nature of the code.

Check the return value of malloc

If the system is running out of memory, malloc will return NULL. Code must check the return value to make sure it is not NULL before dereferencing the variable or the program will crash.

Avoid repeating code

Two places in the code use the construct rand() % 8999 + 1000 which suggests that they should probably be made into a function or macro.

Functions taking no parameter should be declared void

A function declared as void add_customer() in C may actually take any number of parameters which is an old misfeature of the C language. What you probably want instead is to declare it as taking no parameters which is done like this:

void add_customer(void)

Create subfunctions to keep the code clear and neat

The add_customer() code needs to create a new customer and then put it into the hash_table. We can delegate the creation to a separate function:

struct customer *new_customer(int id)
{
    struct customer *cust_ptr = malloc(sizeof(struct customer));
    if (cust_ptr != NULL) {
        cust_ptr->name[0] = '\0';
        cust_ptr->id = id;
        cust_ptr->pin = myrand();
        cust_ptr->money = 0;
        cust_ptr->next = NULL;
    }
    return cust_ptr;
}

Note that this code initializes the name member which the original code did not. Now the add_customer code can be much simpler:

void add_customer(void){
    int id_set = myrand();
    int adress = hash_function(id_set);
    struct customer *cust_ptr = hash_table[adress];
    if (cust_ptr == NULL) {
        hash_table[adress] = new_customer(id_set);
        return;
    } 
    while(cust_ptr->next != NULL) {
        cust_ptr = cust_ptr->next; 
    }
    cust_ptr->next = new_customer(id_set);
}

And of course the myrand() function:

int myrand(void) 
{
    return rand() % 8999 + 1000;
}

Omit return 0 at the end of main

The compiler will automatically generate the equivalent to return 0 for code that successfully gets to the end of main.