Issue with hash table chaining in C

Question

My homework an introductory C class is to complete the implementation of a hash table with dynamic allocation. I have to use the header file provided and I'm not sure what I'm doing wrong. Header file:

/// structure for the nodes of the chains
struct node_s {
    char *key;
    int value;
    struct node_s *link;
};

/// This is the main structure for the overall table.
struct table_s {
    /// This should be used as a pointer to a dynamically
    /// allocated array of pointers to node structures.
    struct node_s **table;

    /// This is for storing the maximum number of buckets/lists in the table.
    size_t bins;

    /// This is for storing the current number of elements in the table
    size_t size;
};
    /// A convenience declaration for referring to a pointer to a HT..
    typedef struct table_s *hash_t;

What I need to implement:

/// Allocate a table with some initial empty bins.
/// @param bins -- the number of bins in the table (initally empty)
/// @return -- a pointer to a dynamically allocated hash table
hash_t create_table(int bins){
        struct node_s *nodes[bins];
        for(int i = 0; i < bins; i++){
                nodes[i] = NULL;
        }
        hash_t table = malloc(sizeof(hash_t));
        table -> table = nodes;
        table -> bins = bins;
        table -> size = 0;
        return table;
}

/// Set the value for a key in a given hash table.
/// @note -- if this is the first time setting this key, then the
///          table must make a dynamic copy of the string.  This
///          copy must be freed when the table is freed.
/// @note -- if the table exceeds a load factor of 1 after setting
///          the key/value pair, then this function should trigger
///          rehashing into a larger table.  It will then deallocate
///          the table field in the table_s structure, but it will
///          NOT free the table address in the table parameter.
/// @param table -- a pointer to a hash table

void set(hash_t table, char *key, int value){
        int index = hash(key) % table -> bins;
        printf("Index: %d\n", index);
        struct node_s *node = table -> table[index];
        struct node_s *newNode = malloc(sizeof(newNode));
        newNode -> key  = key;
        newNode -> value = value;
        newNode -> link = NULL;

        printf("New node, key: %s\n", newNode -> key);
        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }
        printf("\n");
}

What runs:

 char key[max_key];
    hash_t table = create_table(10);
    for (int i = 0; i < trials; i++) {
        int sample = rand() % max_num;
        sprintf(key, "%d", sample);
        set(table, key, sample);
    }

Output:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NOT NULL!
Segmentation fault (core dumped)

Expected output:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NULL!
New bucket filled!

And so on, until a collision when the node at index is not NULL, where newNode chains itself by replacing the NULL *link of the last node present.

I know my chaining isn't quite correct yet and needs to be expanded upon, but I'm just really confused as to why it's not registering the NULL at index and placing a new linked list node, and is instead trying to add onto the linked list as though there was a collision.

Answer 1

Coding tip: Don't put a space before/after the dot . or arrow -> operators.

Instead of this:

table -> bins

This:

table->bins

Your actual issue is this. create_table isn't propertly allocating memory for bins. Even worse, it's using an array on the stack. That memory is undefined behavior as soon as create_table returns. Better:

hash_t create_table(int bins){
        hash_t table = malloc(sizeof(hash_t));
        table->table = calloc(sizeof(struct node_s*) * bins); //malloc and zero-init
        table->bins = bins
        table->size = 0;
        return table;
}

Also, instead of this:

        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }

Just do this:

printf("%s\n", (table->table[index] ? "Filled bucked!" : "Chained!"));
newNode->link = table->table[index];
table->table[index] = newNode;

Each time a new node gets added to a bin, it becomes the head item in the bin's linked list. The chaining happens at the front of the each bin's list instead of the back.